首页 >
> 详细

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

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Cs2461-10实验程序代做、代写java，C/C++，Python编程设 2021-03-02
- 代写program程序语言、代做python，C++课程程序、代写java编 2021-03-02
- Programming课程代做、代写c++程序语言、Algorithms编程 2021-03-02
- 代写csc1-Ua程序、代做java编程设计、Java实验编程代做 代做留学 2021-03-02
- 代做program编程语言、代写python程序、代做python设计编程 2021-03-02
- 代写data编程设计、代做python语言程序、Python课程编程代写 代 2021-03-02
- Cse 13S程序实验代做、代写c++编程、C/C++程序语言调试 代写留学 2021-03-02
- Mat136h5编程代做、C/C++程序调试、Python，Java编程设计 2021-03-01
- 代写ee425x实验编程、代做python，C++，Java程序设计 帮做c 2021-03-01
- Cscc11程序课程代做、代写python程序设计、Python编程调试 代 2021-03-01
- 代写program编程、Python语言程序调试、Python编程设计代写 2021-03-01
- 代做r语言编程|代做database|代做留学生p... 2021-03-01
- Data Structures代写、代做r编程课程、代做r程序实验 帮做ha 2021-03-01
- 代做data留学生编程、C++，Python语言代写、Java程序代做 代写 2021-03-01
- 代写aps 105编程实验、C/C++程序语言代做 代写r语言程序|代写py 2021-03-01
- Fre6831 Computational Finance 2021-02-28
- Sta141b Assignment 5 Interactive Visu... 2021-02-28
- Eecs2011a-F20 2021-02-28
- Comp-251 Final Asssessment 2021-02-28
- 代写cs1027课程程序、代做java编程语言、代写java留学生编程帮做h 2021-02-28