Assignment 5

Last updated 18 September 2010

See also: Assignment5FAQ with questions I've been asked and answers I've given.

Due Tuesday 7 December on paper in class and by email to LAS with the clearly labeled subject line FOCS assignment 5.

This assignment is released as of 9:45pm Thursday November 18.

(If you do it on paper, use the handy dandy scanner/copiers to email ...)

1. NP and graphs

   • Just added "notes on NP"

     (based on Sipser 7.11) Call graphs G and H isomorphic if the nodes of G may be reordered so that it is identical to H. Let ISO = {<G,H>|G and H are isomorphic graphs}.

   • Are the following undirected graphs isomorphic (i.e., is <A,B>, <B,C>, or <A,C> in ISO)? Explain.

     A = ({a,b,c,d,e,f},{(a,b),(a,c),(a,d),(a,e),(b,e),(b,f),(c,d),(c,f),(d,e),(d,f),(e,f)})
     B = ({g,h,i,j,k,l},{(g,h),(h,i),(i,j),(g,k),(k,l),(j,h),(i,l),(i,k),(h,k),(j,k),(j,g)})
     C = ({p,q,r,s,t,u},{(p,r),(s,p),(q,t),(u,p),(u,s),(q,u),(t,u),(p,t),(q,r),(r,s),(r,t)}) 

   • Show that ISO is in NP, i.e., that it can be solved using a non-deterministic polynomial-time algorithm. (Hint: short certificates)
2. Bin and Radix Sorts
   • Use Radix Sort to sort the following numbers. Show the sort results after each pass, indicating the bin separations with |

     639 933 789 638 738 311 293 382 493 849 348 282 439

3. Hashtables

   • (Lewis and Denenberg 8.28; See Note at the bottom of this page) When you buy a ticket in the State Lottery, you choose six different numbers between 1 and 36. The lottery officials keep a dictionary keyed on the set of six numbers chosen on each ticket. After the officials pick the winning numbers, they access this dictionary to identify the winning ticket or tickets, if any. Since millions of tickets are sold, the officials have decided to keep the dictionary in external storage with a directory in an internal hash table. Their computer consultant, S.L.Ow, has recommended that they use the hash function h(x_1_,x_2_,x_3_,x_4_,x_5_,x_6_) = (x_1_ + x_2_ + x_3_ + x_4_+ x_5_ + x_6_) mod m where m is the number of external buckets in which the records will be stored. Give a critique of this recommendation, and suggest a better alternative.

4. Turing Machine programming
   • (Sipser 3.8) Give implementation-level descriptions of Turing machines that decide the following languages over the alphabet {0,1}:
     1. {w|w contains an equal number of 0s and 1s}
     2. {w|w contains twice as many 0s as 1s}
     3. {w|w does not contain twice as many 0s as 1s}
5. Automata
   • (Sipser 3.9) Let a k-PDA be a pushdown automaton that has k stacks. Thus, a 0-PDA is an NFA and a 1-PDA is a conventional PDA. You already know that 1-PDAs are more powerful (recognize a larger class of languages) than 0-PDAs.
   • Show that 2-PDAs are more powerful than 1-PDAs.

   • Show that 3-PDAs are not more powerful than 2-PDAs. (Hint: Simulate a Turing machine tape with two stacks.)

Note on Hashtable problem: This problem was written when memory was harder to come by. If you feel that the numbers here are insufficiently motivating, imagine instead that the ticket contains 8 choices drawn from numbers between 1 and 100; that is probably a more comparable set of numbers for today's technologies.