Scribd
Upload
84 views

DAA - ASSIGNMENT - Unit-3 Practice Questions

1. This document contains 16 questions related to algorithms and data structures. The questions cover topics like minimum spanning trees, fractional knapsack problem, convex hulls, shortest path algorithms, matrix multiplication, activity selection problem, binomial and Fibonacci heaps, skip lists, B-trees, and task scheduling. 2. Students are asked to solve each question through explanations, examples, and providing the steps/algorithms to solve problems presented in graphs or other representations. 3. The questions progress from simpler concepts like differentiating between Prim's and Kruskal's algorithms to more advanced topics such as Strassen's matrix multiplication, B-trees, and task scheduling.

Uploaded by

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

DAA - ASSIGNMENT - Unit-3 Practice Questions

1. This document contains 16 questions related to algorithms and data structures. The questions cover topics like minimum spanning trees, fractional knapsack problem, convex hulls, shortest path algorithms, matrix multiplication, activity selection problem, binomial and Fibonacci heaps, skip lists, B-trees, and task scheduling. 2. Students are asked to solve each question through explanations, examples, and providing the steps/algorithms to solve problems presented in graphs or other representations. 3. The questions progress from simpler concepts like differentiating between Prim's and Kruskal's algorithms to more advanced topics such as Strassen's matrix multiplication, B-trees, and task scheduling.

Uploaded by

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

SESSION: 2023-

ABES Engineering College, Ghaziabad 24


Department of Information Technology

DESIGN AND ANALYSIS OF


ALGORITHM CLASS/SEM:
(KCS 503) B.TechVth (ODD)
UNIT-III
Note: Write solution of each question in clear handwriting.
1 Differentiate between Prim’s and Kruskal’s algorithm. Explain Prim’s Algorithm and find
Minimum Spanning Tree of following graph.

2 Consider 5 items along with their respective weights and value


I= < I1, I2, I3, I4. I5>
W=<5,10,20,30,40>
V=<30,20,100,90,160>
The capacity of knapsack W=60. Find the solution to fractional knapsack problem.
3 What do you mean by convex hull? Describe an algorithm that solves the convex hull
problem.
4 When do Dijkstra’s and Bellman ford algorithm both failed to find a shortest path? Can
Bellman ford detect all negative cycles? Apply greedy single source shortest path algorithm on
following graph.

Solve This question using Strassen”s Matrix Multiplication Method.


6 Activity Selection Problem with algorithm and solve following problem
S= { a1,A2,A3,A4,A5, A6 }
Si = {5,1,3,0,5,8}
Fi = {9,2,4,6,7,9}
7 Write the algorithm of unite of two binomial heaps. Create a binomial heap for following
sequence: 8,3,5,18,2,12,7,9,16,11.21.

8 Write Short Notes on:


a.) Skip List
b.) Properties of Binomial Tree
c.) Tries
9 Consider the below graph:

Apply Bellman ford algorithm to find the shortest path.

10 Show the result of inserting the keys F, S, Q, K, C, L, H, T, V, W, M, R, N, P, A, B, X, Y, D, Z, E in


order into an empty b-Tree. use t=3, where t is the degree of B-tree.

11
Show the result of inserting the keys F, S, Q, K, C, L, H, T, V, W, M,
R, N, P, A, B, X, Y, D, Z, E in order into an empty b-Tree. use t=3,
where t is the minimum degree of B-tree.
12
What are the differences in Binomial and Fibonacci Heap?
Write down the algorithm for decrease key operation in
binomial heap also write its time complexity.
13 Explain Job Scheduling (Task Scheduling) with deadlines with suitable Example.
14 Discuss and write algorithm of Strassen Matrix Multiplication. Also, Discuss how Strassen
Matrix Multiplication is better than Standard
15 What is skip list? Explain the search operation in skip list with suitable example. Also write
its algorithm.
16 Discuss task scheduling problem with the help of greedy strategy and develop an algorithm
to solve the following problem. We are given 9 tasks T1, T2,…T9. The execution of each task
requires one unit time. We can execute one task at a time. Ti has a penalty Pi and a deadline
Di. Penalty Pi is paid if task is not completed before the end of the Di unit of time.
Task T1 T2 T3 T4 T5 T6 T7 T8 T9
Penalty 15 20 30 18 18 10 23 16 25
Deadline 7 2 5 3 4 5 2 7 3

You might also like