Suppose you work at the Registry of Motor Vehicles (RMV), and you are in charge

Question

Suppose you work at the Registry of Motor Vehicles (RMV), and you are in charge with grading the written driving exam. From experience, you know that there are only two kinds of drivers: Boston Drivers and Out-of-Staters. There are m drivers taking this exam today, which has n questions. Boston Drivers always get fewer than n/2 questions correct. Out-of-Staters always get all n questions correct. There is no in-between. A deterministic algorithm would proceed as follows: Grade the first n/2 questions. If you see a wrong answer along the way, return boston. If you get through all n/2 with no wrong answers, return out-of-state. What is the worst-case run-time of the deterministic algorithm? Give a randomized version of this algorithm (it need not be in formal pseudocode, but can be similar to the bullet-points above). Is your algorithm "las vegas" style or "monte carlo" style? What is the expected run-time of your algorithm?

Explanation / Answer

10A
In the worst case the driver is out-of-state and thus has answerd all questions right. In that case the algorithm need to check atmost n/2 outputs before coming to a conclusion.

10B

We pick a random driver and review its outcome of mth answer. If the Answer is wrong return boston

The algorithm loops infinitely until it encounters wrong answer and returns boston driver. Since this loops indefititely the code is of la-vegas style.

I kept the answer short to remone any confusion. Please review it buddy. if you dont like the 2md algo, please let me know

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.