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), Fri 10-11 AM (Soda 310)
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).

  • Homework 6 - PDF - Released on Oct 7, Due Oct 17 (Monday).

  • Homework 7 - PDF - Released on Oct 18, Due Oct 24 (Monday).

  • Homework 8 - PDF - Released on Oct 23, Due Oct 31 (Monday).

  • Homework 9 - PDF - Released on Nov 8, Due Nov 14 (Monday).

  • Homework 10 - PDF - Released on Nov 16, Not for Submission.

  • Homework 11 - PDF - Released on Nov 28. Not for Submission.

Useful Resources:

Theory of Computation Online Lectures

Mathematics and Computation - Avi Wigderson

Finite State Machine Designer

Course Website - Spring 2022

Course Website - Spring 2021 (Prof. Alistair Sinclair)