[50 points] Evaluate the complexity of the LOOOOOOOOOOP kernel using the
notati
[50 points] Evaluate the complexity of the LOOOOOOOOOOP kernel using the
notation. The many possible values for Istart, Iend, Iincrement, Jstart, Jend, and Jincrement
are given in the table.
LOOOOOOOOOOP(n)
1. for i Istart; i Iend; Iincrement do
2.
for j Jstart; j Jend; Jincrement do
3.
do nothing
Program
Istart
Iend
Iincrement
Jstart
Jend
Jincrement
1 2 n i i+2 2 n j j+2
2 2 n i i+2 2 n j j 2
3 2 n i i+2 2 n j j2
4 2 n i i 2 2 n j j+2
5 2 n i i 2 2 n j j 2
6 2 n i i 2 2 n j j2
7 2 n i i2 2 n j j+2
8 2 n i i2 2 n j j 2
9 2 n i i2 2 n j j2
10 2 n i i+2 2 i j j+2
11 2 n i i+2 2 i j j 2
12 2 n i i+2 2 i j j2
13 2 n i i 2 2 i j j+2
14 2 n i i 2 2 i j j 2
15 2 n i i 2 2 i j j2
16 2 n i i2 2 i j j+2
17 2 n i i2 2 i j j 2
18 2 n i i2 2 i j j2
19 2 n i i+2 2 i j i+j
20 2 n i i+2 2 i j i j
1
2. [10 points] Given an array A[1 n] where n 2containing integers from 1 to n 1
inclusive, exactly one of which is repeated, we need to find and return this integer
that is repeated.
(i) Design a On2 time algorithm FINDREPEATEDNUMBER-NAIVE(A[1 n]) to
solve the problem.
(ii) Design a O(n) time constant extra space algorithm FINDREPEATEDNUMBER
EFFICIENT(A[1 n]) to solve the problem.
3. [10 points] Given an array of integers A[1 n], we need to push all square num
bers in the array to the front of the array and the non-square numbers to the
end. Assume that you are given a function ISPERFECTSQUARE(k) that checks if
a given number k is a square number or not in O(1) time.
(i) Design a On2 time, O(1) extra space algorithm GROUPING-NAIVE(A[1 n]) to
solve the problem.
(ii) Design a (n) time, O(n) extra space algorithm GROUPING-BETTER(A[1 n])
to solve the problem.
(Surprisingly, there is a much better (n)time, (1)extraspacealgorithm GROUPING
BEST(A[1 n])tosolve the problem. You will learn about this beautiful algorithm
in the algorithms course.)
4. [10 points] Suppose prisoners numbered 123
n are standing in a circle in
the clockwise order. Starting from the first prisoner, every kth prisoner in the
clockwise direction is killed in every step. We would like to compute the jthperson
to be killed.
(i) Design a natural algorithm JOSEPHUSPROBLEM-ARRAY(nk j) using an array
to solve the problem.
(ii) Design a natural algorithm JOSEPHUSPROBLEM-CSLL(nk j)usingcircularly
singly linked list to solve the problem.
5. [10 points] Given an array of integers A[1 n], we want to maximize A[i] A[j]
such that i < j. Assume that you are given a function SORT(A[1 n]) that sorts
the array in-place in nlogn time and (n) extra space.
(i) Design a n2 time, (1)extraspacealgorithm MAXIMIZEPRODUCT-NAIVE(A[1 n])
to solve the problem.
(ii) Design a nlogn time, (n)extraspacealgorithm MAXIMIZEPRODUCT-BETTER(A[1 n])
to solve the problem.
(iii) Design a (n)time, (1)extraspacealgorithm MAXIMIZEPRODUCT-BEST(A[1 n])
to solve the problem.
6. [10 points] Given two circularly singly linked lists, design a quadratic time al
gorithm to find if the two lists store the same sequence of elements but perhaps
with different starting points.