Next: About this document ...
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(n2) if the graph is
represented with an adjacency matrix.
- 2.
- Consider the following modified DFS procedure for directed
acyclic graphs:
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.
Next: About this document ...
Subhashis Banerjee
4/24/2001