Log out Go to App
Go to App

Learning Materials

Features

Discover

Chapter 2: Q16E (page 85)

Question: You are given an infinite array A[·]in which the first n cells contain integers in sorted order and the rest of the cells are filled with ∞. You are not given the value of n. Describe an algorithm that takes an integer x as input and finds a position in the array containing x, if such a position exists, in O(log n) time. (If you are disturbed by the fact that the array A has infinite length, assume instead that it is of length n, but that you don’t know this length, and that the implementation of the array data type in your programming language returns the error message ∞whenever elements A[i]withi>n are accessed.)

Short Answer

Expert verified

An algorithm exist which finds the position of input inter x in array A, in time bound of O(logn).

Step by step solution

01

Algorithm  

1. Check A[1],A[2],A[4],A[8],, and so on, doubling its indexing each time until infinity or the value x is discovered. Let q be the most recent index to be examined.

2. If x=A[q]after back q.

3. If not, conduct a binary find in A[q/2]...A[q]for x. Give the index if x is found; else, return FALSE.

02

Binary Search Pseudocode

Each sub-array will be subjected to something like a binary search algorithm A[q/2]...A[q]

binary_search (A,x) :

low = 1, high = size(A)

while low ≤high:

mid = low + (high - low)/2

if A[mid] == x:

return mid

else if A[mid] < x:

low = mid + 1

else:

high = mid - 1

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

In this problem we will develop a divide-and-conquer algorithm for the following geometric task.

CLOSEST PAIRInput: A set of points in the plane, {p1=(x1;y1),p2=(x2,y2),...,pn=(xn,yn)}

Output: The closest pair of points: that is, the pair Pi≠Pjfor which the distance between piand pj, that is,

(xi-xi)2+z(yi-yi)2,

is minimized.

For simplicity, assume that n is a power of two, and that all the x-coordinates role="math" localid="1659237354869" xi are distinct, as are the y-coordinates.

Here’s a high-level overview of the algorithm:

.Find a value for which exactly half the points have xi<x, and half have xi>x. On this basis, split the points into two groups, L and R.

• Recursively find the closest pair in L and in R. Say these pairs are pL·qL∈Land pR·qR∈Rwith distances dLand dR respectively. Let d be the smaller of these two distances.

• It remains to be seen whether there is a point in Land a point in R that are less than distance dapart from each other. To this end, discard all points with xi<x-dor xi>x+d and sort the remaining points by y-coordinate.

• Now, go through this sorted list, and for each point, compute its distance to the seven subsequent points in the list. Let pM·qMbe the closest pair found in this way.

• The answer is one of the three pairs role="math" localid="1659237951608" {pL,qL},{pR,qR}{pM,qM}, whichever is closest.

(a) In order to prove the correctness of this algorithm, start by showing the following property: any square of size d×d in the plane contains at most four points of L.

(b) Now show that the algorithm is correct. The only case which needs careful consideration is when the closest pair is split between L and R.

(c) Write down the pseudocode for the algorithm, and show that its running time is given by the recurrence:

T(n)=2T(nl2)+0(nlogn)

Show that the solution to this recurrence is o(nlogzn).

(d) Can you bring the running time down to O(nlogn)?

Question: Use the divide-and-conquer integer multiplication algorithm to multiply the two binary integers 10011011and10111010 and .

A k−way merge operation. Suppose you have ksorted arrays, each with nelements, and you want to combine them into a single sorted array ofkn elements.

(a)Here’s one strategy: Using the merge procedure from Section 2.3, merge the first two arrays, then merge in the third, then merge in the fourth, and so on. What is the time complexity of this algorithm, in terms of kand n?

(b) Give a more efficient solution to this problem, using divide-and-conquer.

You are given two sorted lists of size mandn. Give an O(logm+logn)time algorithm for computing the k th smallest element in the union of the two lists.

Question: Solve the following recurrence relations and give a bound for each of them.

(a)T(n)=2T(n/3)+1(b)T(n)=5T(n/4)+n(c)T(n)=7T(n/7)+n(d)T(n)=9T(n/3)+n2(e)T(n)=8T(n/2)+n3(f)T(n)=49T(n/25)+n(3/2)logn(g)T(n)=T(n-1)+2(h)T(n)=T(n-1)+nc,whereisaconstant(i)T(n)=T(n-1)+cn,whereissomeconstant(j)T(n)=2T(n-1)+1(k)T(n)=T(√n)+1
See all solutions

Recommended explanations on Computer Science Textbooks

Theory of Computation

Read Explanation

Problem Solving Techniques

Read Explanation

Game Design in Computer Science

Read Explanation

Computer Systems

Read Explanation

Data Representation in Computer Science

Read Explanation

Computer Programming

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free