COMP 482 / ELEC 420: Design and Analysis of Algorithms

Class meets in Duncan Hall 1064 on Tuesdays and Thursdays 10:50am–12:05pm. While class notes and additional handouts will be posted here, class attendance and participation is expected. Class and textbook content will overlap, but also complement each other.

The following schedule is tentative and will be updated as needed.

Overview
23–25 Aug	Overview & Multiplication Example	CLRS 1–2
Mathematical Background Assigments 1–2
25–30 Aug	Asymptotics and math	CLRS 3,A–B
1–6 Sep	Recurrences	CLRS 4
8 Sep	Probabilistic analysis	CLRS 5,C
Sorting and sorting-like algorithms Assignment 3
13–15 Sep	Sorting	CLRS 7–8
15 Sep	Order Statistics	CLRS 9
20–22 Sep	Convex Hull	CLRS 33.3
Tables Assignment 4
22–27 Sep	Hash tables, Dynamic Tables, and Amortization	CLRS 11,17
String Matching Assignment 5
29 Sep–6 Oct	String matching, Tries, and Suffix Trees	CLRS 32, Online supplements
Optimization Assigments 6–8
13–18 Oct	Dynamic Programming	CLRS 15
20–27 Oct	Network flow	CLRS 26
1–8 Nov	Linear programming	CLRS 29
NP completeness Assigments 9–10
10–17 Nov	Complexity classes, NP completeness, Supplementary handout	CLRS 34
19 Nov–1 Dec	Approximation	CLRS 35

Design and Analysis of Algorithms COMP 482 / ELEC 420 Fall 2011

Design and Analysis of Algorithms
COMP 482 / ELEC 420
Fall 2011