Join Lecture (Tues/Thurs at 3:30pm)

Since this is a course in active re-development, I expect to change the flow and pacing of topics as the semester progresses. The past, and my best guess of the future, is reflected below.


While classes are online, lectures will be live-streamed via zoom. Please join us!

View as or ; ; readings can be or as a whole, or clicked on individually to toggle visibility.

13 Jan
Courses begin
14 Jan
welcome TCS Chapter 0 and six habits and slides(pdf) and slides(pptx) and slides(post) and video
16 Jan
Simplifying TCS Chapter 1 and slides(pdf) and slides(pptx) and slides(post) and video
exercise0_1
21 Jan
Counting TCS Chapter 2 and slides(pdf) and slides(pptx) and slides(post) and video
exercise0_2
23 Jan
Infinities slides(pdf) and slides(pptx) and slides(post) and video
27 Jan
Add deadline
28 Jan
Boolean Circuits TCS Chapter 3 and slides(pdf) and slides(pptx) and slides(post) and video
quiz01
30 Jan
Boolean Programs TCS Chapter 3 and slides(pdf) and slides(pptx) and video
exercise1_1
exercise1_2
exercise1_3
3 Feb
exercise0_3
4 Feb
Syntactic Sugar TCS Chapter 4 and slides(pdf) and slides(pptx) and slides(post) and video
exercise1_4
exercise1_5
quiz02
6 Feb
Universality TCS Chapter 5 and slides(pdf) and slides(pptx) and slides(post) and video
exercise2_1
11 Feb
Evaluation TCS Chapter 5 and slides(pdf) and slides(pptx) and slides(post) and video
exercise2_2
exercise2_3
exercise2_4
exercise2_5
13 Feb
Complexity TCS Chapter 5 and slides(pdf) and slides(pptx) and slides(post) and video
exercise3_1
quiz03
18 Feb
Review Exam1 Practice and slides(pdf) and slides(pptx) and slides(post) and video
exercise3_2
exercise3_3
exercise3_4
exercise3_5
exercise3_6
19 Feb
20 Feb
24 Feb
Drop deadline
25 Feb
Automata TCS Chapter 9 and slides(pdf) and slides(pptx) and slides(post) and video
27 Feb
Regular Expressions and Closure TCS Chapter 9 and slides(pdf) and slides(pptx) and slides(post) and video
3 Mar
Non-determinism slides(pdf) and slides(pptx) and slides(post) and video
quiz04
4 Mar
exercise4_1
5 Mar
FSA Equals Regex slides(pdf) and slides(pptx) and video
6 Mar
exercise4_2
exercise4_3
exercise4_4
exercise4_5
16 Mar
Withdraw deadline
19 Mar
Going online and Summary slides(pdf) and slides(pptx) and video
24 Mar
Turing Machines slides(pdf) and slides(pptx) and video
26 Mar
Church Turing Thesis slides(pdf) and slides(pptx) and video
quiz05
31 Mar
Turing Universality and uncomputability slides(pptx) and slides(pdf) and video
exercise5_1
exercise5_2
2 Apr
Reductions slides(pptx) and slides(pdf) and video
6 Apr
quiz06
7 Apr
Rice's Theorem and Complexity Classes slides(pptx) and slides(pdf) and video
9 Apr
Polynomial Time Reductions slides(pptx) and slides(pdf) and video
12 Apr
exercise6_1
exercise6_2
exercise6_3
exercise6_4
exercise6_5
14 Apr
NP-Completeness slides(pptx) and slides(pdf) and video
16 Apr
More NP-Completeness slides(pptx) and slides(pdf) and video
quiz07
17 Apr
Exam_2
21 Apr
Approximation
exercise7_1
exercise7_2
exercise7_3
23 Apr
Conclusion slides(pptx) and slides(pdf) and video1 and video2
26 Apr
quiz08
28 Apr
Courses end
lecture slides(pptx) and slides(pdf) and ACM code of ethics
exercise8_1
exercise8_2
exercise8_3
exercise8_4
4 May
Final Exam
Exam_3

To subscribe to the above calendar, add http://www.cs.virginia.edu/~njb2b/cstheory/s2020/cal.ics to your calender application of choice.