This sununer, after having passed CS341 with a wonderfully high mark, you decide to take on another test of endurance by walking along El Camino de Santiago'. This trail traditionally starts in St Jean Pied de Port and finishes in Santiago de Compostela. The trail is about 780 km long and travels across most of Northern Spain. Suppose you decide to hike at most dim each day. At the end of each day, you will rest in one of the several albergues2 that can be found in the many villages along the Camino. Being a diligent CS student, you understand the importance of collecting data and so, before the journey, you will have generated a list of n albergues. Each entry in the list is simply the name of the I' albergue and its distance from the starting point: x[i] measured in km. Describe a greedy algorithm that will give you a list of m albergues specifying where you will rest if you wish to do the walk in the minimum number of days. Provide an inductive proof that your algoritlun works.
To make answers uniform, everyone should assume that the walk starts from the first albergue at St Jean Pied de Port. So x[1] = 0 and the output list of m albergues should begin with this albergue. You may also assume that the maximum distance between two consecutive albergues is less than d.
The year is 2029. Ex-Blade Runner Rick Deckard has been sent by the Tyrell Corporation to the planet Tyrell-III to identify conunon models of replicants (http://en.wikipedia.orgiwiki/Replicant).
Tyrell-III has n replicants and each has a particular model specification. There are many models. Unfortunately, there was an insurgency on the planet and some of the replicants destroyed a critical database that held replicant data. Because of this, the
Tyrell Corporation does not know the model specifications for the replicants but it does know that there are 13 "conunon" models. Decker is told that a model is said to be common if there are at least n/13 instances of that model.
Deckard has been given a very sophisticated electronic device that, when attached to two replicants, will tell Deckard whether the two replicants have the same model specification. This operation is called a query. Unfortunately (again), replicants tend to be somewhat uncooperative and Deckard can only carry out a query at substantial risk to the continuation of his life. Consequently, the Tyrell Corporation wants him to identify all cominon models using the minimum number of queries.
We model the problem as follows:
We have an array R[l..n] of n entries (each entry being a particular model specification). The only possible operation allowed on R is a query of the form: Check(R[i],R[j]) that returns True if R[i] and R[i] are equal (the corresponding replicants have the same model specification) and False otherwise. For an array R of size n, an entry e is called common if at least n /13 entries of R are equal to e. We want to design an algoritlun that returns all common entries using 0(n log n) calls to Check.
a) Prove that there can be at most 13 distinct common entries in R.
b) Let e be a common entry in R[1..n]. Prove that e is a common entry in at least one of the arrays R[1..Ln/2_1] andR[Ln/2_1+1..n].
c) Give a precise pseudo-code description of a divide-and-conquer algoritlun that finds all common entries of an array R[1..n] in time e(n log n). Prove that your algorithm is correct and analyze its time complexity. Hint: Use part (b) in the design and part (a) in the analysis of your algorithm.