# COMP 582 Module 01 Problems solution

\$30.00

Original Work ?

## 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]
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]
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]
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.
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.