Scribd
Upload
9 views1 page

Algorithms Assignment 1

The document outlines an assignment with multiple questions related to searching algorithms and sorting techniques. It includes tasks such as determining the maximum comparisons in binary and quaternary searches, choosing between QuickSort and Merge Sort in a memory-constrained environment, analyzing pivot selection efficiency in QuickSort, sorting specific functions, and proposing a modified ternary search for a uniquely structured array. Each question is assigned a specific point value, indicating their importance in the assignment.

Uploaded by

abror.mahir
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
9 views1 page

Algorithms Assignment 1

The document outlines an assignment with multiple questions related to searching algorithms and sorting techniques. It includes tasks such as determining the maximum comparisons in binary and quaternary searches, choosing between QuickSort and Merge Sort in a memory-constrained environment, analyzing pivot selection efficiency in QuickSort, sorting specific functions, and proposing a modified ternary search for a uniquely structured array. Each question is assigned a specific point value, indicating their importance in the assignment.

Uploaded by

abror.mahir
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

Faculty: MZG
1. You are given a sorted array of 8000 unique integers and you need to search for the target
number 4561. ​​ ​ ​ ​ ​ ​ ​ ​ ​ [2.5+2.5]
a. What is the maximum number of comparisons needed in binary search in the worst case?
b. What is the maximum number of comparisons in quaternary search (i.e., splitting into 4
parts)?

2. Suppose you are working in a resource-constrained environment where memory is very


limited, and you must sort a huge dataset. You have the choice between QuickSort and Merge
Sort. Which one should you choose, and why? Consider both time and space complexities in
your answer. ​ ​ ​ ​ ​ ​ ​ ​ [2.5]

3. You have decided to implement Quick Sort using the first element of the array as the pivot to
sort a dataset. Will this pivot selection approach be efficient for an already sorted or nearly sorted
array? Explain your reasoning in detail. ​​ ​ ​ ​ ​ ​ [2.5]

4. Sort the following functions in ascending order: [5]


f1 = n2logn, ​ f2 = n4/5, ​ f3 = nlogn

5. You have an array where the left subarray is in strictly decreasing order and the right subarray
is in strictly increasing order. Propose a modified version of your ternary search algorithm. [5]

You might also like