Introduction to Algorithm Design
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.
