Linear search algorithm with scans

Assignment Help Data Structure & Algorithms

Reference no: EM13703755

Algorithm: Consider the linear search algorithm with scans through an n-element array a to determine if element xis in a. We say that the algorithm require i steps if x is located at index i; i.e. a[i] = x, for i = 0, 1, . . . , n ?

1. Furthermore, the algorithm requires n steps if x is not found in a.

Assume 60% of all searches fail to locate the element x in a. Moreover, for the other 40% of searches, when x is found in a, it is equally likely to be in any of the array locations.

Let S denote the number of steps needed for a linear search over an array of size n, use the above facts to find i) the domain of S, ii) a probability distribution for the domain of S, and iii) E[S].

Please show me all the working and provide the answer.

Reference no: EM13703755

Questions Cloud

Relation between the objects : What will be said about the relation between the objects object1 and object2 - Make this program using java programming.

Compute the value of each piece of clothing : You decide to write a script in MATLAB that will compute the value of each piece of clothing.

Explain in words a divide-and- conquer algorithm : explain in words a divide-and- conquer algorithm that runs in O(log n) time, and that determines if there is an i for which a[i] = i. Argue that your algorithm is correct and provide supporting pseudo-cod

Create a class called numberset : You need to create a class called NumberSet. It needs an empty default constructor and an overloaded constructor that takes an integer argument and creates a vector with that many random numbers in it. So... if I created

Linear search algorithm with scans : Consider the linear search algorithm with scans through an n-element array a to determine if element xis in a. We say that the algorithm require i steps if x is located at index i; i.e. a[i] = x, for i = 0, 1, . . . , n ?

Write a function that accepts an array of integers : Write a function that accepts an array of integers and the size of the array and prints out a table listing how many values in the array fall in each of the following ranges:

Find the minimum sum of product expression : Find the minimum sum of product expression for the subsequent expression:

Determine the number of multiplications : Determine the number of multiplications used to find \(x^{2^{k}}\) starting with x and successively squaring (to find \(x^{2}, x^{4}, \) and so on). Is this a more efficient way to find \(x^{2^{k}}\) than by multiplying x by itself the appropri..

Call a unary language an arithmetic progression : Call a unary language an arithmetic progression if it is the set {\(x^{m+ni}\)} : i >= 0 for some m and n show that if a unary language is regular , then it is the union of a finite set and a finite number of arithmetic progressions

User Account

All Pages