Summer '98 CS3158A,
Introduction to Algorithms.
Lectures:
Time: MWF 11-12
Location: CCB 16
Instructor: H. Venkateswaran
Office Hours: MWF 3-4
Office: CCB 255
Phone: +1-404-894-3658
Email: venkat@cc.gatech.edu
Help sessions:
Time: F 3-4
Location: CCB 201
TA: Ion Mandoiu
Office Hours: MW 2-3, TTh 3-4
Office: CCB 245
Phone: +1-404-894-9443
Email: mandoiu@cc.gatech.edu
Newsgroup: git.cc.class.3158
Final grade (revised):
Homeworks: 15%, Midterm: 37.5%, Programming assignment: 10%,
Final exam: 37.5%.
Handouts:
First half schedule
( Postscript file)
Problem set 1
( Postscript file)
Solution set 1
( Postscript file)
Problem set 2
( Postscript file)
Solution set 2
( Postscript file)
Problem set 3
( Postscript file)
Solution set 3
( Postscript file)
Midterm
( Postscript file)
Problem set 4
( Postscript file)
Solution set 4
( Postscript file)
Problem set 5
( Postscript file)
Solution set 5
( Postscript file)
Problem set 6
( Postscript file)
Solution set 6
( Postscript file)
Problem set 7
( Postscript file)
Solution set 7
( Postscript file)
Articulation points and DFS
( Postscript file)
Programming assignment
( Postscript file)
Test graphs:
The first line of each file below contains the number of vertices and
the number of edges in the graph (in the format "n=XXXX m=XXXXX").
The rest of the file is organized as follows: each vertex i appears
on a line by itself, followed by a line for each neighbor j>i
of i (containing j and the length of edge
(i,j)). Each list of neighbors is ended by an empty line.
Vertices i which do not have neighbors with an index greater
than i are not represented.
NOTE: Vertices are indexed from 0 to n-1.
Tar archive containing all test files:
samples.tar.gz [on a Unix
machine, extract the files by giving the command
"gunzip samples.tar.gz" followed by "tar xvf samples.tar"]
Required output for programming assignment:
Your program should read the input graph (in the format described above)
from the standard input, and write the results on the standard output.
Depending on the problem you choose, the output should contain:
- the list of all articulation points, or
- the length of the minimum spanning tree, or
- the length of the shortest path between vertex 0 and
vertex n-1.
You can add more information in your output if you wish (author, running
time, size of input graph, etc.), but do not make the output too lengthy.
Expected results:
| Graph: | 1000-1 | 1000-2 | 1000-3 |
5000-1 | 5000-2 | 5000-3 | 25000-1 | 25000-2
| 25000-3 |
| Art point: |
700 | 810 | 475 | 2764 | 3672 |
3787 | 19546 | 4893 | 19546 |
| MST: | 86472 | 69294 | 62840 | 414464 |
349879 | 314375 | 1285258 | 1266060 | 1208690 |
| D(0,n-1)
| 1199 | 724 | 696 | 1035 | 799 |
995 | 814 | 972 | 685 |
Other files:
unixtimer.c
unixtimer.h