Date: Wed, 20 Nov 1996 21:43:30 GMT Server: NCSA/1.5 Content-type: text/html No Title

CS 330 (Algorithms) --- Fall 95

Computer Science Department, Boston University

Solutions:
Homework: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, Midterm

Office hours:
T 3:30-5, W 1:30-3
Book:
Cormen, Leiserson, Rivest: Algorithms. McGraw-Hill 1990.
Topics:
Some commonly used algorithms and data structures. Analysis from the point of view of correctness, and the amount of resources used. Some of the topics: sorting, recursion, set data structures, dynamic programming, greedy algorithms, backtracking, shortest path, graph matching, some algebraic algorithms, NP problems.
Prerequisites:
CS112, MA293
Kind of work required:
Read the textbook, solve the homework problems (may involve writing C programs as well as giving mathematical proofs), participate in the class discussion.
Homework:
given, in general, on Thursday and due in class on Tuesday 12 days later. No credit for late homework.
Tests:
a midterm exam, and a final exam (closed book, closed notes), and one or two unannounced short quizzes. For the tests, a single handwritten ("crib") sheet is permissible.
Final grade:
Approximately, 25% for homework, 25% for the midterm, 30% for the final, 10% for the quizzes, 10% for class participation.
Information updates:
on the Worl-wide Web at
http://cs-www.bu.edu/faculty/gacs/courses/cs330.
Tentative more detailed plan of topics:
09/05
Intro. Insertion sort. Alg. anal. concepts.
09/07
Recursion. Merge sort.
09/12
Rates of growth.
09/14
More rates of growth. Recursive listing of permutations. Heaps
09/19
More heaps
09/21
Quicksort
09/26
Analysis of randomized Quicksort.
09/28
Median in exp. linear time.
10/03
Hashing, with linked lists.
10/05
Hashing, open adressing.
10/10
Monday schedule due to Columbus Day.
10/12
Binary search trees.
10/12
(Shift everything down) Red-black trees.
10/17
Dynamic programming.
10/19
Greedy algorithms.
10/24
More greedy algorithms. Graph representation.
10/26
Breadth-first search. Depth-first search.
10/31
Midterm (material up to red-black trees)
11/02
Eval. of midterm. Depth-first search. Topological sort
11/07
Spanning trees. (Mergeable heaps.) Shortest paths.
11/09
Shortest paths cont. All-pairs shortest paths.
11/14
Max. flow.
11/16
Bipartite matching.
11/21
Branch-and-bound illustrated on the longest path problem.
11/23
Thanksgiving.
11/28
Approximation algorithms: vertex cover and set cover.
11/30
Polynomial complexity, NP problems.
12/05
NP-complete problems.
12/07
Shift from above
12/12
Tba


Peter Gacs - gacs@cs.bu.edu