Department of CSE Term: Winter 2011 York University Instructor: Andy Mirzaian

CSE3101: Design and Analysis of Algorithms Final Examination

April 19, 2011

Instructions:

• Test time = 180 minutes.

• Do not use any electronic or mechanical storage, computation, or

communication device.

Student Last Name: First Name:

York ID: (CSE) Email:

1. (20 marks)

2. (28 marks)

3. (26 marks)

4. (26 marks)

Total (100 marks)

1. Double Vision in Sorted Array:

The input is an array A[1..n] of n positive numbers sorted in increasing order.

The problem is to determine whether there is a pair of indices i and j such that A[i] = 2A[j]. Design and analyze an O(n) time in-place algorithm for this problem.

             2. Tree Broadcast:

The CEO of a large company has an urgent and important message, and she needs to notify every employee by phone. The company hierarchy can be described by a tree T, rooted at the CEO, in which each other node v has a parent node u where u is the direct superior officer of v, and v is a direct subordinate of u. To notify everyone of the message, the CEO first calls each of her direct subordinates, one at a time. As soon as each subordinate gets the phone call, he or she must notify each of his or her direct subordinates, one at a time. The process continues this way until everyone has been notified. (Note that each person in this process can only call direct subordinates on the phone.) We can picture this process as being divided into rounds. In one round, each person who has already learned the message can call one of his or her direct subordinates on the phone. [Interpret T as a digraph (each edge directed from parent to child) given by its adjacency list structure. So, Adj[x] is the list of direct subordinates of employee x.]

The number of rounds it takes for everyone to be notified depends on the order in which each person calls their direct subordinates. For example, in Fig (a) below, it will take only two rounds if A starts by calling B, but it will take three rounds if A starts by calling D.

a) Consider the instance in Fig (b). Show an optimum solution by labeling each edge by its

round number. What is the required minimum number of rounds?

A BD

C

CEO

Fig (b).

  Fig (a).

b) Define MinRounds(x) to be the minimum number of rounds it takes, counted from the time employee x learns the message, to broadcast the message to all subordinates of x (i.e., all nodes in the subtree rooted at x). Develop a DP recurrence that expresses MinRounds(x)

in terms of that of its direct subordinates MinRounds(y), for all y∈Adj[x].

2. Continued:

c) Give an efficient algorithm that takes as input a broadcast tree T given by its adjacency list structure, and outputs the minimum number of rounds needed to broadcast a message in T.

d) Analyze the worst-case time complexity of your algorithm in (c) as a function of n (# nodes in T).

            3. Treasure Hunt:

You are given a directed graph G = (V,E), where each node v∈V in the graph has a certain amount of money m(v) > 0 sitting on it. You are also given vertices s, t ∈ V . The goal is to start at s and follow a directed path in G to reach t, picking up as much money along the way as you can. You may visit the same node more than once, but once you have picked up the money at that node, it is gone. Define M(G, m, s, t) to be the maximum money that can be picked up on any path from s to t (paths need not be simple).

a) Show M(G, m, s, t) and a corresponding optimum st-path for the instance below.

9435

s1262t 2438

b) Design and analyze an efficient algorithm to compute M(G, m, s, t).

(You are not required to compute the optimum st-path.)

For full credit, your algorithm should run in time O( |V| + |E| ). [Hint: think about SCC.] You may continue your answer on the next page.

3. Answer to part (b) continued:

      4.

Max Flow Min Cut:

a)

Below we have an instance of a flow network with the source s and terminal t and edge capacities shown. Show the max flow and the min cut on the same figure. Also write down the value of that flow and the capacity of that st-cut below the figure as indicated. [Recommendation: do the scratch work on back-side of a page first.]

a9b

     10

5

9

8 6

3 4

15

t

   s

   c7d

Max flow value = _________________ , Min st-cut capacity = __________________ .

Now answer the following parts (b) – (d) for a general Flow Network N= (V, E, c, s, t):

b) Given a flow f for a flow network N, how would you algorithmically determine whether f is a feasible flow for N in O( |V| + |E| ) time?

4. Continued:

c) Given a feasible flow f for a flow network N, how would you algorithmically determine whether f is a max flow for N in O( |V| + |E| ) time?

d) Given a max flow f for a flow network N, how would you algorithmically determine a min capacity st-cut for N in O( |V| + |E| ) time?