Data Structures (CS130N) Minor III April 14, 2001

Name:                                 Entry:                 Grp:   

Note: Maximum marks : 60 (a mark a minute). All questions carry equal marks. Answer only in the space provided. 4 pages in all.

1.

Explain why the DFS method runs in O(n²) if the graph is represented with an adjacency matrix.

2.

Consider the following modified DFS procedure for directed acyclic graphs:

$$\begin{array} {l} \;\;\;\;\mbox{{\bf procedure} $dfs(v)$} \\... ...w)$} \\ \;\;\;\;\;\;\;\;\mbox{{\bf write} $v$} \\ \end{array}$$

Suppose that we start the procedure from a node whose indegree is 0. Prove that if we reverse the output (the resulting list of nodes) we get a topological order. What is the time and space complexity?

3.

IITD and many other technical universities are doing a joint project on multimedia. A computer network is built to connect these univs using communication links that form a tree (not rooted). The univs decide to install a file server at one central place to share data. Since the transmission time on a link is dominated by link setup and synchronization, the cost of a data transfer is proportional to the number of links used. Hence, it is desirable to choose a ``central'' location. Given a tree T and a node v of T, the eccentricity of v is the length of a longest path from v to any other node of T. A node of T with minimum eccentricity is a center of T.

(a)

Given that n univs are participating, design an efficient algorithm to compute a central location.

(b)

Is the location unique? How many distinct central locations are possible?

4.

MTNL has a network of n switching stations connected by m high-speed communication links. Each customer's phone is directly connected to one station in his or her area. The engineers of MTNL have developed a prototype video-phone system that allows two customers to see each other during a phone call. In order to have acceptable image quality, however, the number of links used to transmit video between the two parties cannot exceed 4. Suppose that MTNL's network is represented by a graph. Design an efficient algorithm that computes, for each station, the set of stations it can reach using no more than 4 links.