Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revisionLast revisionBoth sides next revision | ||
19cs422 [2019-03-04] – [Synopsis/Syllabus:] Martin Ziegler | 19cs422 [2019-06-03] – Martin Ziegler | ||
---|---|---|---|
Line 8: | Line 8: | ||
* Location: N1 #112 | * Location: N1 #112 | ||
* TA: Ivan Koswara | * TA: Ivan Koswara | ||
+ | * 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/ | ===== Synopsis/ | ||
Line 25: | Line 26: | ||
* diagonalization / undecidable Halting Problem | * diagonalization / undecidable Halting Problem | ||
- | II. Basic Computability Theory | + | II. Basic Computability Theory |
* Un-/ | * Un-/ | ||
* 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 |
* Ackermann' | * Ackermann' | ||
- | III. Advanced Computability | + | III. Advanced Computability |
* WHILE programs | * WHILE programs | ||
* UTM Theorem | * UTM Theorem | ||
Line 39: | 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/ | ||
+ | * Arithmetic Hierarchy | ||
* (Post' | * (Post' | ||
- | IV. Computational Complexity | + | IV. Computational Complexity |
* 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, | * Example problems: Hamiltonian Circuit, Vertex Cover, Independent Set, Clique, Boolean Satisfiability, | ||
+ | * Boolean formulas ({{ : | ||
- | V. Structural Complexity / NPc | + | V. Structural Complexity / NPc ({{19cs422e.ppt|ppt}}, |
* polynomial-time reductions | * polynomial-time reductions | ||
* equivalent problems Clique, Independent Set, Boolean Satisfiability, | * equivalent problems Clique, Independent Set, Boolean Satisfiability, | ||
Line 55: | Line 59: | ||
* Ladner' | * Ladner' | ||
- | VI. PSPACE and Polynomial Hierarchy | + | VI. PSPACE and Polynomial Hierarchy |
* PSPACE-completeness | * PSPACE-completeness | ||
* QBF, 3QBF, GRAPH | * QBF, 3QBF, GRAPH | ||
Line 71: | Line 75: | ||
===== Homework/ | ===== Homework/ | ||
- | Regularly recalling, applying, and extending the definitions, | + | Regularly recalling, applying, and extending the definitions, |
+ | 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. | ||
+ | |||
+ | - {{ : | ||
+ | - {{ : | ||
+ | - {{ : | ||
+ | - {{ : | ||
+ | - {{ : | ||
+ | - {{ : | ||
===== Academic Honesty ===== | ===== Academic Honesty ===== | ||
Copied solutions receive 0 points and personal interrogation during office/ | Copied solutions receive 0 points and personal interrogation during office/ | ||
Line 86: | Line 104: | ||
* Sipser: Introduction to the Theory of Computation, | * Sipser: Introduction to the Theory of Computation, | ||
* 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. |