## Description

1. (20 pts) Short answer questions. For each question answer TRUE/FALSE. If you answer

TRUE provide a brief justification consisting of at most 3 short sentences (for majority of

these questions, one short sentence suffices). If you answer FALSE provide a small counterexample. Long and complicated justifications as well as unnecessarily large and complicated

counter-examples will lose marks. Guesses without justification receive 0 marks.

Note: for some of the false statements below it might be hard to find a counter-example.

You are encouraged to give it your best shot, but if you notice that you are spending

disproportionate amount of time, you are encouraged to consult the web. If you find a

counter-example on the web you must understand it, internalize it, and write it up from

memory. In addition, you must cite the resource that you used (this won’t cost you any

mark deductions), and you are still responsible for correctness of the example (i.e., you can’t

blame the source if it ultimately turns out incorrect – there is plenty of wrong information

on the web).

(a) An undirected graph with n vertices and at most n − k edges has at least k connected

components.

(b) The shortest-paths tree computed by Dijkstra is necessarily an MST.

(c) Suppose that we have computed an MST. If the weight of each edge in the graph is

increased by 1, the computed spanning tree remains minimum with respect to the new

weights.

(d) In a weighted directed graph with positive weights, Dijkstra might call the update()

procedure (aka Relax() procedure, see CLRS 24.3) on the same edge more than once.

(e) Maximum flow in a network with integral capacities is necessarily integral.

(f) We are given a weighted graph and a shortest path from s to t. If all edge weights in

the graph are multiplied by a positive constant, the given path remains shortest from

s to t with respect to the new weights.

(g) Suppose we run DFS on a directed graph G = (V, E) and we find a vertex with discovery

time 1 and finishing time 2|V |. Then the entire graph must be strongly connected.

(h) Ford-Fulkerson method runs in polynomial time assuming that capacities are positive

integers.

(i) Ford-Fulkerson method terminates on all input flow networks with capacities that are

positive real numbers.

(j) Undirected graph G = (V, E) is called k-regular if degree of every vertex is exactly k.

Girth of the graph is the length of a shortest cycle in G. For example, the simple cycle

with 5 vertices is a 2-regular graph of girth 5. We claim that there is no 3-regular graph

of girth 5 on 10 vertices.

1 of 3

CSC373, Assignment 2

2. (20 pts) Design an efficient algorithm for the following problem:

Input: Undirected graph G = (V, E) in adjacency lists representation with unit edge

costs. Vertices s, t ∈ V .

Output: The number of distinct shortest paths from s to t.

(a) Briefly describe your algorithm in plain English.

(b) Describe your algorithm in pseudocode.

(c) Formally prove correctness of your algorithm.

(d) State and justify the running time of your algorithm.

3. (20 pts) You have a server that can be attached to two electrical outlets simultaneously.

The server runs uninterrupted as long as it is attached to at least one electrical outlet. The

server is located on a rolling cart that can be moved freely within the rectangular room (the

room has no obstacles). Looking at the room from above and seeing its plan, you know

the coordinates of n electrical outlets given by (xi

, yi). Currently the server is attached

via a single power cable of length ` to the electrical outlet s. You would like to move the

server without any interruptions to electrical outlet t. For that purpose you can purchase an

additional power cable of length L and move the server from one electrical outlet to another

until it reaches t. You would like to find out what is the minimum length L of additional

power cable that you need to purchase to accomplish this task. Design an O(n

2

log n)-time

algorithm to compute the minimum value of L. Note this problem is assumed to be entirely

2-dimensional – length in this problem refers to the regular Euclidean 2D distance.

Input: {(xi

, yi)}

n

i=1 – positions of electrical outlets; ` – length of the given power cable;

s, t ∈ [n] – starting and terminal electrical outlets

Output: minimum value of L such that we can move the server from s to t uninterrupted.

(a) Briefly describe your algorithm in plain English.

(b) Describe your algorithm in pseudocode.

(c) Provide a concise argument of correctness of your algorithm. You may use results

proven in class/textbook, but make sure to cite them accurately.

(d) Justify that the runtime is O(n

2

log n).

4. (20 pts) Consider the following network graph.

s

a

b

c

d

e

f

g

t

15

9

8

10

2

6

5

7

3

14

5

10

24

6

2 of 3

CSC373, Assignment 2

(a) Compute maximum flow f and minimum cut (S, T).

(b) Draw the residual graph Gf – don’t forget to state the capacities. Indicate the minimum

cut (S, T) in the residual graph by circling S and T.

(c) An edge is called constricting if increasing its capacity leads to an increase in the value

of maximum flow. List all constricting edges in the above network.

(d) Find a small (at most 4 nodes) example of a network graph that has no constricting

edges.

(e) Describe in plain English an efficient algorithm to find all constricting edges. Argue

correctness by using results from lectures/textbook. State the running time of your

algorithm.

5. (20 pts) Consider a flow network G = (V, E), s, t, c with integral capacities together with an

additional edge-price function p : E → N. The value p(e) denotes the price to increase the

capacity of edge e by one unit. Suppose we have already computed maximum flow f in the

network. Now, we would like to increase this maximum flow f by one unit by increasing

capacities of some edges. The goal is to do this with the least possible cost. Design an

efficient algorithm to compute which edge capacities to increase.

(a) Briefly describe your algorithm in plain English.

(b) Describe your algorithm in pseudocode.

(c) Provide a concise argument of correctness of your algorithm. You may use results

proven in class/textbook, but make sure to cite them accurately.

(d) State and justify the runtime of your algorithm.

3 of 3