Click for Syllabus

Homework Assignments
Please use the <Discussion Board> to ask questions about the homework. Click on <Communication>, then <Discussion Board> ()()Sets of problems in parentheses count as a single, five-point problem.()()
Homework 1 Due February 11, 2008, in class. Each problem is worth 20 points.	0.  For this problem, I am interested in making sure that you have a firm grasp of some basic definitions.    a.  Give an example of a language that has fewer elements than its alphabet.    b.  Give an example of an algorithm that takes as input strings over the alphabet {0, 1}, and         which terminates on all but one input.    c.  How many languages are there over the alphabet {0}?  Finite, countable or uncountable?    d.  Suppose I want to solve the problem of determining whether some given set of polyominos         tiles a rectangle of some given dimensions.  Describe a process by which we could stringify         a problem instance over the alphabet consisting of all characters on the keyboard. 1.  For a string w, let L*(w) = {<M> | M is a T.M. which accepts w}.  For which w is L*(w) Turing-Recognizable?  For which w is L*(w) Turing-Decidable? 2.  Let EQstring = {<v, w> | L*(v) = L*(w)}, using the terminology of the previous problem.  Prove that EQstring is Turing decidable. 3.  We have seen languages which are not Turing-recognizable, but these languages tended to be very specific encodings of machines.     a.  Prove that there is a language over the alphabet {a} which is not Turing-recognizable    b.  Build a language as follows:  List all the strings over {0, 1}, and then go down that list, flipping a coin for each string and including it in the language if and only if you get Heads.  What is the probability that the resulting language will be Turing-recognizable? 4.  Let A17 = {<M> | L(M) contains at least 17 strings}. Prove that A17 is Turing-recognizable but not Turing-decidable.
Exam 1 Study Guide	Pretty much everything from Chapters 3, 4, 5, 7, except: Chapter 4, we didn't talk about Theorems 4.3, 4.6, 4.7 or 4.8. Chapter 5, we didn't talk about Theorem 5.10, and we didn't do the details of the PCP, just the general idea. Chapter 7, we didn't do small-o notation (yet) and we won't test on anything past Theorem 7.21.
Homework 2 Due Wednesday, 3/19, in class	Redo problems from Homework 1, if you wish.  You can get full credit.  Due Wednesday, 3/19 1.  Let FINITETM = {<M> | M is a TM with a finite language}       a.  Prove that FINITETM is not decidable       b.  is FINITETM recognizable? 2.  What's the difference between ATM-complement and {<M, w> | M is a TM, and M does not accept w}? 3.  Prove that {<M, w> | M is a TM, and M does not accept w}is not recognizable. 4.  A language is said to be in co-NP if it's complement is in NP.         a.  Prove that P is a subset of co-NP       b.  Show that if co-NP contains an NP-complete problem, then NP = co-NP.       c.  We mentioned in class that PRIMES is in P.  Use this fact to show that FACTOR is in both NP and co-NP.  (The FACTOR problem has as input some positive integers n and b, and the problem is to decide if n has a factor less than b, aside from '1'.) Also, do problems 5.9, 5.13, 5.17 and 7.15 from the text.
Homework 3
Homework 4 Due at the Final	1.  Show that 2COL = {<G> | G is a graph that is 2-colorable} is in NL.  You may assume without proof, as Problem 8.20 asserts, that a graph is bipartite (which is equivalent to 2-colorable) if and only if it has no odd cycles. 2.  Notice that a graph becomes bipartite if you add a vertex to the middle of every edge (regardless of whether it was bipartite or not to start with).  Use this fact to prove that 2COL is NL-Complete.
Homework 5 Due at the Final	3.  How much space do you need to decide PI = {<x, p> | x is a positive integer and p is the number of primes less than or equal to x}?  Here, I just want you to describe your best algorithm, using as little space as you can, but analyzing correctly the amount of space you use. 4.  We saw in class how to prove that VERTEX-COVER was NP-Complete, by reduction from 3SAT (page 261 in the text). Show that this reduction can be done by a log-space transducer. 5.  Suppose that G is a graph with positive integer weights on the edges, and b is some positive integer. Two players, Maker and Breaker, play a game as follows:  Maker (Player 1) selects an edge, then Breaker (player 2) selects an edge, then Maker, etc..., such that each edge that is selected has no vertex in common with any previously selected edge.  Maker tries to force the sum of the edges to exceed b, and Breaker tries to prevent this. The game ends when either the sum exceeds b, in which case Maker wins, or no further edge may be selected, in which case Breaker wins. Let MAKER-BREAKER = {<G, b> | G is a weighted graph and b is a bound, and Maker has a winning strategy, as described above}.  Show that MAKER-BREAKER is PSPACE-Complete. Here are three graphs, and who wins on each graph with b = 2. And here is a hint about what gadgets might be useful: 6.  Let SUM = {<a, b, c> | a, b and c are binary numbers, with a + b = c}.  Show that SUM is in L.  Please be careful to give all the details of your algorithm, especially your analysis of the amount of space that you use. 7.