Midterm exam will be given on Wednesday, March 4, in class. It will be a
closed-book exam; however, you may bring one 8.5 × 11 page (or two
sides) of notes. You must prepare and handwrite your own set of notes; in
particular, your notes may not be photo-copied or electronically transferred
from another source. The exam will cover all of the lectures given prior to
the exam, reading assignments (Chapters 1–3, §§4.1, 4.2,
4.4) and Homework 1–5.
A list of particularly important topics
The first problem: stable matching
Algorithm analysis
Asymptotic notation
Breadth-first search (BFS)
Depth-first search (DFS)
Testing bipartiteness
Directed acyclic graphs (DAGs) and topological ordering
Greedy algorithms for scheduling problems
Dijkstra's algorithm
Suggested practice exercises from the text
p. 68, Exercise 5
p. 107, Exercise 3
pp. 189, 190, Exercise 3
Additional exercises
For the following exercises, assume that a graph has $n$ nodes and $m$ edges.
Design an $O(n)$-time algorithm to determine whether or not a given graph
$G$ contains a cycle.
Suppose that we are given a directed graph $G = (V, E)$ on which each edge
$(v, w) \in E$ has a real value $r(v, w)$, where $0 \le r(v, w) \le 1$, that
represents the reliability of a communication channel from $v$ to $w$.
Regarding $r(v, w)$ as the probability that the channel from $v$ to $w$ will
not fail, where these probabilities are independent, design an
$O(m \log n)$-time algorithm to find the most reliable path between two given
nodes. Note that, since the probabilities are independent, the probability
that a path will not fail is the product of the probabilities that its edges
will not fail.
Finally, do not forget to review all the homework problems. The homework
problems are as important as those given above.
