CS/ECE 374fa22 : Prerecorded lectures

---

These are old prerecorded lectures of the course, broken into small chunks by topic. 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.
This course should follow similar lines to these pre-recorded lectures. They provide a good way to clarify things if you unclear about specific topic.

---

1. Strings, countable sets, languages, overview of what is coming up [slides]
   • 1.1. Strings [slides, ct, youtube].
   • 1.1.1. Strings exercise [slides, ct, youtube].
   • 1.2. Countable sets: [slides, ct, youtube].
   • 1.3. Inductive proofs over strings: [slides, ct, youtube].
   • 1.4. Languages: [slides, ct, youtube].
   • 1.5. Overview [slides, ct, youtube].
   
   
2. Regular languages [slides]
   • 2.1. Regular languages - Definition: [slides, youtube].
   • 2.1.1. Review questions on regular languages: [slides, youtube].
   • 2.2. Regular expressions: [slides, youtube].
   • 2.2.1. Some examples of regular expressions: [slides, youtube].
   • 2.2.2. An example of a non-regular language [slides, youtube].
   
   
3. Deterministic finite automatas [slides]
   • 3.1. Introduction to DFAs [slides, youtube].
   • 3.1.1. Graphical representation of DFAs [slides, youtube].
   • 3.1.2. Formal definition of DFAs [slides, youtube].
   • 3.1.3. Extending the transition function to strings [slides, youtube].
   • 3.2. Building DFAs [slides, youtube].
   • 3.3. Complement languages for a DFA [slides, youtube].
   • 3.4. Product construction [slides, youtube].
   • 3.5. Supplemental: DFA philosophy. [slides, youtube].
   
   
4. Non-deterministic finite automatas [slides]
   • 4.1. Introduction to NFAs [slides, youtube].
   • 4.1.1. Formal definition of NFAs [slides, youtube].]
   • 4.1.2. Extending the NFA transition function to strings [slides, youtube].
   • 4.2. Building NFAs [slides, youtube].
   • 4.3. Closure properties of NFAs [slides, youtube].
   • 4.4. Every regular language has an NFA that accepts it [slides, youtube].
   
   
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]
   • 7.1. A fluffy introduction to context-free languages (CFL) [slides, youtube].
   • 7.2. Formal definition of context-free grammars (CFG) [slides, youtube].
   • 7.3. (Optional) Converting regular languages into CFL [slides, youtube].
   • 7.4. Some properties of CFLs
     • 7.4.1. Closure properties of CFLs [slides, youtube].
     • 7.4.2. Parsing trees and ambiguity [slides, youtube].
   • 7.5. Proving a CFG generates a specific language [slides, youtube].
   • 7.6. CFGs normal form [slides, youtube].
   • 7.7. PDA: Pushdown automatas [slides, youtube].
   • 7.8. Supplemental: Why aⁿ bⁿ cⁿ is not CFL? [slides, youtube].
   
   
