## Description

(1. 6pts) Computational problem solving: Estimating problem solving time

Suppose that there are three algorithms to solve a problem: a O(n) algorithm (A1), a O(nlogn)

algorithm (A2), and a O(n

2

) algorithm (A3), where log is to the base 2. Using the techniques

and assumptions presented in slide set L2-Buffet(SelectionProblem), determine how long in

seconds it will take for each algorithm to solve a problem of size 200 million. You must show

1

your work to get credit, i.e., a correct answer without showing how it is derived will receive zero

credit.

(2. 4pts) Computational problem solving: Problem specification

Problem Definition: You are a member of a software engineering team, which is tasked to

develop a mobile application for the SmartCity initiatives sponsored by an enterprise. The

application is a transport sharing tool that will connect a driver with empty seats to people

traveling to a specific target location. The driver’s application will query a remote service to

determine specific requests submitted by customers, where each request is defined by the

position of the person making the ride sharing request. The location of a person is specified as

pair (latitude, longitude). Given a list of requests as input and the computed shortest distances

in terms of turn-by-turn directions between each pair of locations, the application generates

the shortest possible route that visits each location exactly once (to pick up a customer) and

return to the target location.

Specify the problem to a level of detail that would allow you to develop solution strategies

and corresponding algorithms. State the problem specification in terms of (1) inputs, (2) discrete structures/data representation, and (3) desired outputs. No need to discuss solution

strategies.

(3. 8pts) Computational problem solving: Developing strategies

Given a set of n numbers, explain a correct and efficient strategy to find the i largest numbers

in sorted order. Your description should be such that the strategy is clear, but at the same time

the description should be at the level of strategy (e.g., sort the numbers and list the i largest –

you should devise a different strategy than this obvious one). Then state the total number of

steps an algorithm that implements the strategy will have to consider as a function of n.

2

(4. 12pts) Computational problem solving: Understanding an algorithm and its strategy by

simulating it on a specific input

Understand the following algorithm. Simulate it mentally on the following four inputs, and state

the outputs produced (value returned) in each case: (a) A: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; (b) A:

[-1, -2, -3, -4, -5, -6, -7, -8, -9, -10], ; (c) A: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], (d) A: [-1, 2, -3, 4, -5, 6,

7, -8, 9, -10].

Algorithm Mystery (A:array[1..n] of integer)

sum, max: integer

1 sum = 0

2 max = 0

3 for i = 1 to n

4 sum = 0

5 for j = i to n

6 sum = sum + A[j]

7 if sum > max then

8 max = sum

9 return max

Output when input is array (a) above:

Output when input is array (b) above:

Output when input is array (c) above:

Output when input is array (d) above:

What does the algorithm return when the input array contains all negative integers?

What does the algorithm return when the input array contains all non-negative integers?

3

(5. 10pts) Computational problem solving: Calculating approximate complexity

Using the approach described in class (L5-Complexity), calculate the approximate complexity

of Mystery algorithm above by filling in the table below.

(6. 13pts) Calculate the detailed complexity T(n) of algorithm Mystery in the table below, then

determine the expression for T(n) and simplify it to produce a polynomial in n.

T(n) =

4

(7. 5pts) Computational problem solving: Proving correctness/incorrectness

Is the algorithm below correct or incorrect? Prove it ! It is supposed to count the number of all

identical integers that appear consecutively in a file of integers. E.g., If f contains “1 2 3 3 3 4

3 5 6 6 7 8 8 8 8″ then the correct answer is 9.

Count(f: input file)

count, i, j : integer

count = 0

while (end-of-file(f) = false)

i = read-next-integer(f)

if (end-of-file(f) = false) then

j = read-next-integer(f)

if i=j then count = count+1

return count

(8. 5pts) Computational problem solving: Proving Correctness

Let A be an algorithm that finds the kth largest of n elements by a sequence of comparisons.

Prove by contradiction that A collects enough information to determine which elements are

greater than the kth largest and which elements are less than it. In other words, you can

partition the set around the kth largest element without making more comparisons.

(9. 8pts) Computational problem solving: Proving Correctness

Function g(n: nonnegative integer)

if n <= 1 then return(n)

else

return(5*g(n-1)-6*g(n-2))

Prove by induction that algorithm g is correct, if it is intended to compute the function 3

n − 2

n

,

for all n ≥ 0

5

(10. 5pts) Computational problem solving: Proving Correctness

Complete the proof by loop invariant method to show that the following algorithm is correct.

Algorithm Max(A: Array[1..n] of integer)

begin

max = A[1]

for i=2 to n

if A[i] > max then max = A[i]

return max

end

Initialization:

Maintenance:

Termination:

(11. 10pts) Computational problem solving: Proving Correctness

Complete the proof by loop invariant method to show that the following algorithm is correct.

Algorithm Convert(n: positive integer)

output: b (an array of bits corresponding to the binary representation of n)

begin

t = n

k = 0

while (t > 0)

k = k + 1

b[k] = t mod 2

t = t div 2 (div refers to integer division)

end

Use the following loop invariant: If m is the integer represented by the binary array b[1..k]

then n = t2

k + m

Initialization:

Maintenance:

Termination:

6

(12. 14pts) Computational problem solving: Algorithm Design

(a. 10pts) Describe a recursive algorithm to reverse a string that uses the strategy of swapping

the first and last characters and recursively reversing the rest of the string. Assume the string

is passed to the algorithm as an array A of characters, A[p..q], where the array has starting

index p and ending index q, and the length of the string is n = q − p + 1. The algorithm should

have only one base case, when it gets an empty string. Assume you have a swap(A[i], A[j])

function available that will swap the characters in cells i and j. Write the algorithm using

pseudocode without any programming language specific syntax. Your algorithm should be

correct as per the technical definition of correctness.

(b) (4pts) Draw your algorithm’s recursion tree on input string “i<33270!” – remember to show

inputs and outputs of each recursive execution including the execution of any base cases.

7