Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
19cs422 [2019-03-27] – [Synopsis/Syllabus:] Ivan Koswara19cs422 [2019-06-09] (current) – Martin Ziegler
Line 12: Line 12:
   * Grading: Homework 30%, Attendance 10%, Midterm exam 30%, Final exam 30%   * Grading: Homework 30%, Attendance 10%, Midterm exam 30%, Final exam 30%
   * Attendance: 10 points for missing less than 5 lectures, 9 when missing 5 lectures, and so on. 14 or more missed lectures earn you no attendance points.   * Attendance: 10 points for missing less than 5 lectures, 9 when missing 5 lectures, and so on. 14 or more missed lectures earn you no attendance points.
-  * Midterm exam on Monday, April 15 at 13:00 +  * Midterm exam on Monday, April 15 from 13:00 to 15:45 in N1 #112 
-  * Final exam on Monday, June 10 at 13:00+  * Final exam on Monday, June 10 from 13:00 to 15:45 in N1 #112
  
 ===== Synopsis/Syllabus: ===== ===== Synopsis/Syllabus: =====
Line 29: Line 29:
   * Un-/Semi-Decidability and Enumerability   * Un-/Semi-Decidability and Enumerability
   * Reduction, degrees of undecidabiliy   * Reduction, degrees of undecidabiliy
-  * (Busy Beaver function)+  * Busy Beaver/Rado function
   * LOOP programs   * LOOP programs
-  * and their capabilities ({{ :lectures:2019:cs422:0327.pdf|pdf}})+  * and their capabilities ({{:lectures:2019:cs422:0327.pdf|pdf}})
   * Ackermann's Function   * Ackermann's Function
  
-III. Advanced Computability+III. Advanced Computability ({{19cs422c.ppt|ppt}}, {{19cs422c.pdf|pdf}}):
   * WHILE programs   * WHILE programs
   * UTM Theorem   * UTM Theorem
Line 40: Line 40:
   * SMN Theorem / Currying (Schönfinkeling)   * SMN Theorem / Currying (Schönfinkeling)
   * Recursion Theorem, Fixedpoint Theorem, QUINES   * Recursion Theorem, Fixedpoint Theorem, QUINES
 +  * Oracle WHILE Programs, Post/Friedberg/Muchnik ({{:lectures:2019:cs422:0408.pdf|pdf}})
 +  * Arithmetic Hierarchy
   * (Post's Correspondence Problem, truth of arithmetic formulae)   * (Post's Correspondence Problem, truth of arithmetic formulae)
  
-IV. Computational Complexity+IV. Computational Complexity ({{19cs422d.ppt|ppt}}, {{19cs422d.pdf|pdf}}):
   * Model of computation with (bit) cost: WHILE+   * Model of computation with (bit) cost: WHILE+
   * Complexity classes P, NP, PSPACE, EXP   * Complexity classes P, NP, PSPACE, EXP
   * and their inclusion relations   * and their inclusion relations
   * nondeterministic WHILE+ programs   * nondeterministic WHILE+ programs
-  * Example problems: Euler Circuit, Edge Cover,+  * Example problems: Euler Circuit, Edge Cover
   * Example problems: Hamiltonian Circuit, Vertex Cover, Independent Set, Clique, Boolean Satisfiability, Integer Linear Programming   * Example problems: Hamiltonian Circuit, Vertex Cover, Independent Set, Clique, Boolean Satisfiability, Integer Linear Programming
 +  * Boolean formulas ({{ :lectures:2019:cs422:0508.pptx |ppt}}, {{ :lectures:2019:cs422:0508.pdf |pdf}})
  
-V. Structural Complexity / NPc+V. Structural Complexity / NPc ({{19cs422e.ppt|ppt}}, {{19cs422e.pdf|pdf}}):
   * polynomial-time reductions   * polynomial-time reductions
   * equivalent problems Clique, Independent Set, Boolean Satisfiability, 3-Satisfiability   * equivalent problems Clique, Independent Set, Boolean Satisfiability, 3-Satisfiability
Line 56: Line 59:
   * Ladner's Theorem (without proof)   * Ladner's Theorem (without proof)
  
-VI. PSPACE and Polynomial Hierarchy+VI. PSPACE and Polynomial Hierarchy ({{19cs422f.ppt|ppt}}, {{19cs422f.pdf|pdf}}):
   * PSPACE-completeness   * PSPACE-completeness
   * QBF, 3QBF, GRAPH   * QBF, 3QBF, GRAPH
Line 63: Line 66:
   * Quantifier Alternations   * Quantifier Alternations
  
-VII. Advanced Complexity +VII. Advanced Complexity  ({{19cs422g.ppt|ppt}}, {{19cs422g.pdf|pdf}}): 
-  * Time Hierarchy+  * (Time Hierarchy)
   * complexity of cryptography: UP and one-way functions   * complexity of cryptography: UP and one-way functions
-  * counting problems, Toda's Theorem +  * (counting problems, Toda's Theorem) 
-  * LOGSPACE, Immerman-Szelepcsenyi Theorem +  * (LOGSPACE, Immerman-Szelepcsenyi Theorem) 
-  * Approximation algorithms and hardness +  * (Approximation algorithms and hardness) 
-  * randomized algorithms, probability amplification, BPP, Adleman and Sipser-Gacs-Lautemann Theorems+  * (randomized algorithms, probability amplification, BPP, Adleman and Sipser-Gacs-Lautemann Theorems)
  
 ===== Homework/Assignments =====  ===== Homework/Assignments ===== 
Line 84: Line 87:
   - {{ :lectures:2019:cs422:hw1.pdf |Homework 1}} and {{ :lectures:2019:cs422:honorcode.pdf |Honor Code}} (given 3/4, due 3/11)   - {{ :lectures:2019:cs422:hw1.pdf |Homework 1}} and {{ :lectures:2019:cs422:honorcode.pdf |Honor Code}} (given 3/4, due 3/11)
   - {{ :lectures:2019:cs422:hw2.pdf |Homework 2}} (given 3/18, due 3/25)   - {{ :lectures:2019:cs422:hw2.pdf |Homework 2}} (given 3/18, due 3/25)
 +  - {{ :lectures:2019:cs422:hw3.pdf |Homework 3}} (given 4/10, due 4/24) 
 +  - {{ :lectures:2019:cs422:hw4.pdf |Homework 4}} (given 5/2, due 5/13) 
 +  - {{ :lectures:2019:cs422:hw5.pdf |Homework 5}} (given 5/20, due 5/27) 
 +  - {{ :lectures:2019:cs422:hw6.pdf |Homework 6}} (given 5/28, due 6/5)
 ===== Academic Honesty ===== ===== Academic Honesty =====
 Copied solutions receive 0 points and personal interrogation during office/claiming hours. \\ Copied solutions receive 0 points and personal interrogation during office/claiming hours. \\