CS:3330 Exam 2 Announcement
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.