Description
1)
Apply insertion sort to the following sample array:
Array={6,5,3,11,7,5,2}
Show each step of the algorithm. At each step, you are required to not only create the arrray
with its new order, but also explain why you created that sequence.
2) What is the time complexity of the following programs? Explain in detail by providing your
reasoning.
a)
function(int n){
if (n==1)
return;
for (int i=1; i<=n; i++){
for (int j=1; j<=n; j++){
printf(“*”);
break;
}
}
}
b)
void function(int n)
int count = 0;
for (int i=n/3; i<=n; i++)
for (int j=1; j+n/3<=n; j = j++)
for (int k=1; k<=n; k = k * 3)
count++;
}
3) We have an unordered array in which we are looking for pairs whose multiplication yields
the desired numbers. For example, let our array be {1,2,3,6,5,4} and let the desired number
be 6. In this case, our pairs will be (1,6) and (2,3). Provide an algorithm that solves this problem
with time complexity O(n(logn)). Express your algorithm as pseudocode (write actual code
using Python) and prove that its complexity is O(n(logn)).
4) You are given a binary search tree (BST) with n nodes. You are required to merge this tree
with another n-node BST. What is the time complexity of this process? Explain in detail by
providing your reasoning.
5) Suppose that you are given two arrays, where one of them is larger than the other one.
Propose a linear time algorithm that finds, if exists, the elements of the small array in the big
array. Express your algorithm using pseudocode and calculate the worst case complexity of
the algorithm.
