CS/ECE 374fa20 : Prerecorded lectures
The prerecorded lectures are available on class-transcribe: here. They are also available on youtube. If you have problems accessing the videos, let us know.
1. Strings, countable sets, languages, overview of what is coming up [slides]

2. Regular languages [slides]

3. Deterministic finite automatas [slides]

4. Non-deterministic finite automatas [slides]

5. Lecture 5: Equivalence on NFAs, DFAs and regular expressions [slides]
• 5.1. Equivalence of NFAs and DFAs [slides, youtube].
• 5.1.2. Algorithm for converting an NFA to DFA [slides, youtube].
• 5.1.3. Proof of correctness of conversion from NFA to DFA [slides, youtube].
• 5.2. Closure properties of regular languages: PREFIX/SUFFIX [slides, youtube].
• 5.3. Converting an NFA into a regular expression [slides, youtube].

6. Lecture 6: How to prove that languages are not regular, and minimal automatas [slides]
• 6.1. Not all languages are regular. [slides, youtube].
• 6.2. When are states of a DFA equivalent? [slides, youtube].
• 6.3. Fooling sets: Proving non-regularity [slides, youtube].
• 6.3.1. Exponential gap in number of states between NFA/DFA [slides, youtube].
• 6.4. Using closure properties to prove that a language is not regular. [slides, youtube].
• 6.5. Minimal automata of a regular language (Myhill-Nerode theorem) [slides, youtube].
• 6.5.2. Proving and stating the Myhill-Nerode theorem [slides, youtube].

7. Lecture 7: Context free languages [slides]

8. Lecture 8: Turing machines [slides]

9. Lecture 9: The halting theorem [slides]
• 9.1. Cantor's diagonalization argument [slides, youtube].
• 9.2. Introduction to the halting theorem [slides, youtube].
• 9.3. The halting theorem (statement+proof) [slides, youtube].
• 9.4. TM-Unrecognizable [slides, youtube].
• 9.5. Turing complete (or what else is equivalent to a real computer?) [slides, youtube].
Extra: An example of proving undecidability of a language [youtube].

10. Lecture 10: Reductions, Recursion, and Divide and Conquer [slides, youtube, classtranscribe].

11. Lecture 11: Divide and conquer: Kartsuba’s Algorithm and Linear Time Selection [slides]
• 11.1. A slow algorithm for multiplying numbers [slides, youtube].
• 11.2. Multiplying numbers using divide and conquer [slides, youtube].
• 11.3. Faster multiplication of numbers - Karatsuba's algorithm [slides, youtube].
• 11.3.1. Solving the recurrences for Karatsuba's algorithm [slides, youtube].
• 11.4. Selection in linear time
• 11.4.1. Selecting in unsorted lists: Problem definition and basic algorithms slides [youtube].
• 11.4.2. Quick select [slides, youtube].
• 11.4.3. Median of medians [slides, youtube].
• 11.4.4. Median of medians is a good median [slides, youtube].
• 11.4.5. Running time analysis of the median of medians algorithm [slides, youtube].
• 11.4.6. Epilogue: On median selection in linear time [slides, youtube].

12. Lecture 12: More on recursive algorithms (backtracking, and search trees). [slides]
• 12.1. On the various flavors of recursive algorithms [slides, youtube].
• 12.2. Recursive search trees and backtracking (as demonstrated on the 8 queen problem) [slides, youtube].
• 12.3. Brute force search, recursion and backtracking
• 12.3.1. A naive algorithm for max independent set in a graph [slides, youtube].
• 12.3.2. A recursive algorithm for maximum independent set in a graph [slides, youtube].
• 12.4. Computing the longest increasing subsequence (really slowly) [slides, youtube].
• 12.4.1. Analyzing RT of recursive algorithm for longest increasing subsequence [slides, youtube].

13. Lecture 13: Introduction to dynamic programming [slides : youtube : ct]

