CSC 4170-001: Homework Assignments


Policy: Homework will not be graded. Using somebody's help when doing homework is not forbidden. However, the quiz problems will usually (90%) come from the homework assignments. Books or notes will not be allowed during the quiz. 


August 29

Material covered: Slides 0.a - 0.h


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

Exercise 0.2

Exercise 0.3

Exercise 0.4

Exercise 0.5

September 5

Material covered: Slides 1.1.a - 1.2.k


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 12

Material covered: Slides 1.2.l - 1.3.j


Exercise 1.16  

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

Exercise 1.20

Exercise 1.19 

September 19

Material covered: Slides 1.3.k - 1.4.e


Exercise 1.21

Exercise 1.27

September 26

Material covered: Slides 2.1.a – 2.2.b10


October 3

Material covered: Slides 2.2.c – 3.1.e1


October 17

Material covered: Slides 3.1.e1 – 3.2.d  NOTE: Due to your instructor’s absence, there will be no class on Thursday October 19.



October 24

Material covered: Nothing new. NOTE: Even though no new material was added last week, there will still be a quiz on October 24 as usual.

Assignmtent: Nothing new.

October 31

Material covered: Slides 3.2.e-3.3.c


State Theorem 3.16 and provide a very brief (a few lines perhaps) yet meaningful and to-the-point explanation of its proof idea. Do not go into (m)any technical details.

November 7

Material covered: Slides 3.3.d – 4.1.c


 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).

Exercises 3.7, 4.1(a,b,c) 4.3.

Prove that if a language is decidable, then so is its complement.  

Prove that if two languages are decidable, then so is their intersection. 


November 14

Material covered: Slides 4.1.d – 4.2.d


Exercise 4.3. Hint: similar to Theorem 4.4.

What language does the universal Turing machine recognize? (Do not just give its name, define the language.) The answer is found on Slide 4.2.a.

How does the universal Turing machine work? (I.e. what algorithm does it follow?) The answer, again, is found on Slide 4.2.a.

November 21

Material covered: Slides 5.1.a, 5.3.a-5.3.d, 6.3.a-6.3.b


·       Prove that the halting problem is undecidable (Theorem 5.1)

·       Prove that the halting problem is undecidable (Theorem 5.1)

·       Prove that the halting problem is recognizable (Hint: Similar to the theorem on Slide 4.2.a).

·       The definitions of mapping reduction and mapping reducibility.

·       Prove that if a language A is mapping reducible to a language B and B is decidable, then A is decidable (Theorem 5.22).

·       Prove that if a language A is mapping reducible to a language B and B is recognizable, then A is recognizable (hint: very similar to the proof of Theorem 5.22).

·       In each case below, find (precisely define) a particular function that is a mapping reduction of A to B. Both A and B are languages over the alphabet {0,1}.


·       When do we say that a language A is decidable relative (i.e. Turing reducible)  to a language B?

·       Prove that if a language A is Turing reducible to a language B and B is decidable, then A is decidable (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 28

Material covered: Slides 6.2.a-6.2.d



December 7

(yes, the quiz has moved from Dec.5 to Dec.7)

Material covered: Slides 7.1.a-8.2.a  (Slides 7.3.g, 7.3.h and 8.0.c omitted)




NOTE: Go to the Lecture Notes page to find the newly added notes for Chapter 8 and the updated notes for Section 7.3.  


·       Definitions 7.1, 7.7, 7.9, 7.12.

·       Describe a O(n2) time TM which decides the language {0n1n | n0} (Slide 7.1.b).

·       Answer the questions of Slide 7.1.j.

·       Theorems 7.8, 7.11 withOUT proofs.

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

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

·       What does Savitch’s theorem say? (Slide 8.1.a).

·       Define the class PSPACE (Slide 8.2.a).