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
Last revisionBoth sides next revision
19cs422 [2019-03-18] – Ivan Koswara19cs422 [2019-06-03] – 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+  * 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 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. \\