CSC 411 Analysis of Algorithms

Official Course Description

This course presents the fundamental techniques for designing efficient computer algorithms, providing correctness, and analyzing the complexity of algorithms. General topics include methods for expressing and comparing the complexity of algorithms: worst and average cases, sorting, selection, graph algorithms, and basic algorithm design techniques such as divide-and-conquer, greedy method, backtracking, and dynamic programming.

Syllabus

Download syllabus (PDF)

Time and Place

Classroom: McCort Ward 209
Day/Time: Tue/Thu 2:10 PM - 3:25 PM

Schedule

Week Topic Class 1 Class 2 Resources
1 Algorithmic Problem Solving and Common Problem Types
2 Fundamentals of Algorithm Analysis Slides: Asymptotic Analysis Lean proofs for complexity
3 Asymptotic Analysis and Math Review Slides: Asymptotic Analysis Slides: Recurrence Analysis
4 Exhaustive Search Slides: Brute-Force Methods Algorithms sandbox (GitHub)
5 Recursive Problems and Solutions No class: Administrative Monday Slides: Decrease and Conquer
6 Divide and Conquer Slides: Topological Sorting and Gray Codes Slides: Divide and Conquer (Part 1) Assignment 2 (GitHub)
7 Transformations and Reductions Slides: Divide and Conquer (Part 2) Slides: Problem Transfor­mations
8 Midterm exam Midterm Review Outline Quiz 1 Solution
Quiz 2 Solution
Makeup Quiz 2 Solution
9 Spring Break
10 Tradeoffs Between Space and Time Complexity Slides: LLM Inference
11 Dynamic Programming Slides: Dynamic Programming (Part 1)
12 Dynamic Programming
13 Greedy Algorithms
14 Complexity Lower Bounds Notes: NP-Completeness Extra Credit: Matrix Multiplication
15 Approximation Algorithms
16 Final Exam Review Notes: Final Review
Notes: Subset Sum Reduction 		You can beat the binary search
An open-source spec for Codex orchestration: Symphony

Additional Resources

Algorithm Demos