CS6515 Homework 2


Category: You will Instantly receive a download link for .zip solution file upon Payment


5/5 - (1 vote)

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)).