CS/ECE 374 - Algorithms and Models of Computation

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.

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].
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].
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].
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].
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].
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].
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].
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].
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].
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]
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].
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].
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].
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].
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].
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.
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].
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.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].
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.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].
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].
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.2. Reducing SAT to 3SAT [slides : youtube].
  - 21.6.3. 2SAT [slides : youtube].
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].

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].
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 2020-12-04 18:53:43 UTC 2020 by Sariel Har-Peled