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.