COSC-311 Sample Midterm Questions
Note: There will be four problems on the actual midterm. The problems on this
handout are meant to give you a sense of the types of questions I might ask. This
study guide is not comprehensive: there are topics we have covered in class that are
not represented in the sample problems. Everything we have done in class or on
homework is fair game for the midterm.
1
Minimum Spanning Trees
Ryan’s cool new Minimum Spanning Tree algorithm works as follows on a graph with
n vertices:
• Initialize set T = ∅ and S = u, where u is a randomly chosen vertex.
• Iterate n − 1 times: Let v be the vertex most recently added to S. Consider all
edges from v to some other vertex x that has not yet been added to S. Among
those edges, let (v, w) be the edge of lowest cost. Add edge (v, w) to T and add
w to S.
• If v doesn’t have any neighbors not already in S, go back to the second-mostrecently added vertex, and keep backtracking until you find a vertex that has
at least one neighbor not already in S. Use that vertex instead of v in this
iteration.
Sadly this algorithm does not work.
(a) State the theorem that tells us which edges are safe to add to a partial MST T .
(b) Explain why Ryan’s algorithm doesn’t fit the criteria for this theorem.
(c) Give an example of a graph with at least 3 vertices for which Ryan’s algorithm
returns the wrong answer. What does the algorithm do? What is the correct MST?
2
Scheduling
In the Interval Scheduling problem, we were given a set of jobs, where each job i
required our resource starting at time a(i) and ending at time f (i), and only one job
could be scheduled to use the resource at a time. If two jobs conflict, we must discard
one of them. Our goal was to come up with a subset of jobs S such that there are no
conflicts among the jobs in S, and |S| is maximized.
(a) Dana suggests the following greedy algorithm: let x(i) = f (i) − a(i) be the size
of job i, and let n(i) be the number of jobs conflicting with job i. Add to S the job i
1 with the smallest x(i) ∗ n(i), then throw out any jobs conflicting with i and recur on
the remaining jobs. Give a counterexample that shows that Dana’s algorithm does
not always produce the optimal solution.
(b) What is the correct greedy algorithm to solve this problem optimally?
3
More Minimum Spanning Trees
Here is a graph:
(a) Draw the minimum spanning tree that would result from running Prim’s algorithm on this graph, starting at vertex s. List the order in which edges are added to
the tree.
(b) Draw the minimum spanning tree that would result from running Kruskal’s algorithm on this graph. List the order in which edges are added to the tree.
4
Recurrences
Allie and Brandon each have come up with a divide-and-conquer algorithm to solve
a problem.
• Allie’s algorithm (algorithm A) splits a problem of size n into four pieces, each
of size n/2, solves the pieces recursively, and takes time 30n to combine the
results.
• Brandon’s algorithm (algorithm B) takes time n3 to turn a problem of size n
into a smaller problem of size n/2, which it then solves recursively.
2 (a) Write a recurrence for the runtime of Allie’s algorithm, TA (n), and a recurrence
for the runtime of Brandon’s algorithm, TB (n).
(b) Which algorithm has an asymptotically better runtime? Justify your answer by
solving each recurrence using the Master Theorem.
5
Shortest Paths
Here is a graph:
(a) Run the Bellman-Ford algorithm on the graph to find the shortest path from s
to every other node. Show the table that you fill in while running the algorithm.
(b) Now suppose you ran one extra iteration of Bellman-Ford. How could you use
that last iteration to detect whether the graph has a negative-weight cycle?
6
Making Change
Suppose you are traveling to a foreign country where the local currency has four
coins with denominations d1 = 1, d2 = 5, d3 = 8, and d4 = 14 cents. As usual, when
making change the goal is to end up with as few coins as possible.
(a) Give a counterexample to show that the greedy algorithm for making change no
longer yields the optimal solution.
(b) Write a recurrence for a dynamic programming algorithm that computes the
minimum number of coins needed to make change for n cents, C(n).
3
COSC-311 Sample Midterm Questions 2
of 3
Report
Tell us what’s wrong with it:
Thanks, got it!
We will moderate it soon!
Free up your schedule!
Our EduBirdie Experts Are Here for You 24/7! Just fill out a form and let us know how we can assist you.
Take 5 seconds to unlock
Enter your email below and get instant access to your document