Download Solutions (Google Drive Link)
Birla Institute of Technology & Science, Pilani
Work-Integrated Learning Programmes Division
Second Semester
2015-2016
Comprehensive Examination
(EC-3 Regular)
Course No. : SS ZG519
Course Title : DATA STRUCTURES AND ALGORITHM
DESIGN
Nature of Exam : Open Book
Weightage : 50%
Duration : 3 Hours
Date
of Exam : 09/04/2016 (AN)
No
of pages: 2
No
of questions: 6
Note:
1. Please follow all the Instructions
to Candidates given on the cover page of the answer book.
2. All parts of a question
should be answered consecutively. Each answer should start from a fresh
page.
3. Assumptions made if any,
should be stated clearly at the beginning of your answer.
Q.1.
Let A[1…n]
be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is
called an inversion of A.
(a)
Which array with elements from the set {1,2,…n}
has the most inversions? How many does it have?
(b)
Describe an algorithm that determines the number
of inversions in any permutation on n elements in Q(n
logn) worst case time. [4 + 4 = 8]
Q.2.
A certain Professor Amongus claims that the
order in which a fixed set of elements is inserted into an AVL tree does not
matter - the same tree results every time. Give a example that proves Professor
Amongus wrong.
[8]
Q.3.
Let G be a graph whose vertices are the integers
1 through 8, and let the adjacent vertices of each vertex be given by the table
below:
|
Vertex
|
Adjacent vertices
|
|
1
|
2, 3, 4
|
|
2
|
1, 3, 4
|
|
3
|
1, 2, 4
|
|
4
|
1, 2, 3, 6
|
|
5
|
6, 7, 8
|
|
6
|
4, 5, 7
|
|
7
|
5, 6, 8
|
|
8
|
5, 7
|
Assume that, in
a traversal of G, the adjacent vertices of a given vertex are visited in the
same order as they are listed in the above table.
(a)
Draw G.
(b)
Show how depth-first search works on the graph G
starting from vertex 1. Also identify discovery and back edges. [3 + 5 = 8]
SS ZG519 (EC-3 Regular) Second Semester 2015-2016 Page 2
Q.4.
Does the strategy of choosing items in
increasing order of weight yield an optimal solution for the fractional
knapsack problem? Justify your answer. [8]
Q.5.
Find the minimum cost spanning tree for the
following graph using Kruskal’s algorithm?
Show all the intermediate steps. [8]
Q.6.
Professor Midas drives an automobile from Newark to Reno
along Interstate 80. His car’s gas tank, when full, holds enough gas to travel n miles,
and his map gives the distances between gas stations on his route. The
professor wishes to make as few gas stops as possible along the way. Give an
efficient method by which Professor Midas can determine at which gas stations
he should stop, and prove that your strategy yields an optimal solution. [10]
**********
No comments:
Post a Comment