Introduction to Analysis of Algorithms
For fundamental algorithms we study the analysis of important properties such as correctness, optimality, and running time. Basic discrete probability is covered in order to analyze randomized algorithms. Knowledge of proof techniques including mathematical induction is assumed.
Prerequisites
CS 320 with a minimum grade of C
Topics
- Graph coloring: greedy and randomized greedy algorithms
- Linear programming and semidefinite programming
- NP-completeness
- Entropy and the optimality of Huffman coding
- Randomized algorithms for sorting and order statistics
- Approximation algorithms for cut problems: the Goemans–Williamson algorithm and Karger’s algorithm
Optional textbook
Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein. 3rd edition or later recommended.
2026 Spring Semester Details
Instructor(s)
|
Instructor |
Ewan Davies |
|
Office |
CSB 448 |
|
|
|
|
Office Hours |
Thursday 11am, CSB 448 |
Class Schedule
|
Section |
Schedule |
Location |
Instructor |
|---|---|---|---|
|
001 |
MWF 9:00am – 9:50am |
Walnut 111 |
Ewan Davies |
|
R01 |
W 3:00pm-3:50pm |
CSB 425 |
Ewan Davies |
TA Information
Ali Bigdeli
