Space, Time, and Perfect Algorithms

This site provides slides, assignments, and other resources that I use in my Space, Time, and Perfect Algorithms class (CS-120, Westmont College).

Slides

1. Introduction: Space, Time, Perfection?
2. Recursion
3. Divide and Conquer Intro
4. Divide and Conquer: Sorting
5. Recursion Trees
6. Recursion Trees, continued
7. Backtracking
8. More Backtracking Algorithms
9. Dynamic Programming: Introduction
10. Dynamic Programming: Tables
11. Dynamic Programming: Subset Sum
    • Summary: Slide notes 1-11, Chapters 1-3
12. Review for Test #1
13. Greedy Algorithms: Scheduling
14. Greedy Algorithms: Exchange Arguments
15. Binary Character Codes
16. Huffman Codes
17. Graphs: Introduction
18. Graphs: Searching
19. Graphs: Reductions
20. Depth-First Search: Revisited
21. DAGs and Topological Sorting
22. Strong Connectivity
    • Summary: Slide notes 13-22, Chapters 4-6
23. Review for Test #2
24. Trees
25. Minimum Spanning Trees
26. Borůvka’s MST Algorithm
27. Classical MST Algorithms
28. Single Source Shortest Path Algorithms
29. SSSP Trees, Continued
30. Flow Networks
31. Maxflow-Mincut Theorem
32. Reductions to Maxflow Problems
    • Summary: Slide notes 24-32, Chapters 7,8,10,11
33. Review for Test #3
34. NP-Hardness
35. More NP-Hard Problems
36. Subset Sum
37. An NP-Hard Puzzle

Written Assignments

1. Running Time Review
2. The Baguenaudier Puzzle
3. Another Hanoi Puzzle
4. The Cavarretta Sort
5. Practice with Recursion Trees
6. More Practice with Recursion
7. Churro Cutting
8. More Backtracking Exercises
9. Fast Churro Cutting
10. Making Change
11. Candy Swap Saga
12. Test #1
13. Greedy Activity Selection
14. Interval Stabbing
15. Prefix Codes
16. Huffman Codes
17. Adjacency Lists
18. Depth-first and Breadth-first Searches
19. Number Maze
20. DFS Parentheses Theorem
21. Topological Sort
22. Strongly Connected Components
23. Test #2
24. Spring Break: No assignment
25. Spanning Tree Practice
26. Edge Contraction
27. Jarník’s Algorithm
28. Dijkstra’s Algorithm
29. Negative Cycles
30. Flows and Cuts
31. Augmenting Paths
32. Applications of Maxflow Algorithms
33. Test #3
34. Satisfiability of Boolean Formulas
35. Rep Sets
36. SUBGRAPH and SplitSum
37. Test #4

Other Resources

• Syllabus (PDF)
• Textbook (PDF)

All of the pages and slides on this site were authored in RMarkdown. The source code is available on GitHub: https://github.com/djhunter/algorithms