Description

Homework 2.
[DPV] Practice problem Divide and Conquer
These are practice problems from DPV to help you to become more familiar with DP, these problems will not be graded. It is not compulsory to finish these problems.
[DPV] Problem 2.1– Practice multiplication.
[DPV] Problem 2.5 – Solving recurrence.
[DPV] Problem 2.7 – Sum and product of roots of unity.
[DPV] Problem 2.14 – Erase duplicates. See next page for homework problems.

1
Name: 2

DP Homework (graded)
For each problem below, do not write pseudocode. Explain with words why your algorithm is correct and analyse its running time.
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)).

2