CSC 8510-001: Homework Assignments

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

 


[January 16]

Material covered: Slides 0.a-1.2.c

Assignment:


[January 23]

Material covered: Slides 1.2.d-1.4.c

Assignment:


[January 30]

Material covered: Slides 2.1.a-3.1.g

Assignment:

 

 


[February 6]

Material covered: Slides 3.1.h-3.2.g

Assignment:

 


[February 13]

Material covered: Slides 3.2.h-4.2.a

Assignment:

[February 20]

Material covered: Slides 4.2.a-5.3.d

Assignment:



[February 27]

Material covered: Slides 7.1.a-7.1.p

Assignment:





[March 13]

Material covered: Slides 7.2.a-7.3.g

Assignment:




[March 27]

Material covered: Slides 7.3.h-7.4.h

Assignment:





[April 10]

Material covered: Slides 7.4.i-7.4.k, 7.5.a-7.5.k

Assignment:




[April 17]

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

Assignment:


[April 24]

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

Examination on May 1; comprehensive, including the present material. 

Assignment:

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.     PATH is in EXPTIME.