COMP 482 / ELEC 420: Design and Analysis of Algorithms

In this course, you should deepen your knowledge about algorithm analysis. Furthermore, you will use those skills while exploring a number of important classes of algorithms and data structures. You will also examine the limits of practical computation, in the form of NP-completeness.

Course administrative information

Schedule
(Tentative and approximate. Will be updated throughout the semester.)
Assignments Due	Date			Topic	CLRS Reading
	T	26	Aug	Course overview	1-2
	Th	28		Algorithm Analysis
	Th	28		Asymptotic concepts & useful math	3.1,A,B,3.2
	T	2	Sep	Asymptotic concepts & useful math	3.1,A,B,3.2
1 (sol'n)	Th	4		Recurrences	4
	T	9		Recurrences	4
	T	9		Probabilistic analysis	5
	Th	11		Probabilistic analysis	5
				Sorting & Sorting-like Algorithms
				Sorting	6-8
	T	16		Hurricane Ike aftermath
	Th	18		Sorting (continued)	6-8
2 (sol'n)	T	23		Sorting (continued)	6-8
				Order statistics	9
				Convex Hull	33.1,33.3
	Th	25		Convex Hull	33.1,33.3
3 (sol'n)	T	30		Tree-based Data Structures
3 (sol'n)	T	30		Skip Lists	10,12,13, This paper
4 (sol'n) Project deadline 1	Th	2	Oct	Skip Lists	10,12,13, This paper
4 (sol'n) Project deadline 1	Th	2		Amortization & Splay trees	17,Handout
	T	7		Amortization & Splay trees	17,Handout
	T	7		Heaps	19-20
5 (sol'n) Project deadline 2	Th	9		Heaps	19-20
	T	14		Mid-semester holiday
	Th	16		Heaps (continued)	19-20
				String Algorithms
				String Matching	32
6 (sol'n)	T	21		String Matching	32
Exam 1 (sol'n)	Th	23		Tries
	T	28		Optimization
	T	28		Network flow	26
	Th	30
7 (sol'n) Project deadline 3	T	4	Nov
7 (sol'n) Project deadline 3	T	4		Linear Programming	29
	Th	6
8 (sol'n)	T	11
	Th	13		NP-Completeness
	Th	13		NP-completeness	34,Handout
9 (sol'n)	T	18
	Th	20
10 (sol'n)	T	25
10 (sol'n)	T	25		Approximation	35
	Th	27		Thanksgiving holiday
Project deadline 4	T	2	Dec	Approximation	35
	Th	4		Approximation	35
11 (sol'n)	F	5		Finals & Winter holiday
Exam 2 (sol'n)	W	17		Finals & Winter holiday