Description
Points to remember:
Youcanassumethatyouhaveaccesstothefunction BINARYSEARCH(A[low high] key)
that searches for key in the subarray A[low high] and returns an index of key if key
is present and returns 1 if key is not present.
Quick summary: Brute force is a simple, straightforward, naive, and exhaustive
search-based approach. Decrease-and-conquer is a recursive algorithm design tech
nique where a function calls only one instance of itself on a smaller subproblem.
1. [10 points] Given a sorted array of numbers A[1 n], we would like to determine
a value x such that both x and (2x + 17) are in the array. If there is, print one
such value x, else, print that there is no such value.
(i) Design a On2 time, (1) extra space algorithm FINDX-NAIVE(A[1 n]) to
solve the problem.
(ii) Design a Onlogn time, (n) extra space algorithm FINDX-BETTER(A[1 n])
to solve the problem.
(iii) Design a O(n) time, (1) extra space algorithm FINDX-BEST(A[1 n]) to solve
the problem.
2. [10 points] Consider the algorithm called SIMPLESORT. Consider two example
arrays of size 5 and show the array contents with values of i and j (approximately
25 steps for each example). Does this simple algorithm sort an array of unique
elements? Does it sort an array even if there are duplicates? If the algorithm
does sort, why do you think it sorts? If the algorithm does not sort an array give
a counterexample and you will get 5 extra points as bonus points.
SIMPLESORT(A[1 n])
1. Input: Array to be sorted A[1 n]
2. Output: Sorted array in A[1 n]
3. for i 1tondo
for j 1tondo
4.
5.
6.
if A[i] < A[j] then
SWAP(A[i]A[j])
1
3. [10 points] Given an array of real numbers A[1 n], apair of indices (i j) is called
an inversion if i < j and A[i] > A[j]. We want to count the total number of inver
sions in a given array.
(i) Design asimplenon-recursive algorithm COUNTINVERSIONS-NONRECURSIVE(A[1 n])
to solve the problem.
(ii) Design a simple recursive algorithm COUNTINVERSIONS-RECURSIVE(A[1 n])
to solve the problem.
4. [10 points] Given an array of real numbers A[1 n], we want to compute and
return the prefix sum array P[1 n] such that P[i] = A[1]+ A[2]+ A[3]+ +A[i].
(i) Design a O(n) non-recursive algorithm PREFIXSUM-NONRECURSIVE(A[1 n])
to solve the problem.
(ii) Design a O(n) recursive algorithm PREFIXSUM-RECURSIVE(A[1 n]) to solve
the problem.
5. [10 points] Given a string S[1 2n] containing just the characters ’(’ and ’)’, de
sign an algorithm ISVALIDSTRING(S[1 2n]) to determine if the input string is
valid. An input string is valid if the open brackets are closed in the proper order.
Example: (()) is valid; (())() is valid; )()) is invalid; ())) is invalid; ()(( is invalid.
(Hint: Use a stack to solve the problem.)
6. [10 points] Given two natural numbers a and b, we want to compute the greatest
common divisor (GCD) of a and b.
(i) Design a simple non-recursive algorithm GCD(ab) to solve the problem.
(ii) Design a simple recursive algorithm GCD(ab) to solve the problem.
7. [10 points] Apolynomial P(x) with asingle indeterminate x is written in the form:
n
P(x) =
aixi = anxn + an 1xn 1 + +a2x2 +a1x+a0
i=0
where ai for all i [0n] is a real constant. Assume that ai = A[i] for all i. We want
to compute the univariate polynomial P(x) at a specific value of x.
(i) Design a On2 algorithm EVALUATEPOLY(A[0 n] x) to solve the problem.
(ii) Design a Onlogn algorithm EVALUATEPOLY(A[0 n] x)tosolvetheproblem.
(Hint: Ideas from the slides are helpful)
(iii) Design a O(n) algorithm EVALUATEPOLY(A[0 n] x) to solve the problem.
(Hint: Use Horner’s method of representing the polynomial as follows.)
P(x) = a0 + x(a1 + x(a2 + x(a3 + + x(an 1 + xan) )))
8. [10 points] Given a sorted array A[1 n] and a value k, we want to return a pair
of distinct indices such that the sum of elements at those indices equals k. That
is, we want to return a pair of indices (i j), where 1 i < j n and A[i]+ A[j] = k.
(i) Design a On2 algorithm PAIRSUM(A[1 n] k) to solve the problem.
(ii) Design a Onlogn algorithm PAIRSUM(A[1 n] k) to solve the problem.
2
(iii) Design a O(n) algorithm PAIRSUM(A[1 n] k) to solve the problem.
9. [10 points] Given a sorted array A[1 n], we want to count the number of occur
rences of value k in the array.
(i) Design a O(n) algorithm COUNTFREQUENCY(A[1 n] k) to solve the problem.
(ii) Design a O logn algorithm COUNTFREQUENCY(A[1 n] k) to solve the prob
lem. (Hint: Modify binary search and use it.)
10. [10 points] Simulation problem.
(i) Simulate a stack using queue(s). That is, show how to implement Push and
Pop functions of stack using Enqueue and Dequeue methods of queue(s).
(ii) Simulate a queue using stack(s). That is, show how to implement Enqueue
and Dequeue functions of queue using Push and Pop methods of stack(s)
Unformatted Attachment Preview
Points to remember:
You can assume that you have access to the function B INARY S EARCH(A[low . . . high], key)
that searches for key in the subarray A[low . . . high] and returns an index of key if key
is present and returns −1 if key is not present.
Quick summary: Brute force is a simple, straightforward, naive, and exhaustive
search-based approach. Decrease-and-conquer is a recursive algorithm design technique where a function calls only one instance of itself on a smaller subproblem.
1. [10 points] Given a sorted array of numbers A[1 . . . n], we would like to determine
a value x such that both x and −(2 x + 17) are in the array. If there is, print one
such value x, else, print that there is no such value.
(i) Design a O n2 time, Θ (1) extra space algorithm F IND X-N AIVE(A[1 . . . n]) to
solve the problem.
(ii) Design a O n log n time, Θ (n) extra space algorithm F IND X-B ETTER(A[1 . . . n])
to solve the problem.
(iii) Design a O (n) time, Θ (1) extra space algorithm F IND X-B EST(A[1 . . . n]) to solve
the problem.
2. [10 points] Consider the algorithm called S IMPLE S ORT. Consider two example
arrays of size 5 and show the array contents with values of i and j (approximately
25 steps for each example). Does this simple algorithm sort an array of unique
elements? Does it sort an array even if there are duplicates? If the algorithm
does sort, why do you think it sorts? If the algorithm does not sort an array give
a counterexample and you will get 5 extra points as bonus points.
S IMPLE S ORT(A[1 . . . n])
Input: Array to be sorted A[1 . . . n]
Output: Sorted array in A[1 . . . n]
3. for i ← 1 to n do
4.
for j ← 1 to n do
5.
if A[i] < A[ j] then
6.
SWAP (A[i], A[ j])
1.
2.
1
3. [10 points] Given an array of real numbers A[1 . . . n], a pair of indices (i, j) is called
an inversion if i < j and A[i] > A[ j]. We want to count the total number of inversions in a given array.
(i) Design a simple non-recursive algorithm C OUNT I NVERSIONS -N ONRECURSIVE(A[1 . . . n])
to solve the problem.
(ii) Design a simple recursive algorithm C OUNT I NVERSIONS -R ECURSIVE(A[1 . . . n])
to solve the problem.
4. [10 points] Given an array of real numbers A[1 . . . n], we want to compute and
return the prefix sum array P[1 . . . n] such that P[i] = A[1] + A[2] + A[3] + · · · + A[i].
(i) Design a O (n) non-recursive algorithm P REFIX S UM -N ONRECURSIVE(A[1 . . . n])
to solve the problem.
(ii) Design a O (n) recursive algorithm P REFIX S UM -R ECURSIVE(A[1 . . . n]) to solve
the problem.
5. [10 points] Given a string S [1 . . . 2n] containing just the characters ’(’ and ’)’, design an algorithm I S VALID S TRING(S [1 . . . 2n]) to determine if the input string is
valid. An input string is valid if the open brackets are closed in the proper order.
Example: (()) is valid; (())() is valid; )()) is invalid; ())) is invalid; ()(( is invalid.
(Hint: Use a stack to solve the problem.)
6. [10 points] Given two natural numbers a and b, we want to compute the greatest
common divisor (GCD) of a and b.
(i) Design a simple non-recursive algorithm GCD(a, b) to solve the problem.
(ii) Design a simple recursive algorithm GCD(a, b) to solve the problem.
7. [10 points] A polynomial P(x) with a single indeterminate x is written in the form:
n
X
P(x) =
ai xi = an xn + an−1 xn−1 + · · · + a2 x2 + a1 x + a0
i=0
where ai for all i ∈ [0, n] is a real constant. Assume that ai = A[i] for all i. We want
to compute the univariate polynomial P(x) at a specific value of x.
(i) Design a O n2 algorithm E VALUATE P OLY(A[0 . . . n], x) to solve the problem.
(ii) Design a O n log n algorithm E VALUATE P OLY(A[0 . . . n], x) to solve the problem.
(Hint: Ideas from the slides are helpful)
(iii) Design a O (n) algorithm E VALUATE P OLY(A[0 . . . n], x) to solve the problem.
(Hint: Use Horner’s method of representing the polynomial as follows.)
P(x) = a0 + x(a1 + x(a2 + x(a3 + · · · + x(an−1 + xan ) · · · )))
8. [10 points] Given a sorted array A[1 . . . n] and a value k, we want to return a pair
of distinct indices such that the sum of elements at those indices equals k. That
is, we want to return a pair of indices (i, j), where 1 ≤ i < j ≤ n and A[i] + A[ j] = k.
(i) Design a O n2 algorithm PAIR S UM(A[1 . . . n], k) to solve the problem.
(ii) Design a O n log n algorithm PAIR S UM(A[1 . . . n], k) to solve the problem.
2
(iii) Design a O (n) algorithm PAIR S UM(A[1 . . . n], k) to solve the problem.
9. [10 points] Given a sorted array A[1 . . . n], we want to count the number of occurrences of value k in the array.
(i) Design a O (n) algorithm C OUNT F REQUENCY(A[1 . . . n], k) to solve the problem.
(ii) Design a O log n algorithm C OUNT F REQUENCY(A[1 . . . n], k) to solve the problem. (Hint: Modify binary search and use it.)
10. [10 points] Simulation problem.
(i) Simulate a stack using queue(s). That is, show how to implement Push and
Pop functions of stack using Enqueue and Dequeue methods of queue(s).
(ii) Simulate a queue using stack(s). That is, show how to implement Enqueue
and Dequeue functions of queue using Push and Pop methods of stack(s).
3
Purchase answer to see full
attachment
