Scribd
Upload
10 views1 page

Assignment Module 1 2 3

The document outlines various algorithmic concepts, including properties of monotonically increasing functions, the running time analysis of quick sort, and the implementation of sorting algorithms like Merge Sort and Quick Sort. It discusses the importance of algorithm analysis, including worst, best, and average case complexities, as well as the divide and conquer approach. Additionally, it covers sorting techniques such as Radix sort and Counting sort, and explores binary search trees and their traversals.

Uploaded by

bobyroy.araria
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
10 views1 page

Assignment Module 1 2 3

The document outlines various algorithmic concepts, including properties of monotonically increasing functions, the running time analysis of quick sort, and the implementation of sorting algorithms like Merge Sort and Quick Sort. It discusses the importance of algorithm analysis, including worst, best, and average case complexities, as well as the divide and conquer approach. Additionally, it covers sorting techniques such as Radix sort and Counting sort, and explores binary search trees and their traversals.

Uploaded by

bobyroy.araria
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

1.

Show that if f(n) and g(n) are monotonically increasing functions, then so are the
functions f(n) + g(n) and f(g(n)), and if f(n) and g(n) are in addition nonnegative,
then f(n) * g(n) is monotonically increasing.
2. Show that the running time of quick sort when array A contains distinct elements
and is sorted in decreasing order. Also discuss best case running time for quick
sort.
3. Write the Merge Sort Algorithm to sort the following numbers 12, 14, 25, 27, 11,
12, 13, 16. Illustrate the algorithm.
4. Write an algorithm to sort the given array of elements using QUICKSORT. Apply
Quick-Sort algorithm to sort the following array 5, 8, 1, 3, 6, 9, 2, 4. Analyze the
running time of the algorithm in Best case also.
5. Explain why analysis of algorithms is important? Explain: Worst Case, Best Case
& Average Case Complexity.
6. Write an algorithm for quick sort and derive best case, worst case using divide
and conquer technique using given data (3, 12, 1, 6, 8, 1, 4, 5, 9, 2, 6, 5).
7. Explain the working of divide & conquer approach with example.
8. What are the general characteristics of Dynamic programming approach?
9. Explain the asymptotic notations? How growth of function is useful to explain
such notations?
10. Perform Radix sort on the following elements: 327, 869, 523, 677, 123, 150.
11. Perform Counting sort on the following elements: 2, 5, 3, 0, 2, 3, 0, 3.
12. What is a binary search tree? Given preorder traversal sequence of a binary
search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Find the post order traversal
sequence of the same tree.
13. What do you understand by divide and conquer technique? Write pros and cons
of Merge Sorting. Illustrate the merge sort algorithm with example in detail.
14. Differentiate between full and complete binary tree with examples?
15. How you will analyze the performance of an algorithm in different cases? Analyze
the following For Loop and give its complexity.

You might also like