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-04] – 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 26: Line 26:
   * diagonalization / undecidable Halting Problem   * diagonalization / undecidable Halting Problem
  
-II. Basic Computability Theory+II. Basic Computability Theory ({{19cs422b.ppt|ppt}}, {{19cs422b.pdf|pdf}}):
   * 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 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 #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.
 +
 +**You must print and sign the Honor Code** and submit it along with your first homework submission. As long as your Honor Code is missing, we will not grade your homework submissions.
 +
 +  - {{ :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 87: 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.