Assignment 5 FAQ
NP and graphs
Q. No matter how much I read or think about it, what exactly NP, NP-Hard, and NP-Complete still evades me.
A. See "notes on NP" for some additional summary/background.
Bin and Radix Sorts
Q. Did we talk about radix sort in class?
A. Yes. It is the bin-sort variant that we discussed with a deck of cards, e.g.
Q. This doesn't seem like very much data. Why use a hashtable?
A. 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 in a national-scale lottery; that is probably a more comparable set of numbers for today's technologies.
Q. "...where m is the number of external buckets in which the records will be stored..." I’m confused as to what m is supposed to be.... What’s an external bucket?
A. The problem suggests that the ticket numbers will be hashed to provide a dictionary (stored internally in memory), while the actual tickets will be stored externally (e.g., in a file or database). The external buckets therefore refer to the storage of actual ticket info. You may further assume that this proposal uses what wikipedia calls "separate chaining", also called "open hashing" or "closed addressing" (not to be confused with "closed hashing" or "open addressing"). Cormen et al. call this "collision resolution by chaining". This means that the buckets are the associated linked lists.
Turing Machine programming
Q. When you ask for implementation level descriptions of Turning machines, can we just give the state diagram that we make in JFLAP or do we need to write out the entire formal definition as well, where we define what Q, sigma, and all of those other things are, even though they are generally implicitly defined by the diagram?
A. JFLAP is fine; it gives a sufficient description to determine how the proposed TM works.
Q. For question 5, I want to show a 2-PDA is more powerful than a 1-PDA by using a language that is recognizable by the former but not by the latter. If I choose a language that is known not to be recognizable by a 1-PDA, do I have to re-prove this unrecognizability?
A. No. If the language is widely known not to be recognizable by a traditional PDA (or, e.g., if it is proved in Sipser), this is sufficient. Please note that I am not inviting you to search for languages that someone else has proved to be non-context-free; I'm saying there are some conventional examples and if you use one of those, you don't have to prove the non-context-free-ness.
Q. Should I prove 2-PDAs and 3-PDAs equivalent by proving that each can simulate the other?
A. The hint in the problem suggests that a 2-PDA can simulate a Turing Machine. That's probably an easier way to go....
General advice for this problem: Think about the limitation of a PDA vs. a TM. Why is a PDA more limited? What can a TM do that a PDA can't? Also, note that this is a problem that isn't very hard to write up but does require some key insights. If you're struggling with it, I suggest you make sure that you understand the question, then put it aside for a while and do other things. The answer is at least as likely to occur to you when your mind is wandering as through continued beating your head against it. (You *do* need to understand it first, of course.)