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

This problem illustrates how to do the Fourier Transform (FT) in modular arithmetic, for example, modulo .(a) There is a number such that all the powers ω,ω2,...,ω6 are distinct (modulo ). Find this role="math" localid="1659339882657" ω, and show that ω+ω2+...+ω6=0. (Interestingly, for any prime modulus there is such a number.)

(b) Using the matrix form of the FT, produce the transform of the sequence (0,1,1,1,5,2) modulo 7; that is, multiply this vector by the matrix M6(ω), for the value of ωyou found earlier. In the matrix multiplication, all calculations should be performed modulo 7.

(c) Write down the matrix necessary to perform the inverse FT. Show that multiplying by this matrix returns the original sequence. (Again all arithmetic should be performed modulo 7.)

(d) Now show how to multiply the polynomials and using the FT modulo 7.

Practice with polynomial multiplication by FFT.

(a) Suppose that you want to multiply the two polynomials x + 1 and x2+1using the FFT. Choose an appropriate power of two, find the FFT of the two sequences, multiply the results component wise, and compute the inverse FFT to get the final result.

(b) Repeat for the pair of polynomials 1+x+2x2and 2 + 3x.

In our median-finding algorithm (Section 2.4), a basic primitive is the split operation, which takes as input an array S and a value V and then divides S into three sets: the elements less than V , the elements equal to V , and the elements greater than V . Show how to implement this split operation in place, that is, without allocating new memory.

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

Big Data

Read Explanation

Computer Programming

Read Explanation

Problem Solving Techniques

Read Explanation

Issues in Computer Science

Read Explanation

Computer Systems

Read Explanation

Algorithms in Computer Science

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