ECS 220: Graduate Theory of Computation
ECS 220: Graduate Theory of Computation
These are lectures for the course ECS 220, Graduate 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. The textbook is The Nature of Computation by Moore and Mertens: http://nature-of-computation.org/
To list the videos in order, view the 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 up the videos by chapter in the textbook for the course:
To list the videos in order, view the 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 up the videos by chapter in the textbook for the course:
- chapter 1: Prologue
- chapter 2: The Basics
- (there are no lectures for chapter 3)
- chapter 4: Needles in a Haystack: The Class NP
- chapter 5: Who is the Hardest One of All? NP-Completeness
- chapter 6: The Deep Question: P vs. NP
- chapter 7: The Grand Unified Theory of Computation
- chapter 8: Memory, Paths, and Games
Videos are labeled ECS 220 [week][day]:[section]-[topic] where [week] is a number 1,2,...,10, [day] is a letter (a=Monday, b=Wednesday, c=Friday), [section] is the section of the textbook, and [topic], if necessary, starts with a number to indicate topic viewing order within that section. (Sometimes [section] and [topic] are reversed if we cover a section out of order.)
For example, ECS 220 2c:5.3-2 NAE-SAT reduces to 3-Coloring is week 2, Friday, Section 5.3 of the textbook, topic 2 for that day and section: NAE-SAT reduces to 3-Coloring.
-
From David Doty