Homework 3.
[DPV] Practice Problems
These are practice problems to help you to become more familiar with the topic, these problems will not be graded. It is not compulsory to finish these problems.
DPV Problems 2.8, 2.9(a) (FFT practice)
Practice Problem (Types of binary search)
Let A be an arrray of n different elements. By sorted array we mean sorted in non-decreasing order.
(a) Consider A = {10,23,36,47,59,64,71,82,95,100,116,127,138,141,152,163}. We want to check if the number 36 is an element of A. Explain how the binary search works to find this element.
(b) Design an O(log(n)) algorithm to find the smallest missing natural number in a given sorted array. The given array only has natural numbers. For example, the smallest missing natural number from A = {3,4,5} is 1 and from A = {1,3,4,6} is 2.
See next page for homework problems.
1
Name: 2
Problem 1 (Median algorithm)
Let A be an array of n distinct numbers. Let k < n/2. Design an algorithm that outputs the kth elements of A that are closest to the median of A. More precisely, your algorithm should return the order statistics
{n/2 − k/2;n/2 − k/2 + 1;...,n/2 + k/2;n/2 + k/2}.
You can asume that both n and k are even.
Example: for A = [2,5,4,9,0,−1] and k = 2 your output should be the set {2,4,0}. In particular, your output does not have to be sorted.
Use the algorithms discussed in class as black-boxes. Do not use pseudocode. Explain why your algorithm is correct and analyze its running time. Faster and correct solutions are worth more credit.
Problem 2 (Integer multiplication using FFT)
(a) Given an n−bit integer number a = a0a1a2 ...an−1 define a polynomial A(x) satisfying A(2) = a.
(b) Given two n−bit integers a and b, give an algorithm to multiply them in O(nlog(n)) time. Use the FFT algorithm from class as a black-box (i.e. don’t rewrite the code, just say run FFT on ...).Explain your algorithm in words and analyse its running time.
2
