Birla Institute of Technology & Science, Pilani
Work-Integrated Learning Programmes Division
First Semester 2016-2017
EC-3 Regular Comprehensive Examination
Course Title : Data Structures and Algorithms
Course No : SS ZG 519
Total : 50 marks
Nature of Exam : Open Book
Duration : 3 hours
Date : 05/11/2016 (AN)
No. of Pages = 2
No. of Questions = 5
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.
1. (a) Write a program to list out all the monotonic increasing subsequence of an array of inte-
gers. For example, for the input is 1; 4; 2; 7; 9, output will be 1; 1; 4; 1; 2; 1; 7; 1; 4; 7; 1; 2; 7;
1; 9; 1; 4; 9; 1; 2; 9; 11; 7; 9; 1; 4; 7; 9; 1; 2; 7; 9; 4; 4; 7; 4; 9; 4; 7; 9; 2; 2; 7; 2; 9; 2; 7; 9; 7; 7; 9; 9;
(4Marks)
(b) What is the running time of your program and justify your answer. (3Marks)
(c) Prove that af(n) + bg(n) is O(max{f(n); g(n)}) where a and b are some constants.
(3Marks)
2. The goal of n-queens problem is to place n queens on a nn chessboard such that no queen
attacks any other queen (A queen attacks any queen if it is in the same row, or column or
diagonal). Following is a gure shows an attempted solution that fails (two queens on the
same diagonal) for 8-queens problem.
(a) Formulate the problem so that we can use a greedy algorithm: That is, describe the
states, initial state, successor states for each state. Which data structure will you use
to represent the state? (4Marks)
(b) Write an algorithm to generate all successor states of a given state? (3Marks)
(c) Write an algorithm to check whether no queens attack each other in a given state.(3Marks)
(d) Provide a strategy to pick up the best state from the set of successor states of a given
state and justify why you think it is a best strategy. (2Marks)
3. Draw the hash table of size 11 resulting from hashing the keys 45, 93, 97, 58, 53, 105, 26,
41, 31.
(a) Using the hash function h(i) = (i - 5) mod 11) and assuming collisions are handled
by chaining. (3Marks)
SS ZG519 (EC-3 Regular Compre) First Semester 2016-2017 Page 1 of 2
(b) Using the same hash function but collisions are handled by linear probing. (2Marks)
(c) Using the same hash function but collisions are handled by quadratic probing. (2Marks)
(d) Using the same hash function but collisions are handled by double hashing with sec-
ondary hash function h' where h'(k) is dened as the least signicant digit in k. For
example h'(45) = 5. (2Marks)
4. (a) Provide a best case instance for the heap sort algorithm. We are not assuming anything
about the input and the best case running time is O(n). (5Marks)
(b) Modify insertion sort so that the output will be in decreasing order. (2Marks)
(c) We used decision trees to model comparison based algorithms for instances of size n.
Draw a decision tree for your algorithm for the input size 4. (4Marks)
5. (a) Construct the adjacency matrix and adjacency list for the following graph.
(4Marks)
(b) Construct a simple, connected, weighted graph with 7 vertices and 12 edges and each
with unique edge weights. Identify one vertex as a start vertex and illustrate a running
on Dijkstra's algorithm on this graph. (4Marks)
SS ZG519 (EC-3 Regular Compre) First Semester 2016-2017
Work-Integrated Learning Programmes Division
First Semester 2016-2017
EC-3 Regular Comprehensive Examination
Course Title : Data Structures and Algorithms
Course No : SS ZG 519
Total : 50 marks
Nature of Exam : Open Book
Duration : 3 hours
Date : 05/11/2016 (AN)
No. of Pages = 2
No. of Questions = 5
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.
1. (a) Write a program to list out all the monotonic increasing subsequence of an array of inte-
gers. For example, for the input is 1; 4; 2; 7; 9, output will be 1; 1; 4; 1; 2; 1; 7; 1; 4; 7; 1; 2; 7;
1; 9; 1; 4; 9; 1; 2; 9; 11; 7; 9; 1; 4; 7; 9; 1; 2; 7; 9; 4; 4; 7; 4; 9; 4; 7; 9; 2; 2; 7; 2; 9; 2; 7; 9; 7; 7; 9; 9;
(4Marks)
(b) What is the running time of your program and justify your answer. (3Marks)
(c) Prove that af(n) + bg(n) is O(max{f(n); g(n)}) where a and b are some constants.
(3Marks)
2. The goal of n-queens problem is to place n queens on a nn chessboard such that no queen
attacks any other queen (A queen attacks any queen if it is in the same row, or column or
diagonal). Following is a gure shows an attempted solution that fails (two queens on the
same diagonal) for 8-queens problem.
(a) Formulate the problem so that we can use a greedy algorithm: That is, describe the
states, initial state, successor states for each state. Which data structure will you use
to represent the state? (4Marks)
(b) Write an algorithm to generate all successor states of a given state? (3Marks)
(c) Write an algorithm to check whether no queens attack each other in a given state.(3Marks)
(d) Provide a strategy to pick up the best state from the set of successor states of a given
state and justify why you think it is a best strategy. (2Marks)
3. Draw the hash table of size 11 resulting from hashing the keys 45, 93, 97, 58, 53, 105, 26,
41, 31.
(a) Using the hash function h(i) = (i - 5) mod 11) and assuming collisions are handled
by chaining. (3Marks)
SS ZG519 (EC-3 Regular Compre) First Semester 2016-2017 Page 1 of 2
(b) Using the same hash function but collisions are handled by linear probing. (2Marks)
(c) Using the same hash function but collisions are handled by quadratic probing. (2Marks)
(d) Using the same hash function but collisions are handled by double hashing with sec-
ondary hash function h' where h'(k) is dened as the least signicant digit in k. For
example h'(45) = 5. (2Marks)
4. (a) Provide a best case instance for the heap sort algorithm. We are not assuming anything
about the input and the best case running time is O(n). (5Marks)
(b) Modify insertion sort so that the output will be in decreasing order. (2Marks)
(c) We used decision trees to model comparison based algorithms for instances of size n.
Draw a decision tree for your algorithm for the input size 4. (4Marks)
5. (a) Construct the adjacency matrix and adjacency list for the following graph.
(4Marks)
(b) Construct a simple, connected, weighted graph with 7 vertices and 12 edges and each
with unique edge weights. Identify one vertex as a start vertex and illustrate a running
on Dijkstra's algorithm on this graph. (4Marks)
SS ZG519 (EC-3 Regular Compre) First Semester 2016-2017
No comments:
Post a Comment