(40 points) In the game Angry Dogs, you launch dogs at cars that are arranged in
ID: 3749563 • Letter: #
Question
(40 points) In the game Angry Dogs, you launch dogs at cars that are arranged in a line. You get one point for every car within 100 feet where the dog lands. Suppose that you are given an array car[1. .n] with car locations (given in feet). a. Write an efficient and correct algorithm that minimizes the number of dogs launched while 3. achieving the maximum score What is the time complexity of your algorithm? Use asymptotic notation. Justify your answer Prove that your algorithm is correct. b. c.Explanation / Answer
3. a.
3. b. Time Complexity = O (n logn). In sorting the array, the best algorithm will even sort the worst case in O (n logn) complexity. And while iterating in the loop, binary search will do its work in O (logn) complexity and in the worst case, the loop will iterate n times. Hence the composite time complexity will be O (n logn).
3. c. According to the question, the ANGRY DOG has an impact in the range of 100 feet (both back and front), which means that 99 feet back + position of Dog + 99 feet front. So, starting from the first car and taking its position as pos, the next first car which won't be affected the the current Dog will be pos+200, and thus we will first find the first car at a position >=pos+200, and assign new dog for it. Every dog will cover the cars with positions in the range [pos,pos+200). Hence, this algorithm finds the minimum number of ANGRY DOGS required for the given orientation of cars in most efficient manner.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.