CS21: Decidability and Tractability
course information and tentative schedule
Catalog description: This course introduces the formal foundations of computer science, the fundamental limits of computation, and the limits of efficient computation. Topics will include automata and Turing machines, decidability and undecidability, reductions between computational problems, and the theory of NP-completeness.
Course Information:
Copyright By PowCoder代写 加微信 powcoder
• Instructor:
Andrei Diaconu
• Lectures: Mondays, Wednesdays, and Fridays 1:00 – 1:55
• Office hours: TBD (2 on Monday nights, 2 on Tuesday afternoons, 5 on Tuesday nights)
• Text: Introduction to the Theory of Computation – 3rd Edition by M. Sipser (required). Earlier editions should also suffice; the main difference is that they do not have solutions to selected problems.
• Webpage: http://www.cs.caltech.edu/~umans/cs21/
Homework: The homework is extremely important – for this material, the best way to learn is by doing. I strongly encourage you to work in groups of two or three on the homework. However, you must each turn in your own write-up and note with whom you worked. The rules on homework are:
• There are 7 problem sets. They are released at the end of the Wednesday lecture, and they are due at the beginning of class (1pm) the following Wednesday.
• The quality (clarity, conciseness, neatness) of your write-up counts.
• You may elect to take a two-day extension (until 5pm Friday) on one problem set without penalty. Other problem sets turned in late, but before 5pm Friday, receive half credit. You don’t need to notify me or the TAs if you are taking the free extension.
• We will be using Gradescope for turning in assignments, and online grading.
Exams: There will be a midterm and final exam. They will be indistinguishable from the problem sets, except that they will be cumulative, and you may not work with others on the exams. The homework rules apply to exams as well. There are no extensions for the exams, and no partial credit for exams that are turned in late.
Honor code: For homework and exams, you may consult only the following material: (1) lecture slides and problem sets posted on the class webpage, (2) solution sets for problem sets you have already turned in, (3) course notes you or others took during lecture, and (4) the required text (Sipser). I am well aware that there is material from past iterations of this course readily available (online and elsewhere). You may not seek out, study from, or otherwise consult this material during the term, starting now (January 3, 2024). Please feel free to ask me for clarification if any of these guidelines are unclear.
Collaboration policy: Collaboration on problem sets is encouraged, and you may work together in small groups to figure out a solution, including working out details of parts that are challenging or may require a clever trick. You must however turn in your own writeup that may draw on ideas from your group, even in detail, but you may not use or look at the completed work of others. The writeup should note with whom you
worked. You are individually responsible for learning and understanding the course material in preparation for the exams, and this is not likely to happen if you rely too heavily on your collaborators!
Reading: The webpage will list reading in Sipser (3rd edition) that parallels the lectures (when applicable). This is mainly for reference; the lectures are designed to be self-contained.
Feedback: If you have any comments or concerns on issues like: the pace of the lectures, the difficulty of the material, time spent on problem sets, or anything else, please let me know! You can tell me or the TAs directly, or you can talk to the course ombudsperson (we will select someone for this role after the first couple of lectures).
Evaluation and Grades: Your grade will be based on the following (weighted) components: Homework 60%; Participation 10%; Midterm 15%; Final 15%.
Each of the 7 problem sets contributes equally to the Homework portion of the grade (i.e., each problem set is worth ≈ 8.57% of your overall grade).
If you earn 90% of the available (weighted) points you are guaranteed at least an A of some form, 80% guarantees at least a B of some form, 70% guarantees at least a C of some form, etc… If you are taking the course pass/fail, you need to earn a C- or higher to pass.
Tentative lecture schedule:
10 Jan. 26
11 Jan. 29
12 Jan. 31
17 Feb. 12
18 Feb. 14
19 Feb. 16
20 Feb. 21
21 Feb. 23
22 Feb. 26
23 Feb. 28
Introduction; Finite Automata and Regular Expressions Finite Automata and Regular Expressions
Finite Automata and Regular Expressions
and Context Free Grammars and Context Free Grammars
NO CLASS: MLK Day (Institute Holiday)
and Context Free Grammars Turing Machines, undecidability, and reductions
Turing Machines, undecidability, and reductions
Turing Machines, undecidability, and reductions
Turing Machines, undecidability, and reductions
Turing Machines, undecidability, and reductions
Turing Machines, undecidability, and reductions
Turing Machines, undecidability, and reductions
G ̈odel Incompleteness Theorem
Introduction to Complexity
Complexity Classes: P, EXP, and NP
Complexity Classes: P, EXP, and NP
NP-completeness and reductions
NP-completeness and reductions
NO CLASS: President’s Day (Institute Holiday)
[drop day] NP-completeness and reductions NP-completeness and reductions
NP-completeness and reductions
More complexity classes
More complexity classes
More complexity classes
Topics: randomized computation
Topics: quantum computation
Assignments Reading
Final Final due
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com