Scribd
Upload
3 views1 page

Algorithms Assignment: Sorting & Complexity

Uploaded by

Kunal k
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 views1 page

Algorithms Assignment: Sorting & Complexity

Uploaded by

Kunal k
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

Design and Analysis of Algorithms – Assignment 1

1. Differentiate between stable and unstable sorting algorithms with examples.


2. Explain Time-Space Tradeoff in algorithms. Give one practical example where
using extra memory reduces execution time.
3. Solve the recurrence relation using Master’s Theorem: T(n) = 5T(n/5) + 2n.
Find the asymptotic complexity of T(n).
4. Write pseudo code for Merge Sort using divide-and-conquer strategy.
5. Solve the recurrence relation, T(n) = 3T(n/3) + n^2, T(1) = 1, using the
Recursion Tree method.
6. Insert the elements 22, 18, 35, 9, 15, 28, 40 into a Max Heap. Show the heap
after each insertion.
7. Apply Shell Sort on the numbers 33, 17, 29, 12, 41, 8, 21. Display the array
after each pass.
8. For the function f(n) = 10n^3 + 7n^2 + 20, prove that: - f(n) = O(n^3) - f(n) =
Ω(n^3) - f(n) = Θ(n^3)
9. Explain the properties of a Red-Black Tree. How does it maintain balance and
why is it preferred over a simple Binary Search Tree?
[Link] Best, Average, and worst-case complexities of selection sort, quick
sort, merge sort, shell sort, and heap sort in the form of a table.

You might also like