CS 4124 -- Fall 1994

• Syllabus

• Lecture Notes:
  • Introduction
  • Chapter 1
  • Chapter 2
  • Chapter 3
  • Chapter 4
  • Chapter 5
  • Chapter 6
  • Chapter 7

• Written Homework Assignments:
  1. Due 9/2. From Lewis & Papadimitriou, problems
     1.2.1, 1.2.2, 1.3.1, 1.3.2, 1.4.1, 1.4.6, 1.5.1, 1.5.2, 1.7.2.
  2. Due 9/16. From Lewis & Papadimitriou, problems
     2.1.4, 2.3.1, 2.4.6, 2.6.2[abde], 2.6.7[abc], 3.1.4, 3.1.8[abdf].
  3. Due 10/5. From Lewis & Papadimitriou, problems
     3.4.2, 3.5.4, 3.5.22[ab], 4.1.2, 4.1.6, 4.1.7, 4.2.1, 4.2.3.
  4. Due 10/12. From Lewis & Papadimitriou, problems
     4.4.3, 4.4.7b, 4.4.8, 4.6.2c.
  5. Due 10/28. From Lewis & Papadimitriou, problems
     5.2.3(choose 2), 5.2.5, 5.3.1(c), 5.3.3(a,d), 5.3.4, 5.3.7.
  6. Due 11/9. From Lewis & Papadimitriou, problems
     5.4.1, 5.6.2(a), 5.7.1(a), 6.1.3.
  7. Due 11/16. See handout.
     
  8. Due 12/5. From Lewis & Papadimitriou, problems
     7.2.2, 7.2.5, 7.3.2.

• In-class Problems:
  1. September 9: A-G do 1.9.2 and 2.2.2, H-M do 1.9.3 and 2.1.3, N-Z do 2.1.2 and 2.2.1.
  2. September 23: 3.5.1 and 3.5.2.
  3. October 7: 4.4.4.

• Reading Assignments (all from Lewis & Papadimitriou, unless otherwise indicated):
  • Read Chapter 1 by 8/26.
  • Read Chapter 2 by 9/5.
  • Read Sections 3.1--3.4 (omitting proofs) by 9/14.
  • Read Section 3.5 through page 126 (omitting proofs) by 9/23.
  • Read Sections 4.1--4.2 by 9/28.
  • Read Sections 4.3--4.4 by 10/7.
  • Read Sections 4.5--4.6 by 10/12.
  • Read Sections 5.1--5.3 by 10/24.
  • Read Sections 5.4--5.7 by 10/31 (omitting proofs).
  • Read Section 6.1 by 11/2.
  • Read Sections 6.2--6.3 by 11/11.
  • Read Sections 7.1--7.3 by 11/18 (omitting proofs).
  • Read Sections 7.4--7.5 by 11/30 (omitting proofs).