8. Lecture 8: Turing machines [slides]
   • 8.1. History and background on Turing Machines and the halting theorem [slides, youtube].
     ...Or can computers really be intelligent? ( Turing's excellent paper on AI).
   • 8.2. Formal definition of a Turing machine [slides, youtube].
   • 8.3. Snapshots of TM execution [slides, youtube].
   • 8.4. The type of languages defined by a Turing machine [slides, youtube].
   • 8.5. Examples of Turing machines
     • 8.5.1. Turing machine for w$w [slides, youtube].
     • 8.5.2. Turing machine for 0ⁿ1ⁿ [slides, youtube].
     • 8.5.3. Turing machine for aⁿbⁿcⁿ [slides, youtube].
   • 8.6. Why Turing machine is a real computer [slides, youtube].
   
   
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].
    • 10.1. Brief introduction to the RAM model [slides, youtube].
      • 10.1.1. What is an algorithmic problem? slides [youtube].
    • 10.2. What is a good algorithm, and why use asymptotic running time? [slides, youtube].
    • 10.3. Reductions [slides, youtube]
      • 10.3.1. More examples of reductions slides [youtube]
    • 10.4. Recursion and self reductions [slides, youtube].
    • 10.5. Divide and Conquer [slides, youtube].
    • 10.6. Merge sort [slides, youtube].
      • 10.6.1. Proving that merge, in merge-sort, is correct [slides, youtube].
      • 10.6.2. Proof that merge-sort is correct [slides, youtube].
      • 10.6.3. Running time analysis of merge-sort: Recursion tree method [slides, youtube].
    • 10.7. QuickSort [slides, youtube].
    • 10.8. Binary search [slides, youtube].
    • 10.9. Solving recurrences - some examples [slides, youtube]
    • 10.10. Supplemental: Divide and conquer algorithm for closest pair [slides, youtube]
    
    
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]
    
    • 13.1. Recursion and memoization
      • 13.1.1. Fibonacci numbers [slides : youtube].
      • 13.1.2. Automatic/implicit memoization [slides : youtube].
    • 13.2. Dynamic programming [slides : youtube].
    • 13.3. Checking if a string is in $L^*$ [slides : youtube].
    • 13.4. Longest increasing subsequence revisited [slides : youtube].
    • 13.5. How to come up with dynamic programming algorithms [slides : youtube].
    • 13.6. Supplemental: Some experiments with memoization [slides : youtube].
    • 13.7. Tangential: Fibonacci and his numbers [slides : youtube].
    • 13.1.2 Answers to questions [slides : youtube].
    
    
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].
    • 15.1. Graph basics [slides : youtube : ct].
    • 15.1.1. Graph notation and representation [slides : youtube].
    • 15.2. Graph connectivity [slides : youtube].
    • 15.3. Computing connect components in undirected graphs [slides : youtube].
    • 15.4. Direct graph and directed connectivity [slides : youtube].
      • 15.4.1. Strong connected components (SCCs) [slides : youtube].
      • 15.4.2. Graph exploration in directed graphs [slides : youtube].
    • 15.5. Some algorithms on directed graphs using basic search [slides : youtube].
    • 15.6. Exercises: Modeling problems and solving them using graphs [slides : youtube].
    
    
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.4.1. DFS in Directed Graphs: Pre/Post numbering [slides : youtube].
      • 16.4.2. DFS and cycle detection: [slides : youtube].
    • 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.2.1. Shortest path with negative lengths: The challenge [slides : youtube].
      • 18.2.2. Shortest path via number of hops [slides : youtube].
      • 18.2.3. The Bellman-Ford Algorithm [slides : youtube].
      • 18.2.3.1. Correctness of the Bellman-Ford Algorithm [slides : youtube].
      • 18.2.4. Bellman-Ford: Detecting negative cycles [slides : youtube].
      • 18.2.5. Variants on Bellman-Ford [slides : youtube].
    • 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.1.1. Minimum spanning tree. Problem definition. [slides : youtube].
      • 20.1.2. Some graph theory [slides : youtube].
    • 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.4.1. Safe edges must be in the MST [slides : youtube].
      • 20.4.2. The safe edges form the MST [slides : youtube].
      • 20.4.3. The unsafe edges are NOT in the MST [slides : youtube].
    • 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.3.1. Independent Set and Clique [slides : youtube].
      • 21.3.2. NFAs/DFAs and Universality [slides : youtube].
    • 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)
      • 21.6.1. CNF, SAT, 3CNF and 3SAT [slides : youtube].
      • 21.6.1.1. Review problems on CNF [slides : youtube].
      • 21.6.2. Reducing SAT to 3SAT [slides : youtube].
      • 21.6.3. 2SAT [slides : youtube].
    
    
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
      • 22.2.1. Introduction [slides : youtube].
      • 22.2.2. Certifiers/Verifiers [slides : youtube].
      • 22.2.3. Examples to problems with efficient certifiers [slides : youtube].
      • 22.2.4. NP: Definition [slides : youtube].
      • 22.2.5. Intractability (P, NP, EXP) [slides : youtube].


23. NP and NP-Completeness [slides : youtube : ct]
    • 23.1. NP-Completeness: Cook-Levin Theorem
      • 23.1.1. Completeness [slides : youtube].
      • 23.1.2. SAT is NP-Complete [slides : youtube].
      • 23.1.3. Other NP Complete Problems [slides : youtube].
    • 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.2.1. The circuit satisfiability (CSAT) problem [slides : youtube].
      • 24.2.2. Towards reducing CSAT to 3SAT [slides : youtube].
      • 24.2.3. Reduction from CSAT to SAT [slides : youtube].
    • 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.3.3.1. The variable assignment gadget [slides : youtube].
        • 24.3.3.2. The clause gadget [slides : youtube].
    • 24.4. Proof of Cook-Levin Theorem
      • 24.4.1. Statement and sketch of idea for the proof [slides : youtube].
      • 24.4.2. The consistency of execution [slides : youtube].
    • 24.5. NP-Complete problems to know and remember [slides : youtube].

---

---

Last modified: Fri 2022-08-19 17:55:39 UTC 2022 by Sariel Har-Peled