CS:3330 Exam 2 Announcement
Exam 2 for CS:3330 "Algorithms" will be held on April 3rd (Tuesday) from 6:30 pm to 8:30 pm
in W128 CB (Chemistry Building).
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.
The exam is worth 150 points, which is 15% of your final grade. Here is a brief description
of the structure of the exam.
- Problem 1. (30 points) Graph representations (adjacency matrix and adjacency list),
run-time analysis of generic graph algorithms for different graph representations.
For example, suppose we want to compute the number of vertices that are at most 2 hops away
from every vertex in the graph. What would the running time of your algorithm be
if your underlying representation was an adjacency matrix? What if it were an adjacency list?
Also, make sure you know the basic "running-time analysis pattern" that was common
to Breadth-First Search (BFS), Depth-First Search (DFS), and Dijkstra's shortest path algorithm.
- Problem 2. (40 points) Breadth-First Search (BFS) and Depth-First Search (DFS) algorithms and variants,
correctness, run-time analysis, and applications. Some of the specific things you should know are
how to hand-execute BFS and DFS (Problem 1, Quiz 3),
how to use DFS to find connected components and perform topological sort,
how to find separating vertices (HW 6, Problem 3),
how to use BFS to count number of shortest paths (HW7, Problem 2), etc.
- Problem 3. (40 points) Dijkstra's algorithm and the Bellman-Ford algorithm and variants, run-time analysis for different priority queue
implementations, and applications.
Some of the specific things you should know are
how to hand-execute Dijkstra (Problem 2, Quiz 3) and Bellman-Ford,
how running times of priority queue operations affect the overall running time of Dijkstra,
how to improve the running time of Dijkstra in special situations (e.g., Problem 4, HW 7),
and how to improve the running time of Bellman-Ford in special situations.
- Problem 4. (40 points) Simple greedy algorithms for problems similar to the Interval scheduling problem,
constructing counter examples, proving correctness using techniques such as ``greedy finishes first.''
Take a look at the practice problems I posted on greedy algorithms.