UMBC CMSC641, Design & Analysis of Algorithms, Fall 1997

Course Syllabus

We will mainly follow the textbook Introduction to Algorithms, by Cormen, Leiserson and Rivest. The following schedule outlines the material to be covered during the semester and specifies the corresponding sections of the textbook. Selected topics not in the textbook will require reading from handouts. The schedule may be adjusted as the semester progresses. However, due dates for the homework assignments and the tests will not change.
TBA
Date Topic Reading Due
Wed 9/3 Introduction
Mon 9/8 Amortized Analysis 18.1 -- 18.4
Wed 9/10 Binomial Heaps 20.1 HW 1 due
Mon 9/15 Binomial Heaps 20.2
Wed 9/17 Fibonacci Heaps 21.1 -- 21.2 HW 2 due
Mon 9/22 Fibonacci Heaps 21.3 -- 21.4
Wed 9/24 Disjoint Set Union 22.1 -- 22.4 HW 3 due
Mon 9/29 Splay Trees handout
Wed 10/1 Recurrences 4.1 -- 4.4 HW 4 due
Mon 10/6 Network Flow 27.1 -- 27.2
Wed 10/8 Network Flow 27.3 -- 27.4 Test 1 due
Mon 10/13 Network Flow
Wed 10/15 Dynamic Programming 16.1 -- 16.4 HW 5 due
Mon 10/20 Sorting Networks 28.1 -- 28.3
Wed 10/22 Sorting Networks 28.4 -- 28.5 HW 6 due
Mon 10/27 Parallel Algorithms 30.1 -- 30.2
Wed 10/29 Parallel Algorithms 30.3 HW 7 due
Mon 11/3 Computational Geometry 35.1 -- 35.2
Wed 11/5 Convex Hulls 35.3 HW 8 due
Mon 11/10 Closest Pairs 35.4
Wed 11/12 Voronoi Diagrams handout Test 2 due
Mon 11/17 NP-completeness 36.1 -- 36.2
Wed 11/19 NP-completeness 36.3 -- 36.4 HW 9 due
Mon 11/24 NP-completeness 36.5
Wed 11/26 Approximation Algorithms 37.1 -- 37.2
Mon 12/1 Approximation Algorithms 37.3 -- 37.4
Wed 12/3 Approximation Algorithms handout HW 10 due
Mon 12/8 String Matching 34.1 -- 34.2
Wed 12/10 String Matching 34.3 -- 34.4 HW 11 due
Final Exam due

Last Modified: 22 Jul 2024 11:28:46 EDT by
Richard Chang

Back up to Fall 1997 CMSC 641 Homepage