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-11] – [Synopsis/Syllabus:] Martin Ziegler19cs422 [2019-06-09] (current) – Martin Ziegler
Line 8: Line 8:
   * Location: N1 #112   * Location: N1 #112
   * TA: Ivan Koswara   * TA: Ivan Koswara
-  * Office hours: Mondays 3pm~4pm in E3-1 #3431+  * Office hours: Mondays 15:00 to 16:00 in E3-1 #2450
   * Language: English   * Language: English
-  * 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 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 ===== 
 Regularly recalling, applying, and extending the definitions, theorems, and proofs from the lecture is essential for comprehension and successful study. Therefore consider it as a courtesy that we will create homework assignments and publish them on this web page. Regularly recalling, applying, and extending the definitions, theorems, and proofs from the lecture is essential for comprehension and successful study. Therefore consider it as a courtesy that we will create homework assignments and publish them on this web page.
  
-Homework submissions are to be submitted **on the deadline day, by 1.10pm** (before class, with a grace period).+Homework submissions are to be submitted **on the deadline day, by 13:10** (before class, with a grace period).
  
-If you're late, you can submit after class, or by going to building E3-1 room #3431 (if it's Monday) or #3413 (if it's Wednesday), up to 4.00pm, with 50% penalty. After that we will not accept late submissions for the homework.+If you're late, you can submit after class, or by going to building E3-1 room #2450 (if it's Monday) or #3413 (if it's Wednesday), up to 16:00, with 50% penalty. After that we will not accept late submissions for the homework.
  
 If you are unable to come to class for whatever reason, you may submit it earlier by going to E3-1 room #3413, or you may ask a friend to submit it for you during class. If you are unable to come to class for whatever reason, you may submit it earlier by going to E3-1 room #3413, or you may ask a friend to submit it for you during class.
Line 83: Line 86:
  
   - {{ :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: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. \\
Line 96: Line 104:
   * Sipser: Introduction to the Theory of Computation, PWS Publishing (1997).   * Sipser: Introduction to the Theory of Computation, PWS Publishing (1997).
   * Enderton: Computability Theory (2011).   * Enderton: Computability Theory (2011).
-You are expected to buy some of these (or similar) books — latest for the midterm exam: leaving you enough time to thoroughly browse and compare them in the library, first.+You are expected to buy some of these (or similar) books — latest for the midterm exam: leaving you enough time to first thoroughly browse and compare them in the library.