Spring 1995
CS 330 or consent of instructor.
[CLR] Algorithms, by T. Cormen, C. Leiserson, and R. Rivest, McGraw-Hill, 1990.
[LG] Computation Complexity, manuscript by L. Lovasz and P. Gacs, 1994.
[BB] Algorithmics, by G. Brassard and P. Bratley, Prentice Hall, 1988.
[K] The Art of Computer Programming, Vols 1, 2, 3, by D. Knuth, Addison Wesley, 1973.
[GJ] Computers and Intractability, by M.R. Garey and D.S. Johnson, W.H. Freema, 1979.
[A] The Design and Analysis of Parallel Algorithms, by S.G. Akl, Prentice Hall, 1989.
CS530 is the graduate-level continuation of CS330. The course will cover some of the core-topics, already studied in CS330 (or in some equivalent course at another university), but with more details and rigor. In addition, we will present a selection of advanced topics (additional tools for analyzing algorithms, refinements of design methodology, more advanced application areas).
Chapters and sections listed below refer to: either background material or material to be covered fresh in CS530. Most of the background material is assumed known; the little of it that is not known already can be learned without the instructor's help. Background material is largely covered in CS330 and its prerequisites (or in equivalent courses at other universities). If you are unfamiliar with any part of this background, you may have to do some reading on your own, or we may refer you to parts of it as the need arises.
Chapter 1. Introduction to Analysis of Algorithms:
insertion sort, mergesort.
Chapter 2. Growth of Functions:
asymptotic notation.
Chapters 3, 4. Summations and Recurrences (Section 4.4 excluded).
Chapters 5, 6. Discrete Mathematics (Sections 6.4-6.6 excluded).
Chapter 7. Heapsort:
priority queues, dynamic sets.
Chapter 8. Quicksort (Sections 8.3-8.4 excluded).
Chapter 11. Elementary Data Structures:
techniques for representing discrete structures.
Chapter 12. Hash Tables:
collision resolution, chaining, universal hashing,
open addressing.
Chapter 13. Binary Search Trees (Section 13.4 excluded).
Chapter 14. Red-Black Trees.
Chapter 16. Dynamic Programming (Section 16.4 excluded).
Chapter 17. Greedy Algorithms (Sections 17.3-17.5 excluded).
Chapter 23. Elementary Graph Algorithms:
breadth-first search, depth-first search, topological sort.
Chapter 25. Single-Source Shortest Paths (Sections 25.3-25.5 excluded).
Chapter 26. All-Pairs Shortest Paths (Sections 26.3-26.4 excluded).
Chapter 27. Maximum Flow (Sections 27.3-27.5 excluded):
network flow, augmenting paths, residual graph, max-flow min-cut,
Ford-Fulkerson.
Topics listed below from chapters preceding Chapter 28 are occasionally covered in CS330 (and other undergraduate-level courses on algorithms). They are purposely included here as a warm-up transition to the more advanced topics after Chapter 28.
Chapter 8. Quicksort (only Sections 8.3-8.4):
randomized quicksort, randomized algorithms.
(Supporting material on probability from Sections 6.1-6.3
assumed known.)
Section 6 in [LG]. Randomized Algorithms:
Verifying a polynomial identity, pp 100-102.
Chapter 9. Sorting in Linear Time:
lower bounds for sorting, counting sort, radix sort.
Exclude Section 9.4.
Section 9 in [LG]. Decision Trees:
Algorithms using decision trees, pp 132-134,
lower bounds on the depth of decision trees, pp 139.
Chapter 10. Medians and Order Statistics.
Chapter 6. Counting and Probability.
Review of more advanced concepts in Sections 6.4-6.6.
Chapter 13. Binary Search Trees (only Section 13.4):
randomly built binary search trees.
Chapter 18. Amortized Analysis (only Sections 18.1-18.3).
Chapter 34. String Matching (only Sections 34.1 and 34.4):
Emphasis on Section 34.4, Knuth-Morris-Pratt algorithm
and its amortized analysis.
Chapter 22. Disjoint Sets:
Emphasis on Sections 22.3 and 22.4.
Chapter 24. Minimum-Spanning Trees:
Prim's and Kruskal's algorithms.
Chapter 27. Maximum Flow:
Sections 27.1-27.2 reviewed briefly,
Sections 27.3-27.5, preflow-push algorithms, covered fresh.
Chapter 34. String Matching (Section 34.2):
Rabin-Karp algorithm, in two randomized versions
(Monte Carlo and Las Vegas).
Chapter 30. Algorithms for Parallel Computers.
Omit material in Section 30.3 based on Chapters 28 and 29,
and all of Section 30.4. Luby's randomized parallel algorithm
for finding a maximal independent set in an undirected graph
(not in [CLR], adapted from original paper in STOC 1985).
Chapter 36. NP Completeness.
Concepts and statements of results, without proofs, from
Sections 36.1-36.3. Selection of results and their proofs from
Section 36.4-36.5.
Chapter 37. Approximation Algorithms.
Christofides' improvement of APPROX-TSP-TOUR (not in [CLR],
adapted from [GJ] page 131-132.)
Chapter 35. Computational Geometry.
Additional material on the convex-hull problem (not in [CLR]):
lower bound, divide-and-conquer approach, parallel algorithms
(adapted from [A] pages 288-296).
Assaf Kfoury
Created: 94.12.07
Modified: 95.05.05