Homework Written
Due 11:59 pm Friday April 2, 2021
Show the steps of deriving your answers. Points will be deducted for answers without adequate
steps discussed or not compliant with the instruction. Submit your homework via Blackboard as
one PDF or Word document. Refer to the grading guidelines posted on Blackboard to
understand how the submitted exercises will be graded.
1. (25) [Divide and conquer: majority equivalence class] Do Textbook Exercise 3 in Chapter
5. Note that the problem of finding a set of more than half the bank cards that correspond to the
same account can be reduced to finding a majority equivalence class, that is, an equivalence class
that contains more than half the set elements (i.e., bank cards). Assume that the equivalence
tester requires two cards to give a test result. Give your answers as specified below.
a) Prove the property that if there exists a majority equivalence class in the set of size n then at
least one of the two halves (each of size n/2) has a majority equivalence class. Suggested
proof technique: proof by contradiction.
b) Based on the proven property, write an executable pseudocode of the recursive algorithm
designed using the divide-and-conquer approach. Name the algorithm “MajEC”. Hint:
divide the set of bank cards into two halves and call the algorithm recursively on each half.
c) Write a recurrence relation expressing the run-time T(n) of the recursive algorithm, and solve
it to derive the run-time in big-O; it suffices to derive the closed functional form of the runtime
and do not prove the big-O formally. The recurrence relation should have both recursive
cases and base cases. Either the recursion tree technique or the telescoping technique can be
used to derive the closed functional form. If the recurrence relation is one we have already
solved in class, it is sufficient to refer to it without solving it again.
2. (25) [Integer multiplication: reading & research] Read the discussion on Integer
Multiplication algorithm using divide-and-conquer in Section 5.5 of the textbook (pages 231 –
234), and provide answers as specified below. Assume the integers multipled are binary integers.
a) Write the key idea that enables the algorithm to divide the problem into three disjoint
subproblems -- that is, to achieve the multiplication of two n-bit integers from multiplying
two n/2-bit integers three times.
b) Write the resulting divide-and-conquer algorithm in an executable pseudocode. Name the
algorithm “MultInt”. Do not copy the pseudocode in the texbook but write your own
pseudocode. Make sure to add the base case; the textbook code may not have the base case.
Make use of the following functions as needed in your pseudocode.
• MultInt(x, y, n) returns the multiplication of two n-bit integers x and y.
• Add(x, y, n) returns the sum of two n-bit integers x and y, i.e., x + y.
• Sub(x, y, n) returns the difference of n-bit integer y from n-bit integer x, i.e., x – y.
• LSL(x, b) returns x shifted to the left logically by b bits. (Logical shift left(LSL)
shifts in bit 0’s on the least significant bits.)
• LSR(x, b) returns x shifted to the right logically by b bits. (Logical shift right(LSR)
shifts in bit 0’s on the most significant bits.)
• ceil(b) returns the ceiling of b.
• floor(b) returns the floor (i.e., truncation)of b.
Note:
• Dividing (i.e., separating) an n-bit integer into the upper n/2-bit integer and the lower
n/2-bit integer can be implemented in linear time by calling logical-shift by n/2 bits
(LSL and LSR below).
• Multiplying an integer by 2n can be implemented in linear time by calling logicalshift
left by n bits.
c) Write a recurrence relation that expresses the run-time, T(n), of the recursive algorithm, and
explain how each term in the recurrence relation is formed.
d) Write the steps of solving the recurrence relation to derive the run-time complexity T(n) =
O(nlg3) (=O(n1.585)). (Here, lg3 ≡ log23.) Use the recursion tree technique to derive the runtime
complexity; make a simplifying assumption that n is a power of 2 integer. Do not use
the master theorem in Section 5.2. There is no need to give a formal proof of big-O.