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]
  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]
  6. Lecture 6: How to prove that languages are not regular, and minimal automatas [slides]
  7. Lecture 7: Context free languages [slides]
  8. Lecture 8: Turing machines [slides]
  9. Lecture 9: The halting theorem [slides] 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]
  12. Lecture 12: More on recursive algorithms (backtracking, and search trees). [slides]
  13. Lecture 13: Introduction to dynamic programming [slides : youtube : ct]

  14. Lecture 14: More dynamic programming [slides : youtube : ct]

  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].
  17. BFS and Dijkstra's Algorithm for Shortest Paths [slides : youtube : ct].
  18. Dynamic Programming: Shortest Paths and \DFA to Reg Expressions [slides : youtube : ct]
  19. Greedy algorithms [slides : youtube : ct]
  20. Minimum spanning trees (MST) [slides : youtube : ct]
  21. Polynomial time reductions [slides : youtube : ct]
  22. NP: Nondeterministic polynomial time [slides : youtube : ct]

  23. NP and NP-Completeness [slides : youtube : ct]
  24. Circuit satisfiability and Cook-Levin Theorem [slides : youtube : ct]

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