# Homework 1

Out: Monday, January 28, 2019

Due: 8pm, Monday, February 11, 2019

You should always describe your algorithm clearly in English. You should always give pseudocode for all algorithms that you design. For all algorithms you design, you must prove correctness and give the best upper bound that you can for the running time. You are also encouraged to analyze the space required by your algorithm.

Collaboration is limited to discussion of ideas only. You should write up the solutions entirely on your own. You should list your collaborators on your write-up. If you do not type your solutions, be sure that your hand-writing is legible, your scan is high-quality and your name is clearly written on your homework.

1. (25 points) In the table below, indicate the relationship between functions f and g for each pair (f, g) by writing “yes” or “no” in each box. For example, if f = O(g) then write “yes” in the first box. Here logb x = (log2 x)b.

 f g O o Ω ω Θ n log2 n 6n2 log n √log n (log log n)3 4 log n n log 4n n3/5 √n log n 5√n + log n 2√n 5nn8 n54n √n2n 2n/2+log n n log 2n n2log n n! 2n log n! log nn

depth 0 (root level)

x1< x2 ?

yes no

depth 1

x2 < x3 ?

x1< x3 ?

yes no

yes no

depth 2

x1, x2, x3

x1< x3 ? x2, x1, x3 x2 < x3 ?

yes no

yes no

depth 3

x1, x3, x2

x3, x1, x2

x2, x3, x1 x3, x2, x1

Figure 1: A tree corresponding to a comparison-based sorting algorithm on input x1, x2, x3.

2. (35 points)

1. (15 points) A lower bound for comparison-based sorting

You may view a comparison-based sorting algorithm as a binary tree. For example, the tree in Figure 1 sorts 3 integers x1, x2, x3: it first compares x1 to x2; if x1 < x2, it compares x2 to x3, else is compares x1 to x3, etc. Each leaf corresponds to a possible permutation of the 3 numbers. For example, if x1 < x2 < x3, we get the leaf labelled x1, x2, x3.

Suppose you want to sort n integers.

1. (2 points) Argue that every possible permutation of the n numbers must appear as a leaf in the tree corresponding to a sorting algorithm.

2. (2 points) Fill in the missing number in the following sentence:

Thus the tree has at least . . . leaves.

3. (3 points) The worst-case time complexity of the sorting algorithm is given by the maximum number of comparisons performed by the algorithm. What does the latter quantity correspond to in the tree?

4. (3 points) Consider a binary tree of depth d. Give with a proof an upper bound on the number of leaves of the tree.

5. (5 points) Derive a lower bound for the worst-case time complexity of a comparison- based sorting algorithm.

2. (17 points) Give an algorithm that sorts any array of n integers x1, . . . , xn in O(n + D) time, where D = max xi min xi.

i i

3. (3 points) Suppose D is small (that is, O(n)). Does the algorithm you proposed in part

(b) contradict the lower bound you derived in part (a)?

3. (20 points)

1. (4 points) Show that 5 integer multiplications suffice to compute the square of a 2 × 2 matrix.

2. (6 points) What is wrong with the following algorithm for computing the square of an

n × n matrix?

Use a divide-and-conquer approach as in Strassen’s algorithm, except that instead of getting 7 subproblems of size n/2, we now get 5 subproblems of size n/2 thanks to part (i). Using the same analysis as in Strassen’s algorithm, we can conclude that the algorithm runs in time O(nlog2 5).

3. (10 points) In fact, squaring matrices is no easier than matrix multiplication. Show that if n × n matrices can be squared in time O(nc), then any two n × n matrices can be multiplied in time O(nc).

4. (30 points) You’re assisting a bank in the following fraud detection instance.

There are n bank cards. The bank needs to determine whether there is a subset of more than

n/2 cards that belong to the same bank account.

The bank has a device that takes as input two cards and determines in constant time whether the cards belong to the same bank account. The only way to determine whether two cards belong to the same bank account is by inserting them to this device.

1. (15 points) Give an algorithm to solve this problem in O(n log n) time.

2. (15 points) Can you give an algorithm that has a linear worst-case performance?

5. (25 points) You are given a sequence of n distinct numbers x1, . . . , xn and want to understand how far this sequence is from being in ascending order.

One way to define a measure for this is by counting how many pairs of numbers xi, xj appear “out of order” in the sequence, that is, xi > xj but xi appears before xj .

We will define the disorder of a sequence to be the number of pairs (xi, xj ) such that xi > xj but i < j. For example, if the input sequence is 2, 4, 1, 3, 5, then the pairs (2, 1), (4, 1) and (4, 3) are out of order and the disorder of the sequence is 3.

1. (5 points) Give a brute force algorithm to compute the disorder of an input sequence of size n.

2. (20 points) Can you give a faster algorithm to compute the disorder?

# RECOMMENDED EXERCISES (do NOT return, they will not be graded)

1. Give tight asymptotic bounds for the following recurrences.

T (n) = 4T (n/2) + n3 1.

T (n) = 8T (n/2) + n2.

T (n) = 6T (n/3) + n.

T (n) = T (n) + 1.

2. Show that, if λ is a positive real number, then f (n) = 1 + λ + λ2 + . . . + λn is

1. Θ(1) if λ < 1.

2. Θ(n) if λ = 1.

3. Θ(λn) if λ > 1.

Therefore, in big-Θ notation, the sum of a geometric series is simply the first term if the series is strictly decreasing, the last term if the series is strictly increasing, or the number of terms if the series is unchanging.

3. A positive integer N is a power if it is of the form qk , where q, k are positive integers and

k > 1.

1. Design and analyze an efficient algorithm that takes as input an integer N and determines if it is a square, that is, if it can be written as q2 for some positive integer q.

2. Suppose that N = qk , where N, k, q are positive integers. Show that either N = 1 or

k log N .

3. Design and analyze an efficient algorithm for determining whether a positive integer N

is a power.  