Introduction to Algorithm Design
Q1. List the following functions according to their order of growth from the lowest to the highest. Prove the accuracy of your ordering. (20 points)
Note: Your analysis must be rigorous and precise. Merely stating the ordering without providing any mathematical analysis will not be graded!
a) 5n
b) n
c) ln3(n)
d) (n2)!
e) (n!)n
Q2. Consider an array consisting of integers from 0 to n; however, one integer is absent. Binary representation is used for the array elements; that is, one operation is insufficient to access a particular integer and merely a particular bit of a particular array element can be accessed at any given time and this access can be done in constant time. Propose a linear time algorithm that finds the absent element of the array in this setting. Rigorously show your pseudocode and analysis together with explanations. Do not use actual code in your pseudocode but present your actual code as a separate Python program. (20 points)
Propose a sorting algorithm based on quicksort but this time improve its efficiency by using insertion sort where appropriate. Express your algorithm using pseudocode and analyze its expected running time. In addition, implement your algorithm using Python. (20 points)
Solve the following recurrence relations
a) xn = 7xn-1-10xn-2, x0=2, x1=3 (4 points)
b) xn = 2xn-1+xn-2-3xn-3, x0=2, x1=1, x2=4 (4 points)
c) xn = xn-1+2n, x0=5 (4 points)
d) Suppose that an and bn are both solutions to a recurrence relation of the form xn=αxn-1+βxn-2. Prove that for any constants c and d, can+dbn is also a solution to the same recurrence relation. (8 points)
A group of people and a group of jobs is given as input. Any person can be assigned any job and a certain cost value is associated with this assignment, for instance depending on the duration of time that the pertinent person finishes the pertinent job. This cost hinges upon the person-job assignment. Propose a polynomial-time algorithm that assigns exactly one person to each job such that the maximum cost among the assignments (not the total cost!) is minimized. Describe your algorithm using pseudocode and implement it using Python. Analyze the best case, worst case, and average-case performance of the running time of your algorithm. (20 points)
