Download the full course syllabus here.
Course Description
This course is a comprehensive 3-credit upper-level undergraduate course that provides a rigorous foundation in algorithmic thinking and problem-solving strategies essential for computer scientists. It bridges theoretical concepts with practical implementation, enabling students to analyze, design, and implement efficient solutions to complex computational problems.
Through a carefully structured progression of five integrated modules, students develop advanced analytical skills and algorithmic techniques applicable across diverse domains. The course emphasizes both mathematical analysis and practical implementation, ensuring students can evaluate trade-offs between different algorithmic approaches and select appropriate solutions for specific contexts.
Learning Progression
The course moves through five strategically sequenced modules covering the core paradigms of algorithm design:
- Fundamentals of Algorithm Analysis: Students master asymptotic notation (Big-O, Theta, Omega), recurrence relations, and proof techniques to rigorously analyze algorithm efficiency. This module establishes essential mathematical foundations while exploring classic sorting algorithms and their complexity bounds.
- Graph Algorithms and Greedy Strategies: Building on fundamental data structures, this module explores graph representations, traversals, and decompositions. Students implement minimum spanning tree algorithms, shortest path algorithms, and develop greedy solutions with formal correctness proofs.
- Dynamic Programming: Students learn to identify and exploit overlapping subproblems and optimal substructure, transforming exponential solutions into polynomial-time algorithms. Classic problems like knapsack, sequence alignment, and shortest paths illustrate the power of memoization and tabulation techniques.
- Computational Complexity and Approximation: This module introduces formal complexity theory, including complexity classes (P, NP, NP-complete), reduction techniques, and the limits of computation. Students develop strategies for handling intractable problems through approximation algorithms and randomization.
- Advanced Topics: The final module explores specialized algorithms for network flow, string matching, and linear programming. These advanced techniques demonstrate how algorithmic principles apply to diverse application domains and real-world optimization problems.
Course Goals
- Analyze the efficiency of algorithms using asymptotic notation (Big-O, Θ, Ω)
- Design algorithms using major paradigms including divide-and-conquer, greedy methods, and dynamic programming
- Compare different algorithms and evaluate trade-offs in performance, complexity, and implementation
- Prove algorithm correctness using formal proof techniques such as induction and loop invariants
- Identify NP-complete problems and apply appropriate strategies for tackling intractable computational challenges
- Implement efficient algorithms in a high-level programming language
- Communicate technical ideas effectively through written explanations and collaborative discussions