/*! This file is auto-generated */ .wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none} Q16E Question: You are given an infin... [FREE SOLUTION] | 91影视

91影视

Log out

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鈥檛 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.

Over 30 million students worldwide already upgrade their learning with 91影视!

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

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

Thesquare of a matrix A is its product with itself, AA.

(a) Show that five multiplications are sufficient to compute the square of a 2 x 2 matrix.

(b) What is wrong with the following algorithm for computing the square of an n x n matrix?

鈥淯se a divide-and-conquer approach as in Strassen鈥檚 algorithm, except that instead of getting 7 subproblems of size n2, we now get 5 subproblems of size n2 thanks to part (a). Using the same analysis as in Strassen鈥檚 algorithm, we can conclude that the algorithm runs in time O (nc) .鈥�

(c) In fact, squaring matrices is no easier than matrix multiplication. In this part, you will show that if n x n matrices can be squared in time S(n) = O(nc), then any two n x n matrices can be multiplied in time O(nc) .

  1. Given two n x n matrices A and B, show that the matrix AB + BA can be computed in time 3S(n) + O(n2 ) .
  2. Given two n x n matrices X and Y, define the 2n x 2n matrices A and B,L as follows:
    A=X000andB=0Y00
    What is AB + BA, in terms of X and Y?
  3. Using (i) and (ii), argue that the product XY can be computed in time 3S(2n) + O(n2 ). Conclude that matrix multiplication takes time O(nc ).

Given a sorted array of distinct integersA[1,...,n] , you want to find out whether there is an indexi for which A[i]=i. Give a divide-and-conquer algorithm that runs in time O(logn).

Practice with the fast Fourier transform.

(a) What is the FFT of (1,0,0,0)? What is the appropriate value of 蝇in this case? And of which sequence is (1,0,0,0)the FFT?

(b)Repeat for (1,0,1,-1).

What is the sum of the nth roots of unity? What is their product if n is odd? If n is even?
See all solutions

Recommended explanations on Computer Science Textbooks

Cloud Services

Read Explanation

Problem Solving Techniques

Read Explanation

Computer Network

Read Explanation

Game Design in Computer Science

Read Explanation

Algorithms in Computer Science

Read Explanation

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