Course Syllabus

COMP 202 – Algorithm Analysis

Fall 1996

Meeting Place: SN011 Meeting Time: 11:00 - 12:15, TuTh

Instructor: Prof. David Plaisted Telephone: 962-1751 Office: SN352 E-mail: plaisted@cs.unc.edu Office Hours: 2:30-3:30 Mon

TA: Liu, Boyang Telephone: 962-1821 TA Office: 307 E-mail: liub@cs.unc.edu TA Office Hours: 12:30-2:30 MW

Text: Introduction to Algorithms, Cormen, Leiserson, and Rivest, McGraw Hill, 1990.

Prerequisites: COMP 122 and COMP 181 (new, undergraduate versions).

You should not register for COMP 202 if you have not taken COMP 122 and COMP 181 at UNC, or similar classes taught at another university.

Grading: Homework 30% Midterm Exam 30% Final Exam 40%

The final exam will cover the entire course.

There will be 5 or more homework assignments. Some of the homework assignments may be timeconsuming. Students are encouraged to work together on the problem sets. Note that this says “work together” — copying homework solutions from another student will be considered cheating and dealt with accordingly. Homework assignments are due in class on the due date given. No late homeworks will be accepted.

Topics: The list of topics I plan to cover is given below. Chapters 1 through 18 are really COMP 122 material. I plan to review this material quickly. I urge you to come to class extra well prepared when we cover this material.

Please note that some topics have been listed as taking 0 classes. These are mainly topics that I consider too elementary to discuss in class. You are still responsible for all sections of each chapter listed below unless otherwise noted.

Topics Covered                                                         Classes
==============                                                         =======
Administrivia                                                          1
Chapter 1 -- Introduction to the course
Section 2.1 -- Asymptotic notation
Mathematical Foundation: summations, recurrences, sets                 0
etc., counting and probability
Section 2.2, Chapters 3-6
Review of Sorting and Order Satistics                                  1
Chapter 7 -- Heapsort
Chapter 8 -- Quicksort
Chapter 9 -- Sorting in Linear Time
Chapter 10 -- Medians and Order Statistics
(I plan to spend most of this class period on Chapter 8.  You are
still responsible for knowing the material in Chapters 7, 9, and 10.)
Chapter 11 -- Elementary Data Structures                               0
Review of Hashing and "Simple" Balanced Tree Algorithms                1
Chapter 12 -- Hash Tables
Chapter 13 -- Binary Search Trees
Chapter 14 -- Red-Black Trees
(I plan to cover only Chapters 12 and 14 in class.  You are still
responsible for knowing the material in Chapter 13.)
Chapter 15 -- Augmenting Data Structures                               0
Advanced Design and Analysis Techniques                                1
Chapter 16 -- Dynamic Programming
Chapter 17 -- Greedy Algorithms (will skip 17.4 and 17.5)
Chapter 18 -- Amortized Analysis
==============================================================================

Advanced Data Structures                                               3
Chapter 19 -- B-Trees
Chapter 20 -- Binomial Heaps
Chapter 22 -- Data Structures for Disjoint Sets
Probabilistic analysis (skiplist, quicksort)                           2
Graph Algorithms                                                       5
Chapter 23 -- Elementary Graph Algorithms
Chapter 24 -- Minimum Spanning Trees
Chapter 25 -- Single-Source Shortest Paths (will skip 25.5)
Chapter 26 -- All-Pairs Shortest Paths (will skip 26.4)
Chapter 27 -- Maximum Flow
NP-Completeness and Approximation Algorithms                           6
Chapter 36 -- NP-Completeness
Chapter 37 -- Approximation Algorithms
Other Advanced Topics
Chapter 31 -- Matrix Algorithms                                        2
Chapter 32 -- Polynomials and FFT                                      2
Chapter 33 -- Number-Theoretic Algorithms                              2
Chapter 34 -- String Matching                                          1
TOTAL                                                                 27