CSC 4170: Homework Assignments


Policy: Homework will not be graded. Using somebody's help when doing homework is not forbidden. However, the quiz problems will usually come from the homework assignments (one question from the latest two assignments, and one from an earlier assignment). Books or notes will not be allowed during the quiz. 


September 2

Material covered: Slides 0.a - 1.1.b


·        Exercise 0.1 [Note: "N" stands for natural numbers. See page 4]

·        Exercise 0.2

·        Exercise 0.3

·        Exercise 0.4

·        Exercise 0.5

·        Exercise 1.1

September 4

Material covered: Slides 1.1.c - 1.2.b


·        Exercise 1.2  

·        Exercise 1.3

·        Exercise 1.4

·        Exercise 1.5(a,b,c,g,h)

·        Exercise 1.6(a,b,d,e,g,i,k,m,n)

·        Exercise 1.7(a,b,c,d,g)

September 9

Material covered: Slides 1.2.c - 1.2.m


·        Exercise 1.16  

September 11

Material covered: Slides 1.3.a - 1.3.e


·        Exercise 1.18 (a,b,c,d,e,g,k,l,m,n)

·        Exercise 1.20

September 16

Material covered: Slides 1.3.f - 1.3.x


·        Exercise 1.19 

·        Exercise 1.21

September 18

Material covered: Slides 1.4.a - 1.4.e


September 23

Material covered: Nothing new

Assignment: Nothing new

September 25

Material covered: Slides 2.1.a – 2.1.i


September 30

Material covered: Slides 2.1.i – 2.2.e


October 2

Material covered: Slides 2.3.a – 3.1.c1


October 7

Material covered: Slides 3.1.c2 – 3.1.j


·        Design a fragment of a TM that, from a state “Go to the beginning”, goes to the beginning of the tape and state “Done” (Slide 3.1.j).


October 9

Material covered: Slides 3.1.k – 3.2.d


·         Design a fragment of a TM that, beginning from the current cell, shifts the contents of the tape right, typing in the current cell a 0 (Slide 3.1.k). Assume the tape alphabet is {0,1,-}, and that neither 0 nor 1 ever occurs after the leftmost blank on the tape.

·        Design a fragment of a 2-tape TM that swaps the contents of the tapes, from the position where the heads are at the beginning and there are no blanks followed by non-blank symbols (Slide 3.2.c). Tape alphabet: {0,1,-}.

·        State Theorem 3.13 and provide a very brief (half-page or so) yet meaningful and to-the-point explanation of its proof idea. Do not go into (m)any technical details.


October 21

Material covered: Slides 3.2.e – 3.2.i


·        State Theorem 3.16 and provide a very brief (half-page or so) yet meaningful and to-the-point explanation of its proof idea. Do not go into (m)any technical details.

·        Exercise 3.6.

·        For a bit string w, NOT(w) means w with all bits changed. For example, NOT(11010)=00101. Construct a Turing machine with an output that computes function NOT.


October 23

Material covered: Slides 3.2.j – 3.2.k


·        The definitions of computing, computability and graph of a function (Slide 3.2.j).

·        Proof idea for the theorem on Slide 3.2.k.


October 28

Material covered: Slides 3.3.a – 3.3.f


·        What is encoding? Give examples.

·        What is the Church-Turing thesis all about? (don't just write something like "algorithms = TM"; write a couple of sentences showing that you understand what you are writing).

·        Exercise 3.7.


October 30

Material covered: Slides 4.1.a – 4.1.f


·        Exercises 4.1, 4.2, 4.3.

November 4

Material covered: Slides 4.2.a – 4.2.d


November 6

Material covered: Slides 5.1.a – 5.3.c


November 11

Material covered: Slides 5.3.d, 6.3.a and 6.3.b (Section 6.2 will be covered later)


·       The definition of Turing reducibility.

·       Proof of Theorem 6.21.

·       Show that any language L is Turing reducible to its complement (Hint: A straightforward generalization of the example on Slide 6.3.a).


November 13

Material covered: Slides  6.2.a – 6.2.c


November 18

Material covered: Slides 6.2.d - 7.1.b 


·  Prove that Th(N,+,´) is unrecognizable, assuming that the undecidability of this problem is already known (the Corollary on slide 6.2.d).

·  Definition 7.1.


November 20

Material covered: Slides 7.1.b - 7.1.m (slides 7.1.c-7.1.g omitted)


November 25

Material covered: Slides 7.1.n – 7.2.d


December 2

Material covered: Slides 7.2.e – 7.3.f


·       Show that the RELPRIME problem is in P (Slide 7.2.f).

·       Define the class NP (Slide 7.3.d).

·       Show that the CLIQUE problem is in NP (Slide 7.3.e).

·       Show that the SUBSET-SUM problem is in NP (Slide 7.3.f)

·       Show that the COMPOSITES problem is in NP (as in the previous two cases, you will need to do this by constructing a polynomial time nondeterministic TM).

December 4

Material covered: Slide 7.3.g, and a brief survey of space complexity


·       True or false? (1) Some languages from EXPTIME are undecidable. (2) Every regular language is in P. (3) The complement of a recognizable language is always recognizable. (4) Every context-free language is generated by some unambiguous context-free grammar. (5) Every regular language is context-free. (6) Every regular language is in NP. (7) The complement of a decidable language is always decidable. (8) Turing reducibility implies mapping reducibility. (9) Every language from NP is decidable. (10) The complement of any language from P is also in P. (11) Every language that is decided in polynomial time by some multitape TM is also decided in polynomial time by some single-tape TM. (12)  Every context-free language is in P. (13) PATH is in NP.

·       Prove that the halting problem HALTTM is undecidable.