BU CLA CS 530: Analysis of Algorithms

Spring 1996

Syllabus

Prerequisites:

CS 330 or consent of instructor.

Required Textbook:

[CLR] Algorithms, by T. Cormen, C. Leiserson, and R. Rivest, McGraw-Hill, 1990.

Other Textbooks (not required).

Overview:

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 (all references to [CLR]):

What is "analysis of algorithms", basic sorting techniques (Chap 1). Growth of functions and asymptotic notation (Section 2.1). Summations (Chap 3 once over lightly).

Recurrences and their solutions (early sections of Chap 4). Discrete mathematics (Chap 5). Counting and elementary probability (early sections of Chap 6).

More advance sorting techniques. Heaps, heapsort, priority queues (Chap 7). Quicksort (early sections of Chap 8).

Elementary techniques for representing discrete structures: stacks, queues, linked lists (Chap 11). Hash tables, hash functions (Chap 12). Binary search trees (Sections 13.1, 13.2, 13.3).

Programming methods: dynamic programming (early section of Chap 16), greedy algorithms (early sections of Chap 17).

Elementary graph algorithms: breadth-first search, depth-first search, topological sort (Chap 23).

More advanced graph algorithms: single-source shortest paths (early sections of Chap 25), all-pairs shortest paths (early sections of Chap 26), maximum flow (early sections of Chap 27).

Covered Fresh (all from [CLR], unless otherwise noted):

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.

Week 1.

Chapter 8. Quicksort.
Emphasis on randomized quicksort.

Chapter 9. Sorting in Linear Time.
Lower bounds for sorting, counting sort, radix sort.
Exclude Section 9.4.

Week 2.

Chapter 34. String Matching: Sections 34.1 and 34.2.
Rabin-Karp algorithm, in two randomized versions
(Monte Carlo and Las Vegas).

Chapter 10. Medians and Order Statistics.
Sections 10.1, 10.2, and (once over lightly) 10.3.

Handout 2. Randomized Algorithms.
Verification of polynomial identities.

Week 3.

Chapter 13. Binary Search Trees.
Brief review of concepts in Sections 13.1, 13.2, and 13.3.
Results of Section 13.4 without their proofs.

Chapter 16. Dynamic Programming.
Brief review of concepts in Sections 16.1 and 16.2.
Use "0-1 knapsack problem" (in lecture) instead of
"matrix-chain multiplication" (left to students).

Chapter 17. Greedy Algorithms.
Brief review of concepts in Section 17.2.
Use example of "fractional knapsack problem".

Chapter 18. Amortized Analysis.
Brief review of concepts in Sections 18.1, 18.2 and 18.3.
Use example of "incrementing binary counter".

Week 4.

Chapter 22. Data Structures for Disjoint Sets.
Sections 22.1 and 22.2 briefly, Section 22.3 thoroughly.

Chapter 23. Elementary Graph Algorithms.
Brief review of concepts in Sections 23.1, 23.2 and 23.3.

Chapter 24. Minimum Spanning Trees.
Kruskal's and Prim's algorithms.

Chapter 25. Single-Source Shortest Paths.
Sections 25.1, 25.2 and 25.3. Dijkstra's algorithm,
the Bellman-Ford algorithm, inductive proofs of correctness.

Week 5.

Chapter 26. All-Pairs Shortest Paths.
Sections 26.1, 26.2 and 26.3. Transitive closure of adjacency
matrix, generalized to transitive closure of distance matrix,
dynamic programming formulation. The Floyd-Warshall
algorithm, Johnson's algorithm.

Chapter 6. Review of elementary notions of
probability theory. Sections 6.2 and 6.3.

Handout 3. Randomized Algorithms. Edge-connectivity problem.

Week 6 (1/2 week).

Chapter 27. Maximum Flow. Sections 27.1 and 27.2.
Flow networks, the max-flow min-cut theorem.

Week 7.

Chapter 27. Maximum Flow. Sections 27.1, 27.2 and 27.3.
Reductions to max-flow problems. Maximum bipartite matching.
Mention faster algorithms based on preflow-push method and
others (Sections 27.4 and 27.5).

Chapter 28. Sorting Networks. Sections 28.1 and 28.2.

Week 8 (1/2 week).

Chapter 28. Sorting Networks. Sections 28.3, 28.4 and 28.5.

Chapter 29. Arithmetic Circuits. Sections 29.1 and 29.2.

Mid-term exam on material covered up to this point.

Week 9.

Chapter 29. Arithmetic Circuits. Sections 29.2 completed.
Briefly over Sections 29.3 and 29.4.

Chapter 30. Algorithms for Parallel Computers.
Sections 30.1 and 30.2. Work-efficient EREW algorithm for
finding the maximum in an array of integers (not in [CLR]).

Week 10.

Chapter 30. Algorithms for Parallel Computers.
Results of Section 30.3 without their proofs.

Handout 4. Parallel Graph Algorithms.
Maximal matchings in cubic graphs. Luby's randomized parallel
algorithm for maximal independent sets.

Chapter 30. Algorithms for Parallel Computers.
Section 30.4: Randomized parallel algorithm for prefix computation.

Week 11.

Chapter 30. Algorithms for Parallel Computers.
Section 30.5: Deterministic symmetry breaking. (What was shown
in lecture is that the algorithm requires O(log* n) iterations to
stop, but not that the total time is also O(log* n), contrary to the
claim in the book.)

Chapter 31. Matrix Operations.
Section 31.2: Strassen's algorithm. Theorem 31.10: Boolean matrix
multiplication. Section 31.5: Inverting matrices.

Chapter 36. NP-Completeness.
Parts of Sections 36.1 and 36.2: Preliminaries.

Week 12.

Chapter 36. NP-Completeness.
Parts of Sections 36.1, 36.2 and 36.3: Definitions of polynomial-time
verification, the classes P, NP and co-NP, polynomial-time reducibility,
NP-hard problems. Solutions of several variations of the HAM-CYCLE
problem, including Exercise 36.2-6, page 929 (solutions given in
detail in Solutions of Problem Set 11, Spring 1995).

Week 13.

Chapter 36. NP-Completeness.
Parts of Sections 36.4 and 36.5: More polynomial reductions
(to CLIQUE, SUBSET-SUM, and TSP problems). Polynomial reduction
of optimization problems to their corresponding decision problems,
and vice-versa. MAXIMUM-CLIQUE polynomially reducible to
CLIQUE-SIZE polynomially reducible to CLIQUE.

Chapter 37. Approximation Algorithms.
Preliminaries, pp 964-966. Sections 37.1 and 37.2: vertex-cover
and TSP problems.

Week 14.

Handout 5. Approximation Algorithms.
Christofides' approximation algorithm for TSP (adapted from
[PS], Chapter 14).

Chapter 37. Approximation Algorithms.
Sections 37.3 and 37.4: Set-covering and subset-sum problems.

Week 15 (1/2 week).

Chapter 37. Approximation Algorithms.
Finish Section 37.4: Subset-sum problem.

End-of-term exam on all the material covered during the semester,
with emphasis on topics after the mid-term.

Assaf Kfoury

Created:  95.12.11

Modified: 96.04.30