Computer Science 477/677
Design and Analysis of Algorithms

CSC 477/677 Study Guide for the Second Midterm Examination Spring 2004

1. Review the homework assignments.
2. I have posted exams from three prior semesters. If a question that you see on one of those exams is not related to anything we've covered in class so far this semester up to the last class day before the exam, then don't worry: it will not be on our March 16 exam.
3. I will ask you some general questions about graphs, such as the ones I have mentioned in class. These could include questions about data structures used to represent graphs, and graph algorithms we've discussed, such as depth first search, breadth first search, and Prim's algorithm. They could also include simple definitions, such as, "A directed graph is called a tree if ...... " and simple theorems such as, "The largest number of edges possible for an undirected graph of 6 vertices is ...... "
4. I will ask questions about hashing.
5. I will ask you to run Dijkstra's algorithm, by hand, for an appropriate small example.
6. I will ask you to run Floyd's algorithm, by hand, for an appropriate small example.