ECS 120: Undergraduate Theory of Computation
ECS 120: Undergraduate Theory of Computation
These are lectures for the course ECS 120, Undergraduate Theory of Computation, taught by David Doty. They were recorded for the Spring 2020 offering of the course, on a Monday-Wednesday-Friday lecture schedule. In the current quarter, the exact days and weeks are likely to be slightly different.
To list the videos in order, view the whole playlist, or select Sort By: Alphabetically - A to Z. (Except that it will put week 10 out of order, near the start.)
There are also playlists breaking them up by chapter in the lecture notes for the course:
Videos are labeled as follows. ECS 120 [week][day]:[topic] where [week] is a number 0,1,2,...,10 (0 is for lectures reviewing discrete math prerequisite material), [day] is a letter (a=Monday, b=Wednesday, c=Friday), and [topic] starts with a number to indicate viewing order within that lecture day (there are several short videos for each lecture day, each 5-15 minutes long). For example, ECS 120 2c:5 formal definition of NFA semantics is week 2, Friday, topic 5 for that day: formal definition of NFA semantics.
This naming convention only makes sense for Spring quarter dates; for instance in Fall 2021, the quarter starts on a Wednesday instead of a Monday, so all lectures would be shifted by one for that quarter. Refer to the current course webpage for which videos correspond to which lectures, instead of using the names on the AggieVideo website.
To list the videos in order, view the whole playlist, or select Sort By: Alphabetically - A to Z. (Except that it will put week 10 out of order, near the start.)
There are also playlists breaking them up by chapter in the lecture notes for the course:
- discrete math review (chapter 1)
- 1/2 (intro)
- 3 (DFAs)
- 4 (regex, CFG, NFA)
- 5 (closure properties)
- 6 (equivalence of regular language models)
- 7 (pumping lemma)
- 8 (Turing machines)
- 9 (polynomial time deciders, the class P)
- 10 (polynomial time verifiers and reductions, the class NP)
- 11 (undecidability)
Videos are labeled as follows. ECS 120 [week][day]:[topic] where [week] is a number 0,1,2,...,10 (0 is for lectures reviewing discrete math prerequisite material), [day] is a letter (a=Monday, b=Wednesday, c=Friday), and [topic] starts with a number to indicate viewing order within that lecture day (there are several short videos for each lecture day, each 5-15 minutes long). For example, ECS 120 2c:5 formal definition of NFA semantics is week 2, Friday, topic 5 for that day: formal definition of NFA semantics.
This naming convention only makes sense for Spring quarter dates; for instance in Fall 2021, the quarter starts on a Wednesday instead of a Monday, so all lectures would be shifted by one for that quarter. Refer to the current course webpage for which videos correspond to which lectures, instead of using the names on the AggieVideo website.
-
From David Doty
-
From David Doty
I forgot to write on this slide that this is Section 7.7 in the lecture notes.