Computer Science 477/677
Design and Analysis of Algorithms

CSC 477/677 Study Guide for the Second Midterm Examination Fall 2005

  1. Review the homework assignments.
  2. There will be some true/false and fill-in-the-blank questions.
  3. I have posted exams from 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 November 8 exam.
  4. 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. 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 ...... "
    A list of graph topics.
  5. Use dynamic programming to solve the single-source least weight path problem for this weighted acyclic directed graph where the source is V0. Here is the same graph in pdf format.
  6. Dynamic programming algorithm for the knapsack problem..
  7. Graphs, algorithms and data structures.
    1. Definitions of terms.
    2. Data structures used to represent graphs.
    3. Topological order.
  8. Dynamic programming, divide and conquer.
  9. Know about preorder, inorder, and postorder traversals of a binary tree.
  10. Know about B-trees, tries, treaps, AVL trees, node splitting, rotation.