# 辅导CSCI 2300调试存储过程、数据库编程调试

- 首页 >> DatabaseName: 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