CS 172 Computability and Complexity

Fall 2022

Course Staff

Instructor: Avishay Tal (atal "at" berkeley.edu)
Lectures: Tue/Thu 2:00-3:30 PM, Soda 306
Office Hours: Tue 3:30-4:30 PM, Soda 306. Fri 10-11 on Zoom (link on Ed)

GSI: Siqi Liu (sliu18 "at" berkeley.edu)
Discussion Sections: Wed 5-6 PM (Soda 306), Wed 6-7 PM (Soda 306)
Office Hours: Tue 5-6 PM (Soda 326) Thu 5-6 on Zoom (link on Ed)

Tutor: Clara Mohri (cmohri "at" berkeley.edu)
HW Party/Office Hours: Wed 10-11 AM (Soda 310), Wed 2-3 PM (Wozniak Lounge, Soda 430)

Reader: Dasheng Bi (dbi "at" berkeley.edu)

Ed Discussions

https://edstem.org/us/courses/26774/discussion/

Gradescope

https://www.gradescope.com/courses/427330

Homeworks (link to HW sources)

  • Homework 1 - PDF - Released on Aug 26, Due Sep 2

  • Homework 2 - PDF - Released on Sep 3, Due Sep 9

  • Homework 3 - PDF - Released on Sep 10, Due Sep 16

  • Homework 4 - PDF - Released on Sep 17, Due Sep 24 (Saturday)

  • Homework 5 - PDF - Released on Oct 1, Due Oct 8 (Saturday).

Useful Resources:

Theory of Computation Online Lectures

Mathematics and Computation - Avi Wigderson

Finite State Machine Designer