CSC 8510: Homework

Policy: Homework will not be graded, but the quizzes and examination will be mainly based on your homework. Books or notes will not be allowed during the quiz or exam.

 


[For the quiz of January 24/25]

Material covered: Slides 0.a – 1.1.g

Questions:  

 


[For the quiz of January 31/February 1]

Material covered: Slides 1.1.g – 2.1.b

Questions:  

 


[For the quiz of February 7/8]

Material covered: Slides 2.1.c – 3.1.h

Questions:  

 


[For the quiz of February 14/15]

Material covered: Slides 3.1.i  3.2.g

Questions

 

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

 

 


[For the quiz of February 21/22]

Material covered: Slides 3.2.h  4.1.d

Questions

 

 


 

[For the quiz of February 28/29]

Material covered: Slides 4.2.a  5.3.b

Questions

 

 

 

 


 

[For the quiz of March 13/14]

Material covered: Slides 5.3.c  7.1.p

Questions

 

·       Definitions 7.1, 7.7, 7.9.

·       The work of the machines M1M2M3 (Slides 7.1.k, 7.1.l, 7.1.m) and an analysis of their time complexity.

·       How do the two classes TIME(n) and TIME(2n) compare (are they equal, or one (and which one) is a proper subset of the other, or neither)?  Briefly justify your answer.

·       How do the two classes TIME(n2) and TIME(2n) compare (are they equal, or one (and which one) is a proper subset of the other, or neither)? Briefly justify your answer.

·       Explain why every regular language is in TIME(n).

·       Theorems (with proof ideas) 7.8, 7.11.

 

 


 

[For the quiz of March 20/21]

Material covered: Slides 7.2.a-7.3.i

Questions

 

 


[For the quiz of March 27/April 4]

Material covered: Slides 7.3.j – 7.4.k (the proofs of Theorems 7.37 and 7.42 omitted: simply remember that both SAT and 3SAT are NP-complete).

Questions

 

 

 

 

FINAL examination dates:  May 8/9.  Usual time and place.