Dsecl Zg519-Ec3m PDF

Birla Institute of Technology & Science, Pilani
Work-Integrated Learning Programmes Division

Second Semester 2018-2019
M.Tech (Data Science and Engineering)
End-Semester Test (EC-3 Makeup)
Course No. : DSECL ZG519

Course Title : DATA STRUCTURE ALGORITHMS AND DESIGN
Nature of Exam : Closed Book
Weightage : 40% No. of Pages =3
Duration : 150 Min No. of Questions = 9
Date of Exam : 28-09-2019[AN]
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.
Answer All the Questions (Only in the pages mentioned against questions. If you need more
pages. Continue remaining answers from page 17 onwards, we have provided extra space at
each question)
Question 1: [2M] [to be answered only in page 2]

Q.1. Find the time complexity of the recursion function T(n) =2T(n/2)+nlogn.
Question 2: [3M] [to be answered only in page 3]

Q.2. Implement the dictionary operations INSERT,DELETE, and SEARCH using linked, circular
lists. What are the running times of your procedures?
Question 3: [2+2 =4M] [to be answered only in pages 4-5]

Q.3. Question based on fig-1, The Morse code is a common code that is used to encode
messages consisting of letters. Each letter consists of a series of dots and dashes; for
example, the code for the letter a is ●– and the code for the letter b is –●●●. The letters
of a word are separated by a space. For Example , the morse code for “SOS” is ’●●● –
– – ●●●’ . The binary tree shown below is defining Morse code for all the 26 alphabets.
The root node stores no letter. A branch to the left signifies a dot in the code and a
branch to the right is a dash. In addition to the root node, there are 26 nodes containing
the capital letters of the English alphabet.
Fig-1
a) What is the morse code for the test ‘EOD’ based on the given tree?
b) What is the text for the morse code ‘●–● ●●– –●’
DSECL ZG519 (EC-3 MakeUP) Second Semester 2018-2019 Page 1 of 3

Question 4: [4+2 =6M] [to be answered only in pages 6-7]
Q.4. Consider a hash table created for storing integers. The initial size of the hash table is 5.
The hash function used is integer value (X) mod the size(N) of the hash table . H(X)=
X Mod N. When the load factor reaches or exceeds 0.5, the table enlarges to double
capacity and rehashes values stored at smaller indices first. Insert the following
elements in order. 86, 76, 16, 66, 26
a) What are the indices of the elements 86, 76, 16, 66, 26 in the final hash set?
Indices start from 0.
b) What is the load factor of the final hash set?
Question 5: [4M] [to be answered only in pages 8-9]
Q.5. Construct a Binary Search tree for the following keys 13, 3, 4, 12, 14, 10, 5, 1,8, 2, 7,
9, 11, 6, 18 in that order.
Question 6: [3+2M =5M] [to be answered only in pages 10-11]
Q.6. Consider a complete undirected graph with vertex set {A,B,C,D,E} entry w[i,j] in the
matrix w below is the weight of the edge {i,j} as per the Table-1
A B C D E
A 0 35 40 ∞ ∞
B 35 0 25 10 ∞
C 40 25 0 20 15
D ∞ 10 20 0 30
E 0 0 15 30 0
Table-1
a) Construct the minimum spanning tree using kruskal’s algorithm and
b) Calculate the total cost of the minimum spanning tree
Q.7. Suppose you woke up on some mysterious island and there are different precious items
on it. Each item has a different value and weight. You are also provided with a bag to
take some of the items along with you but your bag has a limitation of the maximum
weight you can put in it. So, you need to choose items to put in your bag such that the
overall value of items in your bag maximizes. The only condition of the island is none
of the items cannot be broken. There are different kinds of items (i =4) and each
item i has a weight (wi) and value (vi) associated with it. xi is the number of i kind of
items we have picked. And the bag has a limitation of maximum weight (W =8).
Item i Value (vi) weight (wi)

1 15 1
2 10 5
3 9 3
4 5 4
Table-2
(hint : you can solve this problem using the Dynamic programming approach)

Q.8. Imagine you have a 20 GB file with one string per line. Explain how you would sort the
file.
Q.9. Let A1,A2,A3, and A4 be four matrices of dimension 30 × 1, 1 × 40, 40 × 10, 10 × 25,
respectively. Parenthesize the matrix to minimize the number of scalar multiplications
required and cost of multiplying the given matrix
*** ALL THE BEST ***

Dsecl Zg519-Ec3m PDF

Uploaded by

Copyright:

Available Formats

Dsecl Zg519-Ec3m PDF

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Dsecl Zg519-Ec3m PDF

Uploaded by

Copyright:

Available Formats

Birla Institute of Technology & Science, Pilani

Work-Integrated Learning Programmes Division

Course No. : DSECL ZG519

Question 1: [2M] [to be answered only in page 2]

Question 2: [3M] [to be answered only in page 3]

Question 3: [2+2 =4M] [to be answered only in pages 4-5]

DSECL ZG519 (EC-3 MakeUP) Second Semester 2018-2019 Page 1 of 3

Question 5: [4M] [to be answered only in pages 8-9]

Question 6: [3+2M =5M] [to be answered only in pages 10-11]

Question 7: [6M] [to be answered only in pages 12-13]

Item i Value (vi) weight (wi)

DSECL ZG519 (EC-3 MakeUP) Second Semester 2018-2019 Page 2 of 3

Question 9: [6M] [to be answered only in pages 16-17]

* ALL THE BEST *

DSECL ZG519 (EC-3 MakeUP) Second Semester 2018-2019 Page 3 of 3

You might also like