B.
TECH - CS
Assignment - 3
Semester-V (Odd), Session: 2023-24
KCS-503: Design and Analysis of Algorithm
Unit-3 Course Outcome: CO3 – Understand the
Unit-Name- Divide and Conquer , Greedy mathematical criterion for deciding whether
methods an algorithm is efficient, and know many
practically important problems that do not
admit any efficient algorithms.
Date of Distribution: 26/10/2023 Faculty Name: Mr. Vinay Singh
Sr. MANDATORY QUESTIONS B
L
1 Explain Divide and Conquer technique with the help of any one example. 1
2 Discuss linear search and binary search with the help of any one example. 2
3 Apply binary search to search for k=70 in the following array 3
<3,4,27,37,39,43,58,70,73,79,83,90,95>
4 Discuss Strassen’s algorithm for matrix multiplication. 2
5 Explain Convex hull problem with the help of any one example. 2
6 Define greedy algorithm with its characteristics. 1
7 What is minimum spanning tree ? 1
8 Explain Prim’s algorithm of MST with the help of any one example. 1
9 Differentiate between Kruskal and Prim’s algorithm of MST. 2
10 Elaborate knapsack problem using greedy approach with the help of any one example, 3
11 What is the time complexity of prim’s and Kruskal algo for finding MST? 1
12 Differentiate between greedy algorithm and dynamic programming. 2
13 For the given set of items and knapsack capacity of 10 kg find the subset of items to be 3
added to be added in the knapsack such that profit is maximum.
Items 1 2 3 4 5
Weights 3 3 2 5 1
Profit 10 15 10 12 8
14 What is knapsack problem ? 1
15 Differentiate between fractional knapsack problem and 0/1 knapsack problem. 2
16 Compare time complexities of linear search and binary search. 2
SUPPLEMENTARY QUESTIONS
1 Derive the time complexity of linear search and binary search. 3
2 Explain any one sorting technique using divide and conquer technique. 2
IQAC/ASU/F/2023-24/2.1 Page 1 of 2
REFERENCES
TEXT BOOKS:
Ref. Authors Book Title Publisher/Press Edition &Year of
[ID] Publication
E. Horowitz & Fundamentals of Computer Galgotia
[T1] 2nd Edition, 2008
S Sahni Algorithms Publication
[T2] Corman Introduction to Algorithms MIT Press 3rd Edition,2009
REFERENCE BOOKS:
Ref. Edition &Year of
Authors Book Title Publisher/Press
[ID] Publication
Aho, Hopcraft, The Design and Analysis of Pearson
[R1] Ist Edition, 2002.
Ullman Computer Algorithms Education
Signature of Faculty:______________ Signature of HOD:_______________
(With Date) (With Date)
IQAC/ASU/F/2023-24/2.1 Page 2 of 2
