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