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
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 Transformations | |
| 8 | Midterm exam | Midterm Review Outline | ||
| 9 | Spring Break | |||
| 10 | Tradeoffs Between Space and Time Complexity | |||
| 11 | Dynamic Programming | |||
| 12 | Dynamic Programming | |||
| 13 | Greedy Algorithms | |||
| 14 | Complexity Lower Bounds | |||
| 15 | Approximation Algorithms | |||
| 16 | Final Exam Review |