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 de ned as the least signi cant 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 de ned as the least signi cant 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
Awesome...
ReplyDeleteSurvival8: Bits Wilp Software Development For Portable Devices 2017-H2 Handout >>>>> Download Now
Delete>>>>> Download Full
Survival8: Bits Wilp Software Development For Portable Devices 2017-H2 Handout >>>>> Download LINK
>>>>> Download Now
Survival8: Bits Wilp Software Development For Portable Devices 2017-H2 Handout >>>>> Download Full
>>>>> Download LINK Ye
i tried mailing you , but it is not going through. Can you please share the answers to this question paper if you have.
ReplyDeleteThanks
Mail me at ashishjainblogger@gmail.com
DeleteMention the subject(s) for which you want help.
Thanks for putting up the content in such organized manner.Great Help. Thumbs UP !!
ReplyDeleteRecorded lecture links are not working please help
ReplyDeleteIs there a group/whatsapp group for Mtech in computing systems and Infrastructure?
ReplyDeleteVery useful .. Thank you very much
ReplyDeleteAre you Looking for Smart Device Development? QuantaEd Solutions is the Best Smart Device Development Company, We design and develop smart devices that suit the healthcare requirements. For any inquiry call us we will provide all kind of assistance. For more details visit- https://quantaedsolutions.com
ReplyDeleteThis post is so interactive and informative.keep updating more information...
ReplyDeleteSoftware Testing Courses in Mumbai
Software Testing Training in Ahmedabad
Software Testing Courses in Kochi
Software Testing Courses in Trivandrum
Software Testing Courses in Kolkata
Thanks for the blog article.Thanks Again. Keep writing.
ReplyDeletejava online training hyderabad
java online training in india
Thanks for the blog article.Much thanks again. Fantastic.
ReplyDeleteonline training in java
online training on java
AI & ML in Dubai
ReplyDeletehttps://www.nsreem.com/ourservices/ai-ml/
Artificial intelligence is very widespread today. In at least certainly considered one among its various forms has had an impact on all major industries in the world today, NSREEM is #1 AI & ML Service Provider in Dubai
1634348519669-9
Thank you for giving valuable information about software for portable device, we can also develop custom software from pixabulous design.
ReplyDeleteNice Blog!!!
ReplyDeleteServiceNow Training
ServiceNow Online Training in Hyderabad
This article explains in a clear manner. Nice way of explaining. Thanks for sharing. cloud engineering services
ReplyDeleteI really liked your blog post.Much thanks again. Awesome.
ReplyDeletejava online training
java training
Data Science Training In Noida
ReplyDeleteData Science course In Noida
WILP is a set of educational programs designed in such a way that they can be easily integrated into your work life. Earlier, only highly developed nations like the US and Europe were indoctrinating WILPs but now the WILP in India have also gained a lot of popularity.
ReplyDeleteCandidates who wish to take the BITSAT should begin studying as soon as possible. Due to the high level of competition, it is critical to follow the best BITSAT 2022 preparation tips recommended by professionals. This blog post contains BITSAT 2022 study suggestions as well as exam pattern and syllabus information. Continue reading to get answers to all of your questions. To know more information visit @ SSSi Online Tutoring Services.
ReplyDeleteSurvival8: Bits Wilp Software Development For Portable Devices 2017-H2 Handout >>>>> Download Now
ReplyDelete>>>>> Download Full
Survival8: Bits Wilp Software Development For Portable Devices 2017-H2 Handout >>>>> Download LINK
>>>>> Download Now
Survival8: Bits Wilp Software Development For Portable Devices 2017-H2 Handout >>>>> Download Full
>>>>> Download LINK bO
"Thanks for sharing this informative blog on Best Software Development company in chennai,Software Development Company in chennai,
ReplyDeleteBest Software Development company in india,
Top software development company in chennai,
Software Development Company in india"
The BITS Pilani Admission Process is designed to select the brightest minds for its world-class programs. With its independent entrance exam, BITSAT, and direct admission opportunities for board toppers, the institute ensures that only the most deserving candidates secure a place.
ReplyDelete