Instructions
CSC373 Fall’20 Assignment 1: Dinosaurian Dilemmas Due Date: 13th October 2020, 11:59pm ET
1. Typed assignments are preferred (e.g., PDFs created using LaTeX or Word), especially if your handwriting is possibly illegible or if you do not have access to a good quality scanner. Either way, you need to submit a single PDF named “hwk1.pdf” on MarkUS at https: //markus.teach.cs.toronto.edu/csc373-2020-09
2. You will receive 20% of the points for a (sub)question when you leave it blank (or cross off any written solution) and write “I do not know how to approach this problem.” If you leave it blank but do not write this or a similar statement, you will receive 10%. This does not apply to any bonus (sub)questions.
3. You may receive partial credit for the work that is clearly on the right track. But if your answer is largely irrelevant, you will receive 0 points.
Q1 [25 Points] Fruit Frenzy
Dinosaur Bobby is hungry and wants to eat some fruits. He knows about n fruit gardens. Each garden i is described by two integers: ei, the easiness of reaching garden i from where Bobby is, and qi, the number of fruits in garden i.
Bobby wants to pick a garden i to visit. But he wants to make a smart choice: he wants to make sure that no other garden j is simultaneously easier to get to (ej > ei) and has more fruits (qj > qi). Bobby wants your help in counting the number of gardens i that meet this requirement.
(a) [15 Points] Give an O(n log n) time divide-and-conquer algorithm for this problem. (b) [10 Points] Provide a brief justification of its correctness and running time.
Q2 [25 Points] Missing Member
The dinosaur society has reached a magical point where it consists of m = 2n dinosaurs, each with a distinct age from the set {0,1,…,2n − 1}. One day, an assembly is called, and only m − 1 dinosaurs show up. Chief Seema enlists your help to find the age of the missing dinosaur.
She has lined up the dinosaurs (including herself) in an arbitrary order. You can walk up to any dinosaur and query their age. However, the dinosaurs are ex-computer-scientists and like binary encodings. So they will only provide a single bit of their age at a time. That is, in one query, you can walk up to some dinosaur i and ask the j-th bit of their age, where i ∈ {1,…,m} and j ∈ {1,…,n}.
Design an algorithm to find the age of the missing dinosaur in O(m) queries and O(m) running time. [Note: Each dinosaur’s age is represented by n bits, so there are a total of mn bits. That means
you will need to be smart and not ask every dinosaur every bit of their age.]
1
Q3 [25 Points] Building Hospitals
There are n dinosaur societies which live along a common one-dimensional road. The members of society i live in the interval [si,fi], and these intervals can overlap. The chiefs of the societies recognize that they need to build hospitals in order to take care of their members. But resources are scarce, so they enlist your help.
Your goal is to design an algorithm which finds locations along the road where hospitals should be built such that each interval [si, fi] contains at least one hospital. Subject to this requirement, you need to minimize the number of hospitals built.
(a) [10 Points] Design a greedy algorithm for this purpose and analyze its worst-case running time. (b) [15 Points] Prove correctness of your algorithm.
Q4 [25 Points] Traveller’s Dilemma
Dinosaur Eli is organizing a road trip across Canada. She owns an electric car, which has a battery that can last for 200km on a single charge. If the car runs out of battery, she will be stranded. Luckily for her, n − 1 charging stations are located along the road she plans to take; the distance of the ith charging station from her starting point is d[i]. The distance of her final destination from her starting point is d[n]. Here, d[1] < d[2] < . . . < d[n].
Assume that she begins the trip with a full charge, and the trip is feasible because the distance between any two consecutive charging stations is at most 200km (i.e. d[i + 1] − d[i] ≤ 200 for all i).
(a) [10 Points] Design a greedy algorithm which takes the array d as input and finds locations of fewest possible charging stations where Eli should stop to full-charge the battery in order to successfully complete her trip. Analyze its worst-case running time.
(b) [10 Points] Prove correctness of your algorithm.
(c) [5 Points] Now suppose that there is a cost c[i] to charge the battery at charging station i, regardless of the current amount of power in the battery. Show that the greedy algorithm given in part (a) does not necessarily minimize the total cost of travel.
Bonus Question
Q5 [20 Points] No More Slaps, Please!
There are n dinosaurs in a line, sorted in a nondecreasing order of their age. You are given a number x and told that there is at least one dinosaur in the line whose age is x. Your goal is to find one such dinosaur.
At first glance, this may seem like a simple application of binary search that you, as a computer scientist, already know by heart. That is until you remember an important detail about the dinosaur society: Dinosaurs, unlike many humans, want to seem older and get offended if you guess them to be younger than they actually are. So if you approach dinosaur i and ask him “Are you x years old?”, three things can happen:
2
1. If he is younger than x, he says “Oh my, I’m flattered. But no, I’m younger than x.” 2. If his age is exactly x, he says, “Why yes! How did you know that?”
3. If he is older than x, he gets offended and slaps you.
Now, you are strong, but not that strong. You know you can withstand at most k dino-slaps. Any more slaps and you’re done for.
Design an algorithm to search a dinosaur of the given age x such that you are guaranteed to get slapped no more than k times. What is the asymptotic number of queries that your algorithm makes in the worst case as a function of k?
√
[Note: Think of k as a constant. As a warm start, design an O( n) algorithm for k = 1. To receive any partial credit, you need to satisfactorily solve the problem at least for k = 2.]
3