CS532 ANALYSIS AND DESIGN OF ALGORITHMS
Tuesday/Thursday, 6:10-7:40 p.m, Wilson Clark Center - Room 403
sava dot krstic at intel dot com
Thomas Cormen, Charles Leiserson, Ronald Rivest and Cliff Stein: Introduction to Algorithms, second edition, MIT Press and McGraw-Hill, 2003.
- Week 1: Preliminaries (Ch. 1-4)
- What is an algorithm?
- Measuring performance
- Big-Oh and similar notations
- Week 2: Data Structures (Ch. 10,6,12)
- Basic structures (arrays, lists, trees, dictionaries, sets)
- Binary search trees
- Weeks 3,4: Sorting and Searching (Ch. 6-8,13,18)
- Insertion sort, heapsort, quicksort, mergesort, lower bounds for sorting
- AVL-trees, red-black trees, B-trees, splay trees
- Week 5: Hashing (Ch. 11) and Midterm
- Week 6: Design and Analysis Techniques (Ch. 15-17)
- Dynamic programming
- Greedy algorithms
- Amortized analysis
- Weeks 7,8: Graph Algorithms
- Traversals, topological sort, strongly connected components
- Minimum spanning trees
- Shortest paths
- Week 9: Computational Geometry (Chapter 33)
- Line-segment intersection
- Convex hulls
- Week 10: NP-Completeness (Ch. 34)
There will be seven assignments. They will be given on Tuesdays and handed in on Tuesday the following week. For problems involving programming, you can use any programming language.
Two in-class 15 minute quizzes will be assigned during weeks 3 and 8. The midterm will probably be on February 5, and the final on March 17. Quizzes will be ``closed book'', and exams will be ``open book and notes''.
Homework will account for 30% of the grade, quizzes for 15%, midterm for 25%, and the final for 30%.
To be announced.
Department of Computer
Science and Engineering
Oregon Graduate Institute
20000 NW Walker Road
Beaverton, OR 97006-8921