Question $1$: Which factor results in the difference between the average and worst case

efficiencies of quick sort? $(10$ points$)$

Question $2$: Let $A$ be a collection of objects. Describe an efficient method for converting A into a

set. That is$,$ remove all duplicates from $A.$ What is the running time of this method? $(10$ points$)$

Question $3$: Suppose we are given two $n-$element sorted sequences A and $B$ that should not be

viewed as sets $($that is$,$ A and $B$ may contain duplicate entries$).$ Describe an $O(n)-$time method

for computing a sequence representing the set $AB($with no duplicates$).(10$ points$)$

Question $4$: For each of the following questions, trace the time taken by your programs $($i$.$e$.,$

plot the time vs$.$ input$-$size graph$).$ You can choose a language of your choice. Briefly discuss

how do your experimental results compare with the theoretical algorithm analysis $($i$.$e$.,$ the

best$-$case and worst$-$case discussions$)$ that was studied in the class.

A$)$ Difference between Linear Search and Binary Search running times: Implement the

linear search and the binary search algorithms in a language of your choice. $(15$ points$)$

B$)$ Difference between Bubble Sort and Quick Sort running times: Implement the bubble

sort and the quick sort algorithms in a language of your choice. $(15$ points$)$

C$)$ Implementing Merge Sort on Linked Lists: Convert your list$/$array sequence that you

used as the input for the above sorting algorithms into the linked list format. Implement

the merge sort algorithm on this linked list. $(15$ points$)$

Create a list or an array comprising numbers from $1$ to $n,$ where $n$ is the input size. You can use

an inbuilt function to generate the above$-$mentioned list of numbers. You need to generate

your list in the following ways: $(25$ points$)$

I$)$ The list should be sorted in non$-$decreasing order.

II$)$ The list should be sorted in non$-$increasing order.

III$)$ The list should contain numbers in a random order.

For the searching algorithms, randomly select a number within or outside the generated list,

which will be used as the input number that needs to be searched.

Run your experiments for input size $n=1,10,100,1000,10000,100000.$ Also, for each input

size, run each of the codes a number of times, say $5$ or $10$ times, and take the average of the

running time over all those runs. Then, use this average number in your graph plot. $($Taking the

average time over multiple runs ensures that your time recordings are independent of any

interruptions caused by background services that may be running on your machines.$)$

Your outputs should comprise of the "input vs$.$ time" graph for each of the three

implementations $A,$ and $C)$ mentioned above. Additionally, within each implementation,

you need to show plots corresponding to the different data generation methods I$),$ II$),$ and III$)$

mentioned above. You can use a language's built$-$in functions to record the running time of a

program.

The goal of this question is to understand, through experimental analysis, how different inputs

can affect the performance of different searching and sorting algorithms.

Question $1$: Which factor results in the difference between the average and worst case

efficiencies of quick sort? $(10$ points$)$

Question $2$: Let $A$ be a collection of objects. Describe an efficient method for converting A into a

set. That is$,$ remove all duplicates from $A.$ What is the running time of this method? $(10$ points$)$

Question $3$: Suppose we are given two $n-$element sorted sequences A and $B$ that should not be

viewed as sets $($that is$,$ A and $B$ may contain duplicate entries$).$ Describe an $O(n)-$time method

for computing a sequence representing the set $AB($with no duplicates$).(10$ points$)$

Question $4$: For each of the following questions, trace the time taken by your programs $($i$.$e$.,$

plot the time vs$.$ input$-$size graph$).$ You can choose a language of your choice. Briefly discuss

how do your experimental results compare with the theoretical algorithm analysis $($i$.$e$.,$ the

best$-$case and worst$-$case discussions$)$ that was studied in the class.

A$)$ Difference between Linear Search and Binary Search running times: Implement the

linear search and the binary search algorithms in a language of your choice. $(15$ points$)$

B$)$ Difference between Bubble Sort and Quick Sort