Cochin University of Science and Techology (CUST) 2005-7th Sem B.Tech Computer Science and Engineering (Supplementary) , , CS 703 Analysis And Design Of Algorithms - Question Paper
B.Tech. Degree VII Semester (SpecialSupplementary)
Examination, May 2005
CS 763 ANALYSIS AND DESIGN OF ALGORITHMS
(1999 Admission*
Time: 3 Hour* Maximum Marla: 100
I (a) Defrte Big-Ob (0)aad Omega ootatkroincd to measure rime complexity. (10) (b) Design ted ten an algorithm to determine how long it tak a computer to evaluate 2". (10)
OR
II (a) Define wbM is time aod sp&cc complexity. (8) (b) Solve the following equations to find asymptotic opper bound:
0) vC~) - fi.r((%J) + 4i w
M. (a) Develop ao algorithm to Aod the upper anctlower bouods to heap sort. (3)
(b) Compare heap sort and qcick sort alforithnu based oa complexity. (12)
OR
IV. Explais the Binary Search algorithm aod derive in worn cac, best case tod average
case rune complexity. (20)
V. Defioe spending tree. Cxplain an algunihan k> fi*d minimum con pinium trw.
Wbai ace (be application* of mininuuu (tpMiog tree? (20)
OR
VL (a) fixplam different method* of tree travercils. (10)
(b) Dexcribc an algorithm for checking strongly connected components of a graph. (10)
VII. (a) What we optimal bina> search trees? Explain ttx compkMty. (10) (b) Explain uac of Dyeamk programming aod whit ia dynamic programming? (10)
OR
VIII. (a) ?rovc that the maximum number of node* of a binary tree of dqKh **4 ii 2*-l. (10) (b) What d greedy algorithm aod define. Whtf are B-iree*? (10)
IX. (a) What ia NP>bsrd problem'/ lixplam gnph cukviag. }
(b) Explain traveling taletroart problem. } (30)
OR
X (a) Show that 3 utnfubtlity i KP complete (1)
(h) Show that the 3 CoCOR is NP complete. Define wbtt is k-colormg (10)
|
Attachment: |
| Earning: Approval pending. |
