CSC 8510: Homework Assignments

Policy: Homework will not be graded, but the weekly quizzes will be mainly based on your homework. Books or notes will not be allowed during the quiz. Using somebody's help is OK doing homework, but not when writing the quiz.


A quiz will typically have two questions: one from the latest homework assignment, and one from some earlier homework assignment. Occasionally, however, questions may be asked that are not exactly on the list of homework problems yet are similar or closely related to the latter; if you have done homework with understanding (as opposed to memorization), answering such questions  should not be a problem.

[January 19]

Material covered: Slides 0.a-1.2.f


[January 26]

Material covered: Slides 1.2.g-2.1.e


[February 2]

Material covered: Slides 2.1.f-3.1.k


·        Complete the following definitions: (1) A Turing machine M is a decider iff ...     (2) A Turing machine M recognizes a language LÍS* iff ...  (3) A Turing machine M decides a language LÍS* iff ...

·        Design a fragment of a TM that, from a state “Beg?”, goes to a state “Yes” or  “No”, depending on whether you are at the beginning of the tape or not, without corrupting the contents of the tape (Slide 3.1.i).

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

·        Design a fragment of a TM that, beginning from the current cell, shifts the contents of the tape to the 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.

·        Construct a Turing machine (provide a full diagram) for the language {#·n>·n>m(note: this is similar to but NOT the same as the example on slide 3.1.f).

[February 16]

Material covered: Slides 3.1.l-3.3.c


·        Theorem 3.16 with a brief description of its proof idea (a few lines would suffice, showing your understanding of the essence of the proof; do not go into technical details).

[February 23]

Material covered: Slides 3.3.d-4.2.b.1


[March 2]

Material covered: Slides 4.2.c -5.3.d




[March 16]

Material covered: Slides 7.1.a – 7.1.n




[March 23]

Material covered: Slides 7.1.o – 7.3.i




[March 30]

Material covered: Slides 7.3.g – 7.4.i



[April 6]

Material covered: Slides 7.3.j (again), 7.4.j,  7.4.k, 7.4.w, 7.5.a-7.5.k


[April 20]

Material covered: Slides 7.5.l-7.5.o, 8.0.a-8.1.a, 8.2.a, 8.3.a-8.3.b, 8.3.e-8.3.f


[April 27]

Material covered: Slides 8.3.d, 8.3.g-8.3.h, 8.4.a-8.4.d, 8.5.a-8.5.d, 8.6.d


·       Show that TQBF is in PSPACE (Slide 8.3.d)

·       What do we know and do not know about the relations (equal? subset?) between L, NL, coNL, P, NP, PSPACE?


1.     The complement of any language in P is also in P.

2.     The complement of any language in NL is also in NL.

3.     The complement of any language in NP is also in NP.

4.     The complement of any language in PSPACE is also in PSPACE.

5.     Any language that is both in NP and coNP is decidable in polynomial time. 

6.     Every regular language is decidable in linear time. 

7.     No EXPSPACE-complete language is in P.

8.     PATH is in EXPTIME.