1 hour
Introduction video
This experiment requires you to have basic knowledge about :
And above all, a curiosity to learn and explore..!
In this experiment, you will be able to do the following:
Module | Weightage | Expectation |
---|---|---|
Pre-test | 10% | Solve All Questions |
Split | 20% | Practice how to recursively split arrays |
Merge | 20% | Practice how to merge sorted arrays |
Mergesort | 30% | Practice the full algorithm |
Post-test | 20% | Solve all Questions |
10 minutes
Given a list of random numbers, sorting means ordering the numbers in either ascending or descending order. By default, we sort numbers in an ascending order.
Trees are hierarchical data structures.
Q1. Which of these best describes an array?
(A) A data structure that shows a hierarchical behavior
(B) Container of objects of similar types
(C) Container of objects of mixed types
(D) All of the mentioned
An array is a data structure, which can store a fixed-size collection of elements of the same data type.
Q2. Write complexity of insertion at any point on an array:
(A) O(N)
(B) O(N^2)
(C) O(NLogN)
(D) None of these
Taking a general example,inserting into the middle of an array, you have to shift all the elements after that element, so the complexity for insertion in that case is O(n). Worst case would be when you have to insert at the starting of the array,you will need to move n elements.
Q3. What does it mean when we say that an algorithm X is asymptotically more efficient than Y?
(A) X will always be a better choice for small inputs
(B) X will always be a better choice for large inputs
(C) Y will always be a better choice for small inputs
(D) X will always be a better choice for all inputs
Performance could be similar for small inputs, but definitely better for larger inputs
Q4. int a = 0, b = 0;
for (i = 0; i < N; i++) {
a = a + rand();
}
for (j = 0; j < M; j++) {
b = b + rand();
}
What is the time and space complexity for the above code?
(A) O(N * M) time, O(1) space
(B) O(N + M) time, O(N + M) space
(C) O(N + M) time, O(1) space
(D) O(N * M) time, O(N + M) space
The first loop runs for O(n) time, second loop runs for O(m). Constant extra space is used for 2 variables a and b, hence O(1) space.
15 minutes
Introduction video to d&c
In this module, we will learn about :
Divide and conquer is a strategy based on the idea that a given hard problem can be solved by breaking it down into smaller subproblems, which are much easier to solve. A Divide and Conquer algorithm works by recursively breaking down a problem into two or more sub-problems of similar type, until these become simple enough to be solved directly.
The solutions to the sub-problems are then combined to give a solution to the original problem. A typical Divide and Conquer algorithm solves a problem using following three steps:
We can visualise sorting an array of size N as two subproblems : sorting two arrays of size N/2, and then somehow combining the two smaller sorted arrays. Sorting a smaller array will be easier than sorting the bigger array.
Recursive nature of Sorting : Sorting an array of size N can be recursively broken down into sorting two smaller arrays of N/2, and each of these smaller arrays can be broken down into even smaller arrays of size N/4 each, and so on.
Merge sort is a sorting algorithm that uses this approach. In Merge Sort we will :
10 minutes
The split step is described here
In this module, we will :
In this case, we will
recursively split our array
A into two equal or nearly
equal parts.
Given an array with starting
index START and ending index
END, we will find the
midpoint :
After finding the MID, we then split the array into two subarrays :
Interactive artefact where user can click on Next Step or Previous Step to understand how the array splits at different levels
Interactive artefact where user can split the array by providing the indices where the array needs to be split at each step.
10 minutes
merge step video
In this module, we will :
Our objective is to merge two sorted subarrays, say array[p..q] and array[q+1..r] and have the result in array[p..r].
For this we first need to make temporary arrays and copy array[p..q] and array[q+1..r] into these temporary arrays, as we can't write over the positions in array[p..r] until we have the elements originally in array[p..q] and array[q+1..r] safely copied.
Let's say we denote the temporary arrays by Subarray1[] and Subarray2[] and copy all the elements in array [p..q] into Subarray1, and all the elements in array[q+1..r] into Subarray2.
The next immediate question is how big should Subarray1 and Subarray2 be?
Now in order to merge the arrays, we assign pointers to the starting index of all the three arrays: Pointer1, Pointer2 and Pointer3
In the example shown above, the merge process is at an intermediate step. Currently Pointer1 points to 48 and Pointer2 points to 65. As Pointer1 points to the lesser element (48 < 65), that number is selected and added to the merged array. Finally, both Pointer1 and Pointer 3 are moved one step ahead as shown in the figure.
Interactive artefact where user can click on Next Step or Reset to understand how the arrays merge at different levels.
Interactive artefact where user can split the array by providing the indices where the array needs to be split at each step
10 minutes
mergesort video
In this module, we will :
Merge sort animation
Tree representation of the whole process
Interactive artefact where user can practise mergesort
20 minutes
time complexity is explained
In this module, we will be learning about :
Lets assume that we are sorting n elements of a given array.
The total time for mergesort is the sum of the merging times for all the levels. If there are L levels in the tree, then the total merging time is L * cN.
So what is L? We start with subproblems of size N and repeatedly halve until we get down to subproblems of size 1.
While merging two arrays, we require an auxillary space to temporarily store the merged array, before we plug this partially sorted array into the main array. Hence space complexity of Merge Sort is O(N), as we require an auxillary array as big as the main input array.
A Comparison Sort is a sorting algorithm where the final order is determined only by comparisons between the input elements.
In Merge Sort, the merge procedure chooses an item from one of two
arrays after comparing the top items from both arrays.
Hence we
can say that Merge Sort is a Comparison Sort algorithm.
A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input unsorted array. For example, look at the picture below. The unsorted array has two elements with value 23. Note the order of both these elements in the stable and unstable sorted arrays.
Yes, merge sort is a stable sorting algorithm. Look at the picture below and keep and eye out for the ordering of 23 and 23*. Note how the original order of these elements is retained throughout the sorting process. The relative positioning of 23 and 23* does not change in the sorted output.
Algorithm | Time | Features | |||
---|---|---|---|---|---|
Sort | Average | Best | Worst | Space | Stability |
Bubble sort | O(n^{2}) | O(n^{2}) | O(n^{2}) | Constant | Stable |
Modified Bubble sort | O(n^{2}) | O(n) | O(n^{2}) | Constant | Stable |
Selection Sort | O(n^{2}) | O(n^{2}) | O(n^{2}) | Constant | Stable |
Insertion Sort | O(n^{2}) | O(n) | O(n^{2}) | Constant | Stable |
Heap Sort | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) | Constant | Unstable |
Merge Sort | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) | Depends | Stable |
Quicksort | O(n*log(n)) | O(n*log(n)) | O(n^{2}) | Constant | Stable |
10 minutes
Post Test includes questions on entire experiment concepts. Read the questions in the quiz section and select the correct option from the ones provided. Please note that some questions may have more than one correct response.
Q1. What are the sizes of the sub-arrays when you split an array of size 5?
(A) 1,4
(B) 2, 3
(C) Unknown sizes
(D) Insufficient information
mid=(5+1)/2=3. So array is divided after index 3 and split into two subarrays with length 3 and 2.
Q2. What is the size of the merged array when you merge two arrays of size 3 each?
(A) 3
(B) 6
(C) 7
(D) Insufficient information
Let Array A have 2 elements and Array B have 3.Consider this sequence of sending elements into the merged array: B,A,B,A,B. Number of comparisons is 4 as the last element just goes into the merged array.
Q3. What is the best case complexity of merge sort?
(A) O(n log n)
(B) O(n)
(C) O(log n)
(D) O(n2)
The merged array is simply a combination of the two subarrays.Total elements=3+3=6
Q4. Which is false for Mergesort?
(A) The algorithm is recursive
(B) The algorithm requires extra storage for a temporary copy.
(C) The invariant is that after each merge one more element is in its final position.
(D) It is not an in-place sorting algorithm.
The mergesort algorithm always has nlogn complexity irrespective of input.
Q5. Which of the following sorting algorithms has the lowest worst-case complexity?
(A) Merge Sort
(B) Bubble Sort
(C) Quick Sort
(D) Selection Sort
(E) A,C
The statement is not necessarily true in all cases.
Q6. Which of the following sorting algorithms, which has a running time that is least dependent on the initial ordering of the input?
(A) Merge Sort
(B) Insertion Sort
(C) Selection Sort
(D) Quick Sort
Rest of the sorting algorithms have O(n^2) worst case sorting complexity but mergesort remains O(nlogn) in all cases.
Q7. In a modified merge sort, the input array is splitted at a position one-third of the length(N) of the array. What is the worst case time complexity of this merge sort?
(A) N(logN base 3)
(B) N(logN base 2/3)
(C) N(logN base 1/3)
(D) N(logN base 3/2
Recurrence relation : T(N) = T(N/3) + T(2N/3) + N. Assume a tree here.n divided in to n/3 and 2n/3. n/3 is divided into n/9 and 2n/9 ( this tree goes on the left side and vanishes to 1 element) 2n/3 is divided into 2n/9 and 4n/9 ( here 4n/9 part grows even after left side has vanished) The time complexity will be based on the deepest branch of the tree. and the elements in that branch go like n/(3/2) -- n/(3/2)^2 -- n/(3/2)^3 -- ..... 1 Solving the above equation we get n * logn/log(3/2) = n logn(base 3/2). As each level requires an O(n) merge and there are logn(base 3/2) levels in the deepest branch
The experiment ends here,thanks for participating..! Please fill in the form.
You can explore more about Mergesort Experiment through following resources:
Some more concept :
Quizzes :
References and Credits :