14. Lecture 14: More dynamic programming [slides : youtube : ct]
• 14.1. Review of dynamic programming, and some exercises [slides : youtube].
• 14.2. Edit Distance and Sequence Alignment
• 14.2.1. Edit distance: Problem definition and background [slides : youtube].
• 14.2.2. More on edit distance as alignment [slides : youtube].
• 14.2.3. The algorithm for edit distance [slides : youtube].
• 14.2.4. Dynamic programming algorithm for edit-distance [slides : youtube].
• 14.2.5. Reducing the space used by edit-distance [slides : youtube].
• 14.2.6. Longest common subsequence problem [slides : youtube].
• 14.3. Maximum weighted independent set in a tree [slides : youtube].
• 14.4. Dynamic programming and DAGs [slides : youtube].
• 14.5. Supplemental: Context free grammars: The CYK Algorithm
• 14.5.1. CYK: Problem statement, basic idea, and an example [slides : youtube].
• 14.5.2. Formal description of the CYK algorithm [slides : youtube].

15. Lecture 15: Graphs and graph search (BFS/DFS/SCC) [slides : youtube : ct].

16. Lecture 16: DAGs, DFS, topological sorting, linear time algorithm for SCC [slides : youtube : ct].
• 16.1. Overview: Depth First Search and SCC [slides : youtube].
• 16.2. Directed Acyclic Graphs
• 16.2.1. DAGs definition and basic properties [slides : youtube].
• 16.2.2. Topological ordering [slides : youtube].
• 16.2.2.1. Explicit definition of what topological ordering/sorting is [slides : youtube].
• 16.3. DFS
• 16.3.1. Depth First Search (DFS) in Undirected Graphs [slides : youtube].
• 16.3.2. DFS with pre-post numbering [slides : youtube].
• 16.4. DFS in Directed Graphs
• 16.5. The meta graph of strong connected components [slides : youtube].
• 16.6. Linear time algorithm for finding all strong connected components of a directed graph
• 16.6.1. Wishful thinking linear-time SCC algorithm [slides : youtube].
• 16.6.2. Maximum post numbering and the source of the meta-graph [slides : youtube].
• 16.6.3. The linear-time SCC algorithm (finally) [slides : youtube].
• 16.7. An Application of directed graphs to make [slides : youtube].
• 16.8. Summary [slides : youtube].
• 16.9. An example of DFS forest slides.

17. BFS and Dijkstra's Algorithm for Shortest Paths [slides : youtube : ct].
• 17.1. Maps as graphs [slides : youtube].
• 17.2. BFS: Breadth First Search [slides : youtube].
• 17.2.1. BFS with distances and layers [slides : youtube].
• 17.3.1. Problem definition [slides : youtube].
• 17.3.2. Flooding, continuous Dijkstra and hot it leads to the regular Dijkstra algorithm
• Animation of (continuous) Dijkstra, and the idea behind the Dijkstra algorithm [youtube].
• Another example.. [youtube].
• 17.3.3. Shortest path in the weighted case using BFS [slides : youtube].
• 17.3.4. On the hereditary nature of shortest paths [slides : youtube].
• 17.3.5. The basic algorithm: Find the ith closest vertex [slides : youtube].
• 17.3.6. How to compute the ith closest vertex? [slides : youtube].
• 17.3.7. Dijkstra’s algorithm [slides : youtube].
• 17.3.8. Dijkstra using priority queues [slides : youtube].
• 17.4. Shortest path trees and variants [slides : youtube].
• 17.4.2. Variants on the shortest path problem [slides : youtube].

18. Dynamic Programming: Shortest Paths and \DFA to Reg Expressions [slides : youtube : ct]
• 18.1. Shortest Paths with Negative Length Edges
• 18.1.1. Why Dijkstra’s algorithm fails with negative edges [slides : youtube].
• 18.1.2. But wait! Things get worse: Negative cycles [slides : youtube].
• 18.1.3. Restating problem of Shortest path with negative edges [slides : youtube].
• 18.1.4. Applications of shortest path for negative weights on edges [slides : youtube].
• 18.2. Bellman Ford Algorithm: Shortest path with negative edges
• 18.3. Shortest Paths in DAGs [slides : youtube].
• 18.4. All Pairs Shortest Paths
• 18.4.1. Problem definition and what we can already do [slides : youtube].
• 18.4.2. All Pairs Shortest Paths: A recursive solution [slides : youtube].
• 18.4.3. Floyd-Warshall algorithm [slides : youtube].
• 18.5. Summary of shortest path algorithms [slides : youtube].
• 18.6. DFA to Regular Expression [slides : youtube].
• 18.7. Dynamic Programming: Postscript [slides : youtube].

