Scribd
Upload
8 views2 pages

CS301: Algorithm Design & Analysis Exam

The document outlines a CS301 exam on Design and Analysis of Algorithms, consisting of various problems related to flow networks, coin selection, minimum spanning trees, vertex covers, and clique covers. Each question requires theoretical proofs, algorithmic solutions, or graphical representations. The exam is structured to assess understanding of key algorithm concepts and their applications.

Uploaded by

polar neckson
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views2 pages

CS301: Algorithm Design & Analysis Exam

The document outlines a CS301 exam on Design and Analysis of Algorithms, consisting of various problems related to flow networks, coin selection, minimum spanning trees, vertex covers, and clique covers. Each question requires theoretical proofs, algorithmic solutions, or graphical representations. The exam is structured to assess understanding of key algorithm concepts and their applications.

Uploaded by

polar neckson
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

CS301 : Design and Analysis of Algorithms

Total Marks 60 Time:3 Hour

1. Figure 1 shows a flow network on which an s − t flow has been computed. The capacity
of each edge appears as a label next to the edge, and the numbers in boxes give the
amount of flow sent on each edge.
10/10

10/10
10/10
10/0

10/10 15/5
5/5
10/0

5/5 5/5
15/0

15/0

Figure 1: Flow Graph

(a) What is the value of this flow? Is this a maximum (s, t) flow in this graph?
(b) Show step wise how to find out the maximum flow from the flow given. Note that
you have to show the steps to calculate the max flow from the given flow using the
algorithm discussed in the class.
(c) What is the minimum s − t cut for the given graph? Show a minimum s-t cut. 10
marks.

2. Given a sequence of coins c1 , · · · cn of varying denominations we have to pick coins such


that the total value of the coins picked is a maximum, with the constraint that if ci is
picked then ci−1 and ci+1 , cannot be picked. One simple minded strategy is to add up
the coins at odd positions and those at even positions and pick the sequence that has
the higher total value. Give a counter example to show that this strategy will not work.
Give a dynamic programming based solution for the problem. 5 marks.

3. A minimum bottleneck spanning tree of an edge-weighted graph G is a spanning tree of


G such that minimizes the maximum weight of any edge in the spanning tree. Prove
that every minimum spanning tree is a minimum bottleneck spanning tree. 10 marks.

4. Show that if a graph’s edges all have distinct weights, the MST is unique. 5 marks.

1
5. Consider the graph G in Figure 2. Consider the instance < G, 2 >, where we are asking
whether G has a vertex cover of size 2 or not. Consider the vertex cover to hamiltonian
cycle reduction discussed in the class. Draw the complete gadget (reduced graph for HC
instance) for the instance < G, 2 >. 10 marks.
c

a b

Figure 2: < G, 2 >

6. Consider an execution of the DFS and BFS algorithm on Kn , the complete graph on n
vertices. What will be the shape of the DFS and BFS tree? Does the shape depend on
the order in which the vertices are explored?
For a graph G the BFS and DFS trees are same. Prove that G do not contain a cycle.
10 marks.

7. A clique cover of a given undirected graph is a partition of the vertices of the graph into
cliques, subsets of vertices within which every two vertices are adjacent. That is, given
a graph G(v, E),{V1 , V2 · · · Vk }} is a clique cover for G if V = V1 ∪ V2 ∪ · · · Vk and for all
u, v ∈ Vi , (u, v) ∈ E.

Figure 3: Clique cover

In a clique cover problem given a graph G and an integer k the objective is to decide
whether there exist a clique cover size k for G or not. Prove that clique cover problem
is NP hard by showing a reduction from 3-Colorability problem. 10 marks.

Page 2

You might also like