Jadavpur University 2010 M.E Software Engineering Algorithms & Data Structure in - Question Paper
Jadavpur University
M.E in Software Engineering
1st Semester Examination, 2010
Subject: Algorithms & Data structure
uai lu/owc/ i/ iRA/ 139/ ZUi1
M.H Software Engg. 1* Scm Examination, 2010 Algorithms & Data Structures Time: Three hours Full Marks: 100
Answer any FIVE questions.
I) (4 X 2)+4+(5+3)
a) Prove that the following equalities are correct or incorrect:
i) " m> iJ 0 (n1)
ii) 10 n*+ 15 n4+ 100 n1 2" - 0(100 n2 2") lii)n* log n 0 (n1)
iv)n,2, + 6nJ3,,0(n,2*)
b) Write down the Master Theorem. **
c) Draw the recursion tree forT(n) w 4T(\nTl\) + c.n, where c is a constant, and provide a tight asymptotic bound on its solution. Verify your bound by the substitution method.
7+5+8
2)
POP should still take O (1) time.
b) Write an algorithm to evaluate prefix expression with operators + and
X.
c) A dequeue (double-ended queue) is a list from which elements can be inserted or deleted at either end. Develop array implementation for a dequeue.
(5+5)+5+5
a) Consider the following 4-digit employee numbers: 9614, 5882, 6713, 4409 and 1825. Find the 2-digit hash address of each number using (i) the division method, with m*97; and (ii) the folding method.
b) Write a function MID (KEY, HASH) which uses the mid-square method to find the 2 digit hash address HASH of a 4-digit employee number key.
c) Explain double hashing technique with example.
4) 3+5+7+5
a) Show that the maximum number of nodes in a binary tree of height h
K+l
is 2 -1
an AVL tree with following keys: 24, 1618, 2346, 271,
3141,1414,1732, 1729,8351 and 9999.
c) Write an insertion function for Red-Black Tree.
d) Remove 9, 8 and 7 from the following Red- Black tree. Show all the intermediate steps. (B Black node and RRed node)
3) 4+4+12
a) Sort the array 170, 45, 75, 90, 24, 802, 66, 19 and 551 using radix sort
4>) Write an algorithm of counting sort.
c) Show the B-tree* of order 4 that result alter successively inserting the keys A-Z into an iaitially empty tree. Delete A, B, E, I, O, P, Q and U.
6) 10+6+4
a) Find the optimal parenthesiariion of a matrix chain whose sequence of dimensions is < 10,80,20, 70.60,75 and 50>.
b) What is the solution generated by Job Sequencing algorithm when
(pi. p2. p3. p4, p5, p6, p7) - (30, 20, 5, 25. 10, 35, 15) and (dl, d2, d3. d4, d5> d6, d7) - (2, 2, 4. 3, 4, 2, 3). When; n- no of jobs, p-profit and d* deadline.
c) Prove that in case sum of all the weights is m. the x* * I ( I
optimal solution. 6+5+6+ 3
a) Show how depth-first search works on the following graph;
considering the vertices in alphabetical order. {
Jb) Find the minimum spannitqpe using KniskaFs algorithm
c} Wriie down the Dijkstra's algorithm. (If you are mentioning any procedure (hen explain/write that procedure )
d) Write the recursive definition of weight and predecessor in the Floyd-
8) (5+5)+J0 a) Short note: Reductions, hncodingr
b) The clique problem t NP-complete." - I*ruvc it
|
Attachment: |
| Earning: Approval pending. |
