Class 10: Circuit Complexity and Universal Circuits
Slides from class: class10.pdf (video is available for students in collab)
Quiz 5 is posted in GradeScope, and is due Wednesday, 9:59pm.
The Midterm Exam will be in class on Thursday, 2 March. See Preparing for Exam 1 for suggestions on how to prepare for the exam.
Preparing for Exam 1
Exam 1 will be in class on Thursday, 2 March. It will cover material from Classes 1 – 9, Problem Sets 1 – 4 (including the provided comments), Quizzes 1 – 4, and Chapter 1 – 5 of the TCS Book. Nearly everything on the exam will have been covered in at least three of these places (e.g., in class, on a problem set, and in the textbook; or in multiple classes, the textbook, and a quiz).Class 9: Circuit Size Hierarchy
Slides from class: class9.pdf (video is available for students in collab)
Problem Set 4 is due on Monday, 20 February (9:59pm): https://overleaf.com/read/hsxfrxnsvyfw (there is no Jupyter notebook part of this problem set).
The Midterm Exam will be in class on Thursday, 2 March.
Class 8: Syntactic Sugar, Complexity of Functions
Slides from class: class8.pdf (video is available for students in collab) Quiz 4 is in GradeScope (after noon today) and due Wednesday, 9:59pm. As posted in discord, the collaboration policy for the quizzes has changed (including for this quiz): From now on, you are permitted to use resources for quizzes, but not to discuss the problems with other people. You may use your notes, the course textbook, posted class slides/videos, and any other materials you want while you take the quiz.Problem Set 4 Posted
Problem Set 4 is now posted and due on Monday, 20 February (9:59pm).
This problem set focuses on understanding the asymptotic notations, syntactic sugar (Chapter 4), and the circuit complexity and the size hierarchy theorem (Chapter 5 of TCS).
The latex template for Problem Set 4 is here: https://overleaf.com/read/hsxfrxnsvyfw (there is no Jupyter notebook part of this problem set).
The problems PDF is: ps4.pdf.
Class 7: Universal Circuits
Slides from class: class7.pdf (video is available for students in collab) Problem Set 3 (Overleaf, Jupyter) is due Monday, 13 February, 9:59pm. As was pointed out to me by an intrepid student after class, what I said about { OR, NOT } being not universal since we included AND in our AON Circuits is badly wrong! One easy way to see this is we know we can convert between { AND, NOT } and { OR, NOT } using De Morgan’s laws, so we can construct AND from { OR, NOT }.Class 6: Modeling Boolean Circuits
Slides from class: class6.pdf (video is available for students in collab)
Quiz 3 is in GradeScope and due Wednesday, 9:59pm.
Problem Set 3 (Overleaf, Jupyter) is due Monday, 13 February, 9:59pm.
Problem Set 3 Posted
Problem Set 3 is now posted and due on Monday, 13 February (9:59pm).
This problem set focuses on understanding finite computation in the Boolean circuit and programming models (Chapter 3 of TCS), and understanding how we prove Boolean circuits can compute every finite function (Chapter 4 of TCS).
The latex template for Problem Set 3 is here: https://www.overleaf.com/read/kvfjnywhnxrw
The problems PDF is: ps3.pdf.
The Jupyter notebook for PS3 is ps3.ipynb.
On Mappings
As discussed in Class 5, there was a problem on Quiz 2 that both the professors got wrong probably more than once. Although it was meant to be a fairly straightforward multiple choice question, it illustrates how tricky it is to think about the subtleties of simple definitions on binary relations and the importance of precise definitions. The question, as asked on Quiz 2 is below: Question 2: Notions of RelationsClass 5: Defining Computation
Slides from class: class5.pdf (video is available for students in collab)
Problem Set 2 is due Monday, 9:59pm.