KEMBAR78
DAA Assignment | PDF | Computer Science | Mathematical Relations
Scribd
Upload
57 views3 pages

DAA Assignment

This document discusses analyzing the time complexities of various algorithms including recurrence relations, nested loops, sorting algorithms like merge sort and quick sort, Strassen's matrix multiplication, minimum spanning tree algorithms like Kruskal's and Prim's, data structures for implementing Kruskal's algorithm, comparing union-find operations in sets implemented with linked lists vs trees, designing algorithms for shortest paths, convex hulls, optimally merging sorted files, the knapsack problem, making change with coins using greedy and dynamic programming approaches, and defining asymptotic notations, time/space complexities, and priority queues.

Uploaded by

Sairam N
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
57 views3 pages

DAA Assignment

This document discusses analyzing the time complexities of various algorithms including recurrence relations, nested loops, sorting algorithms like merge sort and quick sort, Strassen's matrix multiplication, minimum spanning tree algorithms like Kruskal's and Prim's, data structures for implementing Kruskal's algorithm, comparing union-find operations in sets implemented with linked lists vs trees, designing algorithms for shortest paths, convex hulls, optimally merging sorted files, the knapsack problem, making change with coins using greedy and dynamic programming approaches, and defining asymptotic notations, time/space complexities, and priority queues.

Uploaded by

Sairam N
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/ 3

1.

Analyze the time complexity of the following recurrence relations (CO1) (K4)

a)T(n) = { 3T(n-1), if n>0,

{ 1, otherwise

b)T(n) = { 2T(n-1) - 1, if n>0,

{ 1, otherwise

2. Analyze the time complexity of the below program (CO1) (K4)

void function(int n)

int count = 0;

for (int i=n/2; i<=n; i++)

for (int j=1; j<=n; j = 2 * j)

for (int k=1; k<=n; k = k * 2)

count++;

3. Analyze of the time complexities of Merge Sort, Quick Sort, Heap Sort (CO1) (K4)

4. Analyze the time complexity of Strassen’s matrix multiplication (CO1) (K4)

5. Compare Kruskal's and prim's algorithm for finding Minimum Spanning Tree of a Graph. What
makes Kruskal's algorithm faster than Prim's algorithm?(CO2). (K4)

6. What is a Minimum cost spanning tree? Identify an efficient data structure for
implementation of KRUSKAL’s Algorithm for the connected Weighted Graph. (CO2) (K4)
7. Compare the efficiencies of union and find operations in implementing Sets using linked lists and
versus implementing Sets using trees. (CO2) (K4)

8. Design an algorithm to find minimum cost path from s to t in the multistage graph given below.
(CO4) (K6) 1
3
4 7
4 7
2 6
5
6
9
3
1 5 2
5 3
2 8
3
6 1

8 6
2

9. Design an algorithm to find all pairs shortest path for the given graph (CO4) (K6)

9. Design an algorithm to find convex hull (CO4) (K6)

10. Design an algorithm to merge ‘n’ sorted files optimally. (CO4) (K6)

11. Design a greedy algorithm to solve Knapsack problem. (CO4) (K6)

12. You are working at the cash counter at a fun-fair, and you have different types of coins available
to you in infinite quantities. The value of each coin is already given. Can you determine the optimal
way of making change for a particular number of units X using the given types of coins so that the
number of coins is minimum? Solve this problem using Greedy technique. Given an example set of
denominations and X show that the greedy method does not give us an optimal solution. Solve this
using Dynamic programming approach (CO4) (K6)

13. Define asymptotic notations


14. Define time and space complexities

15. Define priority queue

You might also like