Scribd
Upload
24 views5 pages

Algorithms and Data Structures Assignments

The document outlines a series of assignments covering various topics in algorithms and data structures, including recurrence relations, asymptotic notation, time complexity of Merge sort, properties of binomial trees, B-trees, Skip lists, divide and conquer techniques, greedy algorithms, Red-Black Trees, and shortest path algorithms. Each assignment poses specific questions and problems to solve, such as deriving time complexities, inserting keys into trees, and applying algorithms like Dijkstra's and Prim's. The assignments aim to deepen understanding of algorithmic concepts and their practical applications.

Uploaded by

Divyansh Goel
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
24 views5 pages

Algorithms and Data Structures Assignments

The document outlines a series of assignments covering various topics in algorithms and data structures, including recurrence relations, asymptotic notation, time complexity of Merge sort, properties of binomial trees, B-trees, Skip lists, divide and conquer techniques, greedy algorithms, Red-Black Trees, and shortest path algorithms. Each assignment poses specific questions and problems to solve, such as deriving time complexities, inserting keys into trees, and applying algorithms like Dijkstra's and Prim's. The assignments aim to deepen understanding of algorithmic concepts and their practical applications.

Uploaded by

Divyansh Goel
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

ASSIGNMENT-1

[Link] is recurrence relation? How is a


recurrence solved using master’s
theorem?

[Link] is asymptotic notation? Explain


Omega (Ω) notation?

[Link] the time complexity of Merge


sort.
ASSIGNMENT-2

[Link] down the properties of binomial


tree.

[Link] the results 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.

[Link] Skip list and its operations.


ASSIGNMENT-3

[Link] searching technique using divide


and conquer approach.

[Link] Skip list in brief.


[Link] greedy approach to an activity
selection problem of scheduling several
competing activities. Solve following
activity selection problem
S = {A1, A2, A3, A4, A5, A6, A7, A8, A9,
A10}
Si = {1, 2, 3, 4, 7, 8, 9, 9, 11, 12}
Fi = {3, 5, 4, 7, 10, 9, 11, 13, 12, 14}
ASSIGNMENT-4

[Link] an algorithm for insertion of key in


the Red-Black Tree. Discuss the various
cases for insertion of key in red-black tree
for given sequence of key in an empty red-
black tree- 5, 16, 22, 25, 2, 10, 18, 30, 50,
12, 1.

[Link] down the Bellman Ford algorithm to


solve the single source shortest path
problem with example.

[Link] the recurrence T (n) = 4T(n/2) + n2


ASSIGNMENT-5

[Link] are single source shortest paths?


Write down Dijkstra’s algorithm for it.

[Link] the properties of binomial trees.

3. Generate MST for the following graph


using Prim’s algorithm.

You might also like