CST 387/405 Advanced Data Structures (Fall 2006)
- Wednesday 6:00 pm - 8:30 pm
(teleconferenced)
- Every odd week:
Schaumburg
Campus, SCH 809
- Every even week: Chicago Campus, CPA 407
Dr. Evgeny Dantsin
Adam Kirby-Swenson
Advanced
topics in data structures. Emphasis on techniques used in design and
analysis of graph algorithms. Implementation of data structures used in
algorithms for minimum spanning trees, flow networks, and shortest paths. A computer use course.
- Thomas H. Cormen, Charles E. Leiserson,
Ronald L. Rivest, and Clifford Stein.
- Introduction to Algorithms.
- 2nd Edition. McGraw-Hill, 2001.
|
Week |
Topics |
Assignments |
Textbook |
|
1 |
Syllabus. Graphs.
Graph representations: adjacency lists and adjacency matrices.
|
Project #1 |
B.4, 22.1
|
|
2 |
Euler cycles.
Hamiltonian cycles. |
Project #2 |
22 |
|
3 |
Trees. Minimum
spanning trees. Greedy approach: Kruskal’s and Prim’s algorithms.
|
HW-1 |
B.5, 23 |
|
4 |
Implementation of
Kruskal’s algorithm. Data structures for disjoint sets. |
Project #3 |
23, 21 |
|
5 |
Disjoint sets:
heuristics and running time. |
|
21 |
|
6 |
Implementation of
Prim’s algorithm. Fibonacci heaps:
amortized analysis. |
HW-2 |
23, 17, 20 |
|
7 |
Flow networks. The
Ford-Fulkerson method. Minimum cuts. Maximum bipartite
matching. |
Project #4 |
26.1-26.3 |
|
8 |
Preparation for midterm test. |
|
|
|
9 |
Midterm test. |
|
|
|
10 |
Shortest paths in
graphs.
Breadth-first search, Dijkstra's algorithm, the Bellman-Ford algorithm,
shortest paths in dags. Difference constraints. |
|
24.1-24.4 |
|
11 |
All-pairs shortest
paths and matrix multiplication. |
|
25.1 |
|
12 |
Floyd's algorithm for all-pairs
shortest paths. Warshall's algorithm for transitive closure.
Strongly-connected components. |
HW-3/4 |
25.2, 22.5 |
|
13 |
TBA |
|
|
|
14 |
Review of
the course. Preparation for the final exam. |
|
|
|
15 |
Final exam. |
|
|
Prerequisites
- Math 280 - Data
Structures
- Programming proficiency in C++
All four projects are mandatory for a passing
grade. The final grade will be based on the total number of points earned on
four homework assignments, a midterm test, and a final exam:
|
Assignment |
Maximum number of
points |
|
Undergraduate |
Graduate |
|
HW-1 |
15 |
15 |
|
HW-2 |
15 |
15 |
|
HW-3 |
10 |
15 |
|
HW-4 |
10 |
15 |
|
Midterm test |
20 |
25 |
|
Final exam |
30 |
35 |
|
Total number of points: |
100 |
120 |
Also, extra points will be
given for work in class. Overall grades will be assigned on the following
percentage scale:
|
A |
B |
C |
D |
F |
|
≥ 90% |
≥ 75% |
≥ 60% |
≥ 45% |
< 45% |
Statement on cheating and
plagiarism: Instances of academic dishonesty will be handled as described in
University policies. Depending on the severity of the violation, an instructor
may fail a student on the individual assignment or test, may lower the student’s
grade in the course, or may fail the student in the course. More details on the
University's policies on academic honesty may be found in the Student Handbook.
Lecture notes, slides,
homework assignments, and other materials were posted here after every lecture. |