Consider the following meaningless algorithm:

// PRE: a,b,c are integers if a + b > c c = a + b end if a + b == c c = c^2 end if a + b <= c print(’hi!’) end

Suppose there are certain time requirements for various operations:

• Addition takes 2 seconds.
• Comparison takes 1 second.
• Squaring takes 3 seconds.
• Assignment takes 0 seconds.
• Printing takes 5 seconds.

1. If the input to the algorithm is a=1,b=2,c=3, how long will it take? [2 pts]

Solution:

2. If the input to the algorithm is a=3,b=2,c=2, how long will it take? [2 pts]

Solution:

3. If the input to the algorithm is a=4,b=2,c=4, how long will it take?             [2 pts]

Solution:

4. If the three inputs given in (a),(b), and (c) are the only possible inputs and they have [4 pts] probabilities 0.1, 0.2, and 0.7 respectively, what is the expected running time of the algorithm?

Solution:

Define f(n) = 5n² + 7nlgn − lgn + 10.

1. Show from the definition of O that f(n) = O(n²). [8 pts]

Solution:

2. Show from the definition of ? that f(n) = ?(n²). [7 pts]

Solution:

Suppose that for an input of size n:                 [10 pts]

• Algorithm A has running time T_A(n) = n² lgn
• Algorithm B has running time T_B(n) = 0.001n³ + n

Plot these two functions and indicate the approximate intersection point. For which n is each algorithm faster? Explain how you came up with your values. Use of computational tools is permitted for this question provided you explain which tools you used and how you used them.

Plots may be basic and hand-drawn.

Solution:

Give an example of a list for which Binary Search finds the target element of 17 on exactly [10 pts] the third comparison. Do not count the while loop check as a comparison. Give both the list and then at each step give the value of C, what the result of the comparison is, and how the comparisons update L or R.

Solution:

Backstory: Suppose you have a list A[0,...,n-1] with n ≥ 10 and you wish to find the five [15 pts] largest and five smallest entries. One obvious approach would be to sort the data and then just select the first five and last five entries. However certain external constraints may force your algorithm to stop early and as such you want to ensure that it takes care of the two ends of the list first. None of our sorting algorithms do this.

Your Job: Modify SelectionSort so it alternates between the left and right sides of the list, starting on the left. In other words it gets A[0] correct, then A[n-1], then A[1], then A[n-2], and so on, until the list is sorted. Write the pseudocode for this. You may assume n is even.

Solution:

Find integral-related bounds for the following. The terms are decreasing, you do not need to  [10 pts] prove this.

 

 

Solution:

Consider the following pseudocode. Assume n is even and the list A[0,...,n-1] contains only 1s and 2s. For example A might be [1,2,2,1,1,2,1,1].

sum = 0 result = 1 for i = 0 to n-1 sum = sum + A[i] for j = i to n-1 result = result * A[j] end if sum == n break end end

c₁ c₁ c₂ c₅

c₃ c₄

For this pseudocode, answer the following. These are asking for exact time requirements, not time complexity!

(a) Write down the expression (use sum notation) for the exact best-case time requirement. Do not evaluate this sum. Solution:	[5 pts]
(b) Write down the expression (use sum notation) for the exact worst-case time requirement.	[10 pts]

Evaluate this sum.

Solution:

NOTE: This question is challenging so do it last!

Suppose you have a list A[0,...,n-1] whose length is a positive multiple of 5 and you wish [15 pts] to make it cumulative, meaning you want to:

• Leave A[0] alone,
• Assign A[1]=A[1]+A[0],
• Assign A[2]=A[2]+A[1] (with the new A[1]) ,
• Assign A[3]=A[3]+A[2] (with the new A[2]) ,
• ...,
• Assign A[n-1]=A[n-1]+A[n-2] (with the new A[n-2]).

This should be pretty simple but suppose you cannot access the entries in A directly. Instead you have a separate working memory R[0,...,4] which you can access directly. You also have the command in(i) which copies A[i,...,i+4] to R[0,...,4] and out(i) which does the reverse. These are called block transfers.

Due to hardware limitations neither command called with some i may spill over the end of A.

Write the pseudocode for this. Full credit will be granted if you minimize the number of block transfers but majority of credit will be granted even if you don’t.

Solution: