Scribd
Upload
3 views

Daa Assignment

The document outlines an examination for the Design and Analysis of Algorithms course at Chaitanya Bharathi Institute of Technology, detailing various algorithm-related questions. It includes tasks such as determining frequency counts, asymptotic notation, time complexity analysis, and solving specific algorithmic problems like the 0/1 knapsack problem and minimum cost path for TSM. The exam is scheduled for March 13, 2025, with a submission deadline of March 18, 2023.

Uploaded by

abhireddie65
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views

Daa Assignment

The document outlines an examination for the Design and Analysis of Algorithms course at Chaitanya Bharathi Institute of Technology, detailing various algorithm-related questions. It includes tasks such as determining frequency counts, asymptotic notation, time complexity analysis, and solving specific algorithmic problems like the 0/1 knapsack problem and minimum cost path for TSM. The exam is scheduled for March 13, 2025, with a submission deadline of March 18, 2023.

Uploaded by

abhireddie65
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

CHAITANYA BHARATHI INSTITUTE OF TECHNOLOGY (A)

Gandipet, Hyderabad -75


Asmt 1 – Examination Date: 13.03.2025 Deadline: 18.03.2023
SEMESTER: IV B.E. (Department of Information Technology)

SUBJECT: Design and Analysis of Algorithms (22CSC14)


Max. Marks: 10

Answer ALL questions. All parts of the questions must be answered at one place only
SECTION – A
1 Determinethe frequencycountsfor allstatementsin the following two CO1 BL3
Algorithmsegments
fori :=1to n do : i = 1;
forj :=1to ido: while (i ≤ n) do{
fork :=1to jdo : x= x + 1;
x :=x+1; i = i + 1;
}
(a) (b)
2 Notate following functions using asymptotic Notations. CO1 BL3
i) 2n22n +nlognii) n2n+ 6 * 2n
iii)10n3+ 15n4+100 n22niv) n! + nn + logn
3 Find the time complexity of function T(n) = 2T(n/2) + n using Masters CO1 BL3
3

theorem

4 a) Write Control abstraction for Divide and Conquer method CO1 BL2
b) Explain Theta Ɵ Notation using example CO1 BL2

5 Write an algorithm to perform Matrix multiplication of size n x n and CO1 BL3


analyze time complexity using frequency count method.

6 Explain the Master's Theorem for solving recurrence relations of decreasing CO1 BL3
function and write complexity for T(n) = 2T(n-2) + nlogn

7. Solve the following 0/1 knapsack problem to fill a bag with 4 objects in which
capacity of the bag 8 and (p1,p2,p3,p4)={1,2,5,6) (w1,w2,w3,w4)={2,3,4,5} CO2 BL2

8. Differentiate Greedy approach and Dynamic approach of solving problems. CO2 BL2

9. Identify compressed bits when we transfer message


“AAABBBBCTTTTHHHHYYY” using Huffman Code algorithm

10. Find out Minimum Cost and Path for TSM.

You might also like