## Description

1. [12 pts]

def A(x):

i=0

while (True):

x[i] = 0

i = i+1

2. [12 pts]

def A(x):

i=0

while (True):

x[i] = 0

i = i+1

if (i >= 10000000000):

break

3. [12 pts]

def A(x):

i=0

while (i<10000000):

x[i] = 0

i = i+1

external_procedure(x[i])

4. [12 pts] What is the computational complexity of the following program?

(Big Oh notation is sufficient).

Assume that X[i,j] references the (i,j) component of matrix X.

Also, assume that N is a parameter describing the size of X as X[N,N].

for i in range(N):

v[i] = 0

for j in range(N):

v[i] += A[i,j]*b[j]

Be sure to give your reasons for your complexity calculation.

5. [12 pts] What is the computational complexity of the following program?

(Big Oh notation is sufficient).

Assume that X[i,j] references the (i,j) component of matrix X

Also, assume that N is a parameter describing the size of X as X[N,N]

for i in range(N):

v[i] = 0

for j in range(i:N):

v[i] += A[i,j]*b[j]

Be sure to give your reasons for your complexity calculation.

6. [12 pts] What is the computational complexity of the following program?

(Big Oh notation is sufficient).

Assume that X[i,j] references the (i,j) component of matrix X

Also, assume that N is a parameter describing the size of X as X[N,M]

M is a symbolic constant completely independent of N.

for i in range(N):

v[i] = 0

for j in range(M):

v[i] += A[i,j]*b[j]

Be sure to give your reasons for your complexity calculation.

7. [14 pts] Find an efficient algorithm to compute xm, for arbitrary nonnegative integer m.

By “efficient”, the time complexity of your algorithm should be O(log2(m))

Hint: used divide and conquer.

Please include:

1) a proof sketch that your algorithm is correct,

2) the complexity of your algorithm, and how you determined the

complexity.

8. [14 pts] Suppose you were given an array of numbers that were in

ascending order. Some evil mastermind, however, has rearranged the list to

“cycle around” from some middle point. Find an efficient algorithm to

determine the original starting point from the cyclic list. By “efficient”, the time

complexity of your algorithm should be O(log2(N)), where N is the length of

the array.

Example:

Original list: 1, 3, 4, 5, 8, 9

Your rearranged list: 5, 8, 9, 1, 3, 4

Your algorithm should identify the 4th element as the start of the original list.

Please include:

1) a proof sketch that your algorithm is correct,

2) the complexity of your algorithm, and how you determined the

complexity.