Homework 1 DPV

Name: 1
Homework 1

Suggested reading: Chapter 0.3 and Chapter 2 of the book. Section 2.2 contains
the Master Theorem covered in class.
Practice problems (don’t turn in)
Problem (Big-O order, part (a) and (b) are independent)
(a) For the following list of functions, cluster them into groups of functions of the same order
(i.e., f and g are in the same group if and only if f = O(g) AND g = O(f)), and then rank the
groups in increasing order. You do not have to justify your answer.
• log2
(n)
• log(n
2
)
•
√
n
• n
• 2n + 5
• n log(n) + 2019
• n
2.5
• 2
n
• n log2
(n)
(b) The geometric series of ratio a 6= 1 is the sum
S(n) = 1 + a + a
2 + · · · + a
n
.
Prove that
S(n) = a
n+1 − 1
a − 1
.
Deduce that S(n) = O(a
n) for a 1 and S(n) = O(1) for a < 1. (Hint: you may prove the equality
by induction or just directly by checking that both sides are equal after multiplication by a − 1. )
Problem (Problems from the book) [DPV], Chapter 2, exercises:
2.4 (Choosing between three algorithms).
2.5 (Solving recurrences).
2.19 (k-way merge, we discussed this problem in class).
Problem (Order Statistics in a union of two lists) Describe an algorithm that takes as input
two sorted lists of length n and m and an integer k and outputs the k
th smallest element in their
union. You can assume both lists contain integers and all entries are different.
See next page for those problems you need to submit.
1
Name: 2
INSTRUCTIONS.
• Your solution must be in plain English. On every problem, you have to explain your design
and why it is correct in your own words, and you have to analyze and justify the running time.
• Unless otherwise stated, fastest (and correct) algorithms will receive more credit. If we ask for
a specific running time, a correct solution achieving it will worth full credit, even if a faster
solution exists.
• Do not use pseudocode. Your answer will receive a zero, even if the pseudocode is correct.
Problem 1 (2.16 in DPV: finding x in an infinite array)
You are given an infinite array A[.] in which the first n entries contain different integers in sorted
order and the rest are filled with ∞. You are not given the value of n. Describe an algorithm that
takes as an input an integer x and finds a position in the array containing x, if such position exists,
in O(log(n)) time.
Problem 2 (2.17 in DPV: fixed point)
Given a sorted array of n distint integers A = {a1, a2, . . . , an}, you want to find out whether there
is an index i for which ai = i. Give a divide and conquer algorithm to solve this problems that runs
in time O(log(n)).
Problem 3 (2.20 in DPV: ordering bounded input)
Design an algorithm that takes as input an array A with n integers and sort it in time O(n + M)
where M = maxi A[i] − mini A[i]. Conclude that, for small values of M, sorting this way yields a
linear time algorithm.
Problem 4 (Almost ordered)
You are given an unsorted list of numbers. You are told that the index of every number is at distance
at most 100 from the index it will correspond to it if the list is sorted. Use this information to design
an algorithm that takes as input a list with this property and outputs the list sorted. Explain the
correctness of your algorithm and explain its running time. (Hint: Think how to find the minimal
entry in constant time!)
2