Date: Wed, 20 Nov 1996 21:43:30 GMT
Server: NCSA/1.5
Content-type: text/html
No Title
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