CSE 102: Spring 2022
Quiz # 3: April 20 (25 points)
50 minutes (Quiz) + 10 minutes (uploading) = 60 minutes
There are 6 problems and 4 pages.
You may use the following facts. You may also use a calculator.
log2 7 = 2.8073; log3 20 = 2.7268; log4 49 = log2 7.
Problems
1. (3 points)
(a) In the context of asymptotic growth of functions, what does dec-
imal war mean?
(b) Mention two of the main challenges that may occur with more
efficient algorithms (such as Strassen’s square matrix multiplica-
tion algorithm) that do asymptotically better than well known
algorithms (such as straightforward O(n3) square matrix multi-
plication algorithm).
2. (4 points) Strassen’s square matrix multiplication algorithm di-
vides the matrices into 4 blocks of square matrices of size n/2. In-
stead of 8 multiplications (regular case), Strassen designed an algorithm
that requires only 7 multiplications at each level thereby reducing the
asymptotic complexity of algorithm from O(n3) to O(nlog2 7).
If you were to design a divide-and-conquer algorithm for this problem
where you will divide the matrices into blocks of square matrices of size
n/4, then
(a) How many blocks will be there? How many multiplications per
level will be needed in a regular case? Write down the recurrence
relation in this case.
(b) What is themaximum number of multiplications per level that will
result in an asymptotic complexity strictly better than O(nlog2 7)?
Write down the recurrence relation.Show all your work.
3. (4 points) A majority element of an array A[1, .., n] is any element
occurring in strictly more than n/2 positions. A student wants to
design a divide-and-conquer algorithm by dividing the array into three
sub-problems rather than two sub-problems.
In the following problems, you can assume that n = 3m, so that the
number of elements in each of the three sub-parts of the array is m.
Furthermore, if you need to provide a counter-example, use n = 9. If
you need to provide a proof, prove formally by using the < or ≤ or >
or ≥ symbols precisely in your proof.
(a) Suppose each of the three sub-parts have a majority element.
Then prove that the array must have a majority element or pro-
vide a counterexample.
(b) Suppose none of the three sub-parts have a majority element.
Then prove that the array has no majority element or provide
a counterexample.
4. (4 points) Consider the StoogeSort Algorithm which sorts an array
of integers using divide-and-conquer approach roughly dividing the ar-
ray into 2
3
-rds and then recursively calling itself three times as described
in Discussion Homework.
Letm be ⌊2n
3
⌋ instead of ⌈2n
3
⌉ in the above algorithm. With this change
in the algorithm,
EITHER
Provide a counterexample with 5 elements in an array that Stooge-
Sort algorithm will not sort correctly (clearly describing the end result
of applying StoogeSort on the input showing all the intermediate re-
sults)
OR
Provide an outline of a proof that the algorithm will correctly sort
every array with 5 elements (clearly describing the argument).
5. Line Segment Intersections (6 points)
Consider the line intersection problem discussed in homework. Con-
sider the following diagram with 7 points, {p1, p2, . . . , p7}, on line y = 0
and another 7 points, {q1, q2, . . . , q7} on line y = 1. See the diagram
below.
Algorithms Lecture : Recursion [Fa’]
. An inversion in an array A[1 ..n] is a pair of indices (i, j) such that i < j and A[i] > A[ j].
The number of inversions in an n-element array is between 0 (if the array is sorted) and
n
2

(if the array is sorted backward). Describe and analyze an algorithm to count the number
of inversions in an n-element array in O(n logn) time. [Hint: Modify mergesort.]
. (a) Suppose you are given two sets of n points, one set {p1, p2, . . . , pn} on the line y = 0
and the other set {q1,q2, . . . ,qn} on the line y = 1. Create a set of n line segments
by connect each point pi to the corresponding point qi. Describe and analyze a
divide-and-conquer algorithm to determine how many pairs of these line segments
intersect, in O(n logn) time.
(b) Now suppose you are given two sets {p1, p2, . . . , pn} and {q1,q2, . . . ,qn} of n points
on the unit circle. Connect each point pi to the corresponding point qi . Describe and
analyze a divide-and-conquer algorithm to determine how many pairs of these line
segments intersect in O(n log2 n) time. [Hint: Use your solution to part (a).]
(c) Solve the previous problem in O(n logn) time.
q1 q4 q7 q3q5 q2 q6
p1 p4p7 p3 p5p2p6
q1
q4
q7
q3 q5
q2
q6
p1
p4
p7
p3
p5
p2
p6
Eleven intersecting pairs of segments with endpoints on parallel lines,
and ten intersecting pairs of segments with endpoints on a circle.
. Suppose we are given a set S of n items, each with a value and a weight. For any element
x 2 S, we define two subsets
• S• S>x is the set of all elements of S whose value is larger than the value of x .
For any subset R ✓ S, let w(R) denote the sum of the weights of elements in R. The
weighted median of R is any element x such that w(Sx) w(S)/2.
Describe and analyze an algorithm to compute the weighted median of a given weighted
set in O(n) time. Your input consists of two unsorted arrays S[1 ..n] and W [1 ..n], where
for each index i, the ith element has value S[i] and weight W [i]. You may assume that all
values are distinct and all weights are positive.
. Describe an algorithm to compute the median of an array A[1 .. 5] of distinct numbers
using at most 6 comparisons. Instead of writing pseudocode, describe your algorithm using
a decision tree: A binary tree where each internal node contains a comparison of the form
“A[i]ø A[ j]?” and each leaf contains an index into the array.

(a) Redraw/re-label the points on the line after the pre-processing
step used in the solution using divide-and-conquer algorithm. What
is the numb r of intersections between the line segments after
redrawing/re-labeling the points?
(b) After redrawing/r labeling, how many inversions are ther with
respect to the left-most point (or index) on line y = 0 and how
many inversions are there with respect to the left-most point (or
index) on line y = 1? [Recall an inversion is a pair of index (i, j)
with i < j and qi > qj.]
6. (4 points) An array of integers A[0, · · · , n − 1] is called unimodal if
it has a unique peak, i. e., there is some index m such that A[i] is
monotonically increasing1 for i ≤ m and monotonically decreasing2for
i ≥ m. [1, 23, 29, 25, 18, 7] is an example of a unimodal array where
the peak is 29. When an array is unimodal, we can find the maximum
(peak) value faster by using a divide-and-conquer algorithm than by
iterating over the whole array.
Suppose, you attempt to use a variation of the binary search: by looking
at the midpoint p of the array: A[p] and its adjacent elements A[p− 1]
and A[p+ 1].
(a) What condition needs to be satisfied for A[p] so that the midpoint
is the maximum or the peak?
(b) What condition needs to be satisfied for A[p] so that you can
discard left side of the array (and search for the peak only on the
right side of the array)?
{A similar condition needs to be satisfied for A[p] so that you can
discard the right side of the array. You do NOT have to do this
part}.
(c) What is the recurrence equation for this divide-and-conquer algo-
rithm? What is the asymptotic complexity of this algorithm? No
need to show work for this part of the problem.
1A sequence is monotonically increasing if A[i] > A[j] whenever i > j
2A sequence is monotonically decreasing if A[i] < A[j] whenever i > j