Exam 2 for CS:3330 "Algorithms" will be held on Oct 29th (Thursday) from 6:30 pm to 8:30 pm in 101 BBE (Biology Building East).

During the exam you can use any written/printed material you bring, including books and lecture notes; in other words, this is an open book/notes exam. Make sure you bring everything that you feel you will need to the exam because you will not be allowed to share or borrow material with classmates during the exam. You will have to turn off and remove from your vicinity all electronic devices including cell phones, lap tops, calculators, dictionaries, etc.

This exam is over material in Chapter 3 (all of it) and Chapter 4 sections 4.1, 4.2, and 4.4. Additionally, you are responsible for all of the material covered in lectures since Exam 1.

The exam is worth 200 points, which is 20% of your final grade. Here is a brief description of the structure of the exam. Points will be equally divided among the 5 problems (so 40 points per problem).

• Problem 1. On the running time analysis of basic graph algorithms for different graph representations.
  Sample problems: Problems 1 and 3 from HW3.

• Problem 2. On the graph traversal algorithms, breadth-first search and depth-first search and their applications to other problems (e.g., finding all connected components, finding the diameter of a graph, determining if a graph is bipartite, determining if a graph is strongly connected, etc.).
  Sample problems: Problems 2, 4, 6, 9 in Chapter 3; Problems 4 and 5 in HW3; Problems 1, 2, and 3 in HW4.

• Problem 3. On showing that a simple and natural greedy algorithm for a problem is incorrect by constructing counterexamples. Here, you may be required to show that the algorithm is not a c-approximation for some given constant c.
  Sample problems: Problem 2 in HW3.

• Problem 4. On designing and proving the correctness of a simple greedy algorithm. The given problem will have the "flavor" of the scheduling problems we have studied in class.
  Sample problems: Problem 3, 5, 7, 12 in Chapter 4; Problems 4, 5, 6, 7 in HW4.

• Problem 5: On Dijkstra's Shortest Path algorithm.
  Sample problems: I will post a couple of practice problems on Dijkstra's shortest path algorithm.