Outline
The undergraduate course in algorithms comprises the following topics. Each unit spans approximately one week during the spring or the fall term. There is a weeklong assignment for each unit. Two of these assignments are designated as exams: a midterm and a last (final) exam. Units may be covered in slightly different order during the term.
Unit 1: Tools and techniques. Python, the Markdown markup language, LaTeX (another markup language), discrete mathematics. Upper bound notation (big-oh \(\mathcal{O}()\) notation). Example of a simple algorithm: Newton’s method to find \(\sqrt{x}\).
Unit 2: String alignment. Problems with optimal substructure. From brute force with nearly infinite scenarios to practical solutions that can be delivered in polynomial time.
Unit 3: Recurrence relations. Divide and Conquer techniques. Derivation of the Master Theorem. Good recursion. Bad recursion. Factorial and Fibonacci computations. Multiplying very large integers.
Unit 4: Memoization and Dynamic Programming. 0/1 Knapsack (or, how to plan a museum heist). Minimum Weight Independent Set.
Unit 5: Simple graphs. Review of graph definition and basic properties. Graph types. Parts of a graph. Representing a graph with arrays. Graph traversals. Stack v. queue-based traversals of a graph. Labeling and counting components.
Unit 6: Minimum spanning trees. Boruvka’s algorithm. Relaxing tense edges. Correctness and complexity considerations. Evolution of Boruvka to Kruskal, Dijkstra and other variations.
Unit 7: Directed graphs. Adjacency matrix. Determining the reachability of a vertex. Shortest paths. Detecting cycles.
Unit 8: Maximum flows and minimum cuts or why Chicago is a more valuable strategic target than NYC.
Unit 9: Greedy algorithms: Huffman encoding.
Unit 10: Topological ordering.
Unit 11: P versus NP and complexity theory. The SAT3 problem.
The graduate course (COMP 460) comprises a review/refresh part and an advanced part. In the review part, we combine topics as follows:
Week 1: units 1 and 3
Week 2: units 2 and 4
Week 3: units 5, 7, 7, and 10
Week 4: unit 8, by itself
Week 5: unit 9, by itself
Week 6: unit 11, by itself
Depending on everyone’s background and prior experience in the graduate class, we could condense the review part even more. Then, for the last part of the term (weeks 6-12) we focus on advanced and special topics, including
Artificial neural networks
Large language models
Signal processing
Quantum computing
Cryptography
Hypergraphs
Complexity spaces
Numerical methods, etc.
The precise mix of advanced topics depends on students’ preferences and the overall group dynamic of the class.
Coding: You may use any language you wish in the course. Classroom examples are written in Python as Jupyter Notebooks. The preferred platform for these notebooks is Google Colab.