19. Greedy algorithms [slides : youtube : ct]
• 19.1. Greedy algorithms by example [slides : youtube].
• 19.2. Greedy Algorithms: Tools and Techniques [slides : youtube].
• 19.3. Scheduling Jobs to Minimize Average Waiting Time [slides : youtube].
• 19.3.1. Exercise: Scheduling Jobs to Minimize Weighted Average Waiting Time [slides : youtube].
• 19.4. Scheduling to Minimize Lateness [slides : youtube].
• 19.5. Maximum Weight Subset of Elements: Cardinality and Beyond [slides : youtube].
• 19.6. Interval Scheduling
• 19.6.1. Problem statement, and a few greedy algorithms that do not work [slides : youtube].
• 19.6.2: Interval scheduling - earliest finish time [slides : youtube].
• 19.6.3. Proving optimality of earliest finish time [slides : youtube].
• 19.7. Greedy algorithms – an epilogue [slides : youtube].

20. Minimum spanning trees (MST) [slides : youtube : ct]
• Minimum Spanning Tree
• 20.2. Safe and unsafe edges [slides : youtube].
• 20.3. The Algorithms for computing MST [slides : youtube].
• 20.4. Correctness of the MST algorithms
• 20.5. MST algorithm for negative weights, and non-distinct costs [slides : youtube].
• 20.6. Data Structures for MST: Priority Queues and Union-Find
• 20.6.1. Implementing Borůvka’s Algorithm [slides : youtube].
• 20.6.2. Implementing Prim’s Algorithm [slides : youtube].
• 20.6.3. Implementing Prim’s algorithm with priority queues [included in previous part].
• 20.6.4. Union-find data-structure [slides : youtube].
• 20.6.5. Implementing Kruskal’s Algorithm [slides : youtube].
• 20.7. MST: An epilogue [slides : youtube].

21. Polynomial time reductions [slides : youtube : ct]
• 21.1. A quick review: Polynomials [slides : youtube].
• 21.2. (Polynomial Time) Reductions: Overview [slides : youtube].
• 21.3. Examples of Reductions
• 21.4. Polynomial time reductions
• 21.4.1. A quick review of polynomial time reductions [slides : youtube].
• 21.4.2. Polynomial-time reductions and hardness [slides : youtube].
• 21.5. Independent Set and Vertex Cover [slides : youtube].
• 21.6. The Satisfiability Problem (SAT)

22. NP: Nondeterministic polynomial time [slides : youtube : ct]
• 22.1. Review
• 22.1.1. Review: Polynomial reductions [slides : youtube].
• 22.1.2. A quick pre-review of complexity classes [slides : youtube].
• 22.1.3. Polynomial equivalent problems: What do we know so far [slides : youtube].
• 22.2. NP: Nondeterministic polynomial time

23. NP and NP-Completeness [slides : youtube : ct]
• 23.1. NP-Completeness: Cook-Levin Theorem
• 23.2. Reducing 3-SAT to Independent Set [slides : youtube].
• 23.3. NP-Completeness of Hamiltonian Cycle
• 23.3.1. Reduction from 3SAT to Hamiltonian Cycle: Basic idea [slides : youtube].
• 23.3.2. The reduction: Encoding the formula constraints [slides : youtube].
• 23.3.3. If there is a satisfying assignment, then there is a Hamiltonian cycle [slides : youtube].
• 23.3.4. If there is a Hamiltonian cycle ⇒ ∃satisfying assignment [slides : youtube].
• 23.4. Hamiltonian cycle in undirected graph [slides : youtube].

24. Circuit satisfiability and Cook-Levin Theorem [slides : youtube : ct]
• 24.1. Recap (what we know about NPC so far) [slides : youtube].
• 24.2. Circuit SAT
• 24.3. NP-Completeness of Graph Coloring
• 24.3.1. The coloring problem [slides : youtube].
• 24.3.2. Problems related to graph coloring [slides : youtube].
• 24.3.3. Showing NP-Completeness of 3 COLORING
• 24.4. Proof of Cook-Levin Theorem
• 24.5. NP-Complete problems to know and remember [slides : youtube].

Last modified: Fri 2020-12-04 18:53:43 UTC 2020 by Sariel Har-Peled