Name: RCS ID: @rpi.edu
CSCI 2300 — Introduction to Algorithms
Fall 2020 Exam 1 (February 20, 2020) — SOLUTIONS
• Please silence and put away all laptops, phones, calculators, electronic devices, etc.
• You may use your printed notes and book(s) for this exam
• This exam is designed to take 100 minutes, but we will use the full 110 minutes from 6:00-
7:50PM; for 50% extra time, the expected time is 150 minutes, i.e., 5:00-7:30PM
• During the exam, questions will not be answered except when there is a glaring mistake
or ambiguity in the statement of a question; we cannot clarify a question for you; please do
your best to interpret and answer each question clearly and concisely
• Long answers are difficult to grade; the space provided should be sufficient for each question;
however, you may use the last page of this exam for overflow work
• All work on this exam must be your own; do not even think of copying from others
• When you hand in your exam, be prepared to show your RPI ID
Please sign below to indicate that you will not copy or cheat on this exam:
Signature:
Do not start this exam until you are instructed to do so.
1. (3 POINTS) Given undirected graph G = (V,E) represented by an adjacency matrix, what
is the runtime of DFS to determine whether node t ∈ V is reachable from node s ∈ V ?
Assume individual lookups in the adjacency matrix are O(1). Clearly circle the best answer.
SOLUTION: O(|V |2)
2. (3 POINTS) How many connected components are there in the undirected graph below?
Clearly circle the best answer.
SOLUTION: 3 (MAKEUP is 2)
(i.e., {A,B,E, I, J}, {F}, and {C,D,G,H,K,L})
3. (3 POINTS) Applying Dijkstra’s algorithm to the directed graph below, what is the shortest
distance (i.e., minimum sum of all edge weights) from node A to node F? Clearly circle the
best answer.
SOLUTION: 6 (5 edges MAKEUP) (i.e., path A→ B → C → D → G→ F )
4. (3 POINTS) How many strongly connected components are there in the directed graph
below? Clearly circle the best answer.
SOLUTION: 3 (i.e., {A,B,E}, {C}, and {D,F,G,H, I})
5. (3 POINTS) What is the minimum number of edges you must add to the directed graph
below to make it strongly connected? Clearly circle the best answer.
SOLUTION: 2 (i.e., there are five SCCs: source SCCs {B} and {E}; SCCs {A} and {G,H, I};
and sink SCC {C,D, F, J}; therefore, we must add an edge from any node of the sink SCC
to any node of each source SCC, for a total of 2 such edges)
2
6. (12 POINTS) Draw an undirected graph G with five nodes and seven edges such that
the pre and post numbers from the DFS algorithm for all but one of the nodes differ by at
least 3 (i.e., for each node u in G, post(u) > pre(u) + 2).
SOLUTION:
• (2 points) graph is undirected
• (2 points) graph has five nodes
• (2 points) graph has seven edges
• (6 points) graph has at least one node from which DFS meets the pre/post number
requirements
7. (12 POINTS) Draw a directed acyclic graph (DAG) with four nodes that has two sources
and four distinct topological orderings.
SOLUTION:
• (2 points) graph is a DAG
• (2 points) graph has four nodes
• (4 points) graph has two sources
• (4 points) graph has four distinct topological orderings
3
8. (12 POINTS) Draw a graph with four nodes for which Dijkstra’s algorithm fails to find the
shortest path between a source node S and at least one other node, but the Bellman-Ford
algorithm succeeds.
SOLUTION:
• (1 points) graph has source node S shown
• (1 points) graph has four nodes
• (4 points) Dijkstra’s algorithm fails from node S to at least one other node specifically
due to a negative weight that causes distance d to propagate incorrectly (see example in
sample Exam 1 prep solutions)
• (6 points) The Bellman-Ford algorithm successfully finds shortest paths from node S
to all other nodes (watch for negative cycles, which also “breaks” the Bellman-Ford
algorithm)
9. (12 POINTS) Draw a connected undirected graph with six nodes and at least six edges in
which the shortest (i.e., minimum weight) path between two nodes u and v is not part of any
minimum spanning tree (MST). Show the shortest path, then draw all possible MSTs.
SOLUTION:
• (2 points) graph has six nodes
• (2 points) graph has at least six edges
• (4 points) all possible MSTs are shown
• (4 points) shortest path between identified nodes u and v is not part of any MST (u
and v must be shown on graph)
4
10. (12 POINTS) Draw a strongly connected directed graph G = (V,E) with |V | = ?? (varies)
such that, for every u ∈ V , removing u from G leaves a directed graph that is no longer
strongly connected.
SOLUTION:
• (1 points) graph is a directed graph
• (2 points) graph has specified number of nodes (varies with version of exam)
• (3 points) graph is strongly connected
• (6 points) graph is a cycle (i.e, removing any node u causes resulting graph to no longer
be strongly connected)
11. (12 POINTS) Write an algorithm to find a path that traverses all edges of directed graph G
exactly once or determines that such a path does not exist for G. You may visit nodes multiple
times, if necessary. Show the runtime complexity of your algorithm.
SOLUTION:
• (5 points) algorithm is correct (look for counter-examples)
• (1 points) algorithm identifies/returns a path...
• (2 points) ...or determines that such a path does not exist
• (4 points) runtime complexity is shown and is accurate
5
12. (13 POINTS) Consider the following pseudocode of a function that takes integer n ≥ 0 as
input.
function netflix(n):
print '*'
if n == 0: return
for i = 0 to n - 1:
print '*'
netflix(n - 1)
return
Let T (n) be the number of times the above function prints a star ('*') when called with
valid input n ≥ 0. What is T (n) exactly, in terms of n only (i.e., remove any reference of T ()
on the right-hand side). Prove your statement.
SOLUTION:
• (7 points) T (n) can be expressed as
T (n) =
n+1∑
i=1
i
or just
T (n) =
(n + 1)(n + 2)
2
Note that i could start at 0 in the summation; other rearrangements of this are fine as
long as T () does not appear on the RHS
• (6 points) Proof by induction is the best approach here, though (similar to the home-
work) stating that this is proven by definition is also fine