Write pseudo code for a procedure random-search

Assignment Help Mathematics
Reference no: EM131565851

Question: Searching an unsorted array

This problem examines three algorithms for searching for a value x in an unsorted array A consisting of n elements. Consider the following randomized strategy: pick a random index i into A. If A[i] = x, then we terminate; otherwise, we continue the search by picking a new random index into A. We continue picking random indices into A until we find an index j such that A[j] = x or until we have checked every element of A. Note that we pick from the whole set of indices each time, so that we may examine a given element more than once.

a. Write pseudo code for a procedure RANDOM-SEARCH to implement the strategy above. Be sure that your algorithm terminates when all indices into A have been picked.

b. Suppose that there is exactly one index i such that A[i] = x. What is the expected number of indices into A that we must pick before we find x and RANDOM-SEARCH terminates?

c. Generalizing your solution to part (b), suppose that there are k _ 1 indices I such that A[i] = x. What is the expected number of indices into A that wemust pick before we find x and RANDOM-SEARCH terminates? Your answershould be a function of n and k.

d. Suppose that there are no indices i such that A[i] = x. What is the expected number of indices into A that we must pick before we have checked all elements of A and RANDOM-SEARCH terminates?

Now consider a deterministic linear search algorithm, which we refer to as DETERMINISTIC-SEARCH. Specifically, the algorithm searches A for x in order, considering A[1],A[2],A[3], ...,A[n] until either it finds A[i] = x or it reaches the end of the array. Assume that all possible permutations of the input array are equally likely.

e. Suppose that there is exactly one index i such that A[i] = x. What is the average-case running time of DETERMINISTIC-SEARCH? What is the worst case running time of DETERMINISTIC-SEARCH?

f. Generalizing your solution to part (e), suppose that there are k _ 1 indices I such that A[i] = x. What is the average-case running time of DETERMINISTICSEARCH?What is the worst-case running time of DETERMINISTIC-SEARCH?Your answer should be a function of n and k.

g. Suppose that there are no indices i such that A[i] = x. What is the average-case running time of DETERMINISTIC-SEARCH? What is the worst-case running time of DETERMINISTIC-SEARCH? Finally, consider a randomized algorithm SCRAMBLE-SEARCH that works by first randomly permuting the input array and then running the deterministic linear search given above on the resulting permuted array.

h. Letting k be the number of indices i such that A[i] = x, give the worst-case and expected running times of SCRAMBLE-SEARCH for the cases in which k = 0 and k = 1. Generalize your solution to handle the case in which k = 1.

i. Which of the three searching algorithms would you use? Explain your answer.

Reference no: EM131565851

Questions Cloud

Determine two key ways that contingency planning helps : Determine two key ways that contingency planning helps to achieve the overarching goals of a company. Provide a rationale for your response.
By what amount will the earnings be increased : Mike asks Billy to help him run his lemonade stand. He'll either pay him 2/5 of ½ of the stand's profits, or 1/3 of ¾ of the stand's profits.
What other statistic can you name that is misleading why : US government keeps statistics on many people in America. One interesting statistic is poverty rate. What other statistic can you name that is misleading? Why?
Prepare the year-end balance sheet : Prepare the year-end balance sheet for 2015. Be sure to use proper headings. Calculate using Excel formulas, the NPV of each of the 3 projects
Write pseudo code for a procedure random-search : This problem examines three algorithms for searching for a value x in an unsorted array A consisting of n elements. Consider the following randomized strategy.
Explain police executive facing more budget cuts : If you were a police executive facing more budget cuts, how would you go about deciding where to make your cuts? What would you cut first, second, then third
Does the daughters boyfriend have any rights : Should the staff encourage the mother to inform the daughter of both her and her daughter's HIV status?
What are the steps in the strategic management process : What are the steps in the strategic management process? What are key element of an external analysis and why is external analysis important to a strategic plan?
What is probability that three jurors are mexican americans : Assume that 12 jurors are selected from a population in which 50?% of the people are? Mexican-Americans. The random variable x is the number of?

Reviews

Write a Review

Mathematics Questions & Answers

  Questions on ferris wheel

Prepare a Flexible Budget Gator Divers is a company that provides diving services such as underwater ship repairs to clients in the Tampa Bay area.

  Logistic map

This assignment has two question related to maths. Questions are related to bifurcation cascade and logistic map.

  Finding the probability of cards

This assignment has questions related to probabiltiy.

  Systems of ode

Find all the xed points, and study their stability and Draw the phase portrait of the system, as well as the graphs of the solutions in all relevant cases.

  Derive the boolean expression

Derive the Boolean Expression and construct the switching circuit for the truth table stated

  System of equations

Evaluate which equations are under-identified, just-identified, and over-identified.

  Linear programming problem

Linear programming problem consisting of only two constraints with one objective function.

  Find the natural domain

Find the natural domain of the given functions.

  Introduction to numerical methods

Compute the coecients of the polynomials using the term recurrence relation.

  Chart of the topological manifold

De?nition of smoothness of functions on a smooth manifold is chart independent and hence geometric.

  Mathematics in computing

Questions related on mathematics in computing.

  Complex problems

Complex problems

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd