[SOLVED] CSE 310:   Homework #2 

Objectives: Objective of this homework is to reinforce main concepts related to asymptotic analysis, recurrences and solving recurrences, compare and contrast algorithm performances (theoretically and practically) discussed in the class and apply algorithm analysis/design technique in solving a new problem

Note:  This an individual submission and no-collaboration expected.

Submission: Prepare a PDF document called homework2.pdf that contain answers to all the 4 questions above and submit online to the canvas.

1. [35 Pts] Recurrence, Master Theorem, and Recursive Tree:

1. [25 Pts] Consider the following recurrence and answer the questions given below

T(n)= 4T(n/2) +  5n²

• a) How many sub problems are in the above recurrence?
  1. What the size of each of the sub problems identified above?
  2. What is the work/time needed for non-recursive part (divide and

combine) of the               recurrence?

• Use the recursive tree technique to obtain the running time (time complexity) of the above recurrence?

• Use the mater theorem to determine the time complexity of the above recurrence.

1. (10 points) Suppose that we have two algorithms A1 and A2 for solving the same problem. Let T1(n) be the worst-case time complexity of A1 and T2(n)

be the worst-case time complexity of A2. We know that

  T₁(1) = 1                                                       T₂(1) = 1

 T₁(n) = 15 T₁(n/2)+ n²,  n>1                       T₂(n) = 80 T₂(n/3) + 20 n³,  n>1.

• Use the master method to get the running time for T₁(n).
• Use the master method to get the running time for T₂(n).
• Which algorithm is more efficient? Why?

Submission: Make a PDF file named hw2q1.pdf with your answers to question 1

2. [20 Pts] Algorithm Analysis Question: The QUICKSORT algorithm of section 7.1 of the textbook contains two recursive calls to itself. After the call to PARTITION, the left subarray is recursively sorted. The second recursive call in QUICKSORT is not really necessary; it can be avoided by using an iterative control structure. This technique, called tail recursion, is provided automatically by good compilers. Consider the following version of quicksort, which simulates tail recursion.

QUICKSORT’ (A, p, r)

• while p < r
• do Partition and sort left subarray
• q ← PARTITION (A, p, r )
• QUICKSORT’ (A, p, q – 1)
• p ← q + 1

1. Argue that QUICKSORT’ (A, 1, length [A]) correctly sorts array A.

Compilers usually execute recursive procedures by using a stack that contains pertinent information, including the parameter values, for each recursive call. The information for the most recent call is at the top of the stack, and the information for the initial call is at the bottom. When a procedure is invoked, its information is pushed onto the stack; when it terminates, its information is popped. Since we assume that array parameters are represented by pointers, the information for each procedure call on the stack requires O (1) stack space. The stack depth is the maximum amount of stack space used at any time during a computation.

1. Describe a scenario in which the stack depth of QUICKSORT’ is Θ (n) on an n-element input array
2. [30 Pts] Heap and the Heap Sort: Consider the following array A.

A = {34, 67, 1, 4, 34, 89,100, 32, 23, 78}

1. Array A is not a heap. Clearly explain why does above tree not a heap?

1. Using build heap procedure discussed in the class, construct the heap data structure from the array A above. Represent your heap in the array A as well as using a binary tree. Clearly show all the steps

1. Show how heap sort work in the heap you have constructed in part (b) above. Clearly show all the step in the heap sort

4.   [15 Pts] Problem Solving and Algorithm Design

Consider the following scenario and then develop an algorithm that uses divide and conquer to solve it

1. Suppose you have 9 coins and one of them is heavier than others. Other 8 coins weight equally. You are also given a balance. Develop and algorithm to determine the heavy coin using only two measurements with the help of the balance. Clearly write your algorithm in the form of a pseudocode using the similar notation that we have used in the class to represent sorting algorithms

3. Now, suppose you have n coins and one of them is heavier. You can assume that n is a power of 3. Generalize the algorithm you have developed in part (a) above for this case. Clearly write your algorithm in the form of a pseudocode using the similar notation that we have used in the class to represent sorting algorithms

Determine the running time of the algorithm. Clearly show how you have arrived at the solution.