15-110 Spring 2011 Quiz 1
15 minutes

SHOW YOUR WORK.  Correct answers without supporting work will not receive credit.
For questions saying “in 10 words or less”, we will only grade the first 10 words you write!

1.       [15 pts]  Convert 43 from decimal to binary.

2.       [10 pts]  In 10 words or less, why do we care (in this course) about converting from decimal to binary?

3.       Solve the following Knights and Knaves questions using the approach we covered in class.

a.       [20 pts]  Assume Carly says:  “Of I and Ralph, only one is a knight”.  Give a logical expression (in terms of C and R) for SC (the Statement by Carly), and then fill out this truth table (which includes only the columns C, R, and SC):

b.      [10 pts]  If a given Knights and Knaves problem has 4 characters (Alice, Bob, Charles, and Dawn), how many rows (besides the header row) must be in the truth table used to solve it?

4.       [15 pts]  Sort the list [3, 4, 1, 2] into increasing order using selection sort (use the version that finds the min on each pass, and not the max).  Each time the algorithm would swap two items, circle those two items and write a new list below with the items swapped.  Continue in this fashion until the list is sorted.

5.       [10 pts]  Merge sort requires an extra list.  In 10 words or less, why?

6.       [10 pts]  In 10 words or less, what is a Reverse Turing Test as mentioned in the CAPTCHA article?

7.       [10 pts]  In 10 words or less, explain this quote:  “Unlike earlier efforts at crowd-sourced science, EteRNA will cross over from [computer] simulation to [real-world] biology.”