ALGORITHMS ANALYSIS AND DESIGN PPT

ALGORITHMS ANALYSIS AND DESIGN PPT

Instructor: David Luebke

Description: This course will provide a rigorous introduction to the design and analysis of algorithms. We will discuss classic problems (e.g., sorting, traveling salesman problem), classic algorithm design strategies (e.g., divide-and-conquer, greedy approaches), and classic algorithms and data structures (e.g., hash tables, Dijkstra's algorithm). We will also analyze algorithm complexity throughout, and touch on issues of tractibility such as "NP-Completeness". Texts:Required: Introduction to Algorithms (Second Edition) by Cormen, Leiserson, Rivest, and Stein, McGraw-Hill (2001).

This book is similar to the first edition, so you could probably get by with only the first edition.  However, all homework problems assigned from the book will be referenced from the second edition; it is your responsibility to find a way to look them up.  I strongly recommend that you buy the text rather than borrow it; this is one of only two text books that I still use on a regular basis.  It is an indispensable reference.

Lectures: A tentative schedule of lecture topics is given below. The "CULTURE" topics represent interesting but non-essential material from fields such as computational geometry and computer graphics; they add some variety to the schedule but also give us some slack if we get behind schedule.  If we cover a "culture" topic in class, you will be tested on it.

Number	Topic	Source	Text
1	Introduction, administration, time and space complexity	PPT	--
2	Basics: asymptotic notation	PPT	3.1-3.2
3	Basics: recurrences (mergesort)	PPT	4.1
4	Basics: recurrences continued, master theorem	PPT	4.3, 6.1-6.2
5	Sorting: intro to heapsort	PPT	6, 7.1-7.3
6	Sorting: heapsort, priority queues	PPT	7.4
7	Sorting: quicksort	PPT	5.1-5.3
8	Sorting: quicksort average case analysis	PPT	5.4 last section
9	Sorting: linear time sorting algorithms	PPT	8.1-8.2
10	Sorting: linear time algorithms continued; Order statistics: selection in expected linear time	PPT	8.3-8.4 9.1-9.2
11	Order statistics: selection in worst-case linear time	PPT	9.3
12	Review for exam	PPT
13	Structures: binary search trees	PPT	12.1-12.3
14	Structures: red-black trees	PPT	13.1-13.2
15	Structures: red-black trees (insertion)	PPT	13.3-13.4
16	Structures: skip lists	PPT	--
17	Structures: skip lists, hash tables	PPT	11.1-11.2
18	Structures: hash tables (hash functions)	PPT	11.3-11.4
19	Structures: hash tables (universal hashing)	PPT	11.3-11.4
20	Augmenting structures: dynamic order statistics	PPT	14.1-14.2
21	Augmenting structures: interval trees	PPT	14.3
22	Graph algorithms: the basics	PPT	22.1-22.3
23	Graph algorithms: BFS	PPT	22.3
24	Graph algorithms: DFS	PPT	23.1
25	Minimum spanning trees	PPT	23.2
26	Shortest paths: Bellman-Ford	PPT	24.1-24.3
27	Shortest paths: DAG, Dijkstra's algorithm	PPT
28	Finish Dijkstra's.  Kruskals algorithm; disjoint sets	PPT	21.1-21.3, 23.2
29	Disjoint sets; amortized analysis	PPT	17.1-17.2
30	Amortized analysis continued	PPT	17.3-17.4
31	Dynamic programming	PPT	15.1, 15.3
32	Dynamic programming (longest common subsequence)	PPT	15.4
33	Dynamic programming (knapsack problem)	PPT
34	Greedy algorithms	PPT	16.1-16.2
35	NP-Completeness	PPT	34.1-34.2
36	NP-Completeness continued	PPT	34.1-34.2
37	NP-Completeness: reductions	PPT	34.3-4
38	NP-Completeness: reductions	PPT	34.3-4
39	Review for final	PPT	--