CSC373

Assignment 1

Instructions

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/2022-05.

2. You will receive 20% of the points for a (sub)question when you leave it blank (or cross o↵

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 [20 Points] Decide the Candidate(s)!

Imagine you are the election ocer of a residential township with n eligible voters. There has

already been a round of preliminary voting in which each voter has given you the name of one

person who they would like to see run as a candidate in the upcoming election. As a result, you

have a list of n names (a name can, of course, repeat multiple times in this list – especially the

popular ones!). Any person who receives (strictly) more than n/3 votes in the preliminary voting

is to be declared a candidate. Note that hence, there can only be 0, 1, or 2 candidates as a result

of preliminary voting. Your task as the election ocer is to figure out if there even is someone who

is to be declared a candidate, and if so, who the candidate(s) is/are.

Note that the brute-force way to do this takes O(n2) time: for every name on the list, you run

through the entire list, count how many times it appears on the list, and check if the count is

strictly larger than n/3.

(a) [10 Points] Give a divide-and-conquer algorithm that solves this problem in O(n log n) time.

(b) [5 Points] Analyze the running time of your algorithm (and provide the recurrence relation).

(b) [5 Points] Briefly justify why your algorithm is correct.

Q2 [20 Points] Treasure hunt!

A treasure hunter has a map of n treasures. For each treasure i, the treasure hunter assigns two

integer valued parameters, namely the easiness xi to obtain the treasure, and its value yi. The

treasure hunter is organizing their trip and wants to identify treasures that are valuable to them.

Specifically, a treasure i is valuable if there is no other treasure j with xj xi and yj yi. The

treasure hunter wants to count the number of valuable treasures on their map.

1

(a) [10 Points] Give an ecient divide-and-conquer algorithm to count the number of valuable

treasures. You may assume that two distinct treasures di↵er in at least one of the two parameters

i.e., for distinct i and j, either xi 6= xj or yi 6= yj .

(b) [5 Points] Analyze the running time of your algorithm (and provide the recurrence relation).

(c) [5 Points] Briefly justify why the algorithm given in part (a) is correct.

Q3 [20 Points] Two Classrooms Only!

Here is a variant on the problem of Interval Scheduling. Suppose we now have two classrooms

available, and we want to schedule as many lectures as we can. As before, the input is a collection

of intervals [s1, f1), [s2, f2),…, [sn, fn) where n 1 and all si < fi are non-negative integers.

A schedule is now defined as a pair of sets (A1, A2), with A1 and A2 being the sets of lectures

scheduled in classrooms 1 and 2, respectively. A schedule is said to be valid if it satisfies the

obvious constraints:

A1, A2 ✓ {1, 2,…,n},

A1 \ A2 = ; (i.e., a lecture can only be scheduled in one classroom), and

for all i 6= j such that i, j 2 A1 or i, j 2 A2, lectures i and j do not overlap (i.e., the lectures

scheduled in a classroom are compatible with each other).

(a) [8 Points] Design a greedy algorithm to solve this problem i.e., on input [s1, f1),…, [sn, fn),

your algorithm produces a valid schedule with the maximum number of lectures.

(b) [2 Points] Analyze the running time of your algorithm.

(c) [10 Points] Prove the correctness of your algorithm.

Q4 [20 Points] Help Your Professor!

Your Professor has agreed to assign as much of his TAs’ time as necessary to ensure that his course’s

Piazza page is monitored around the clock (24 hours a day, 7 days a week) throughout the term.

Suppose that his TAs have given him their availabilities, specified as intervals [si, fi) where si < fi

are the start and end times of each available time slot, over some suitable range of non-negative

integers.

Your Professor would like to draw up a monitoring schedule with the following properties:

at every point in time, there is at least one TA available to monitor the course Piazza page,

i.e., there are no gaps in the schedule, although it’s okay if there is overlap, and

the TAs are not overworked, i.e., the schedule uses as few available time slots as possible

to achieve the first property, so that there are enough TA hours left over to help out with

marking.

Note that this problem is a “dual” to the interval scheduling problem: with the same kind of

input – intervals [s1, f1),…, [sn, fn) – we are asked a complementary question – to find a subset

2

of intervals that totally cover the range from the earliest start time to the latest finish time, with

overlap allowed, using as few intervals as possible.

(a) [5 Points] Give an ordering of the intervals for which the natural greedy algorithm corresponding

to this ordering does not always find an optimal solution – include a description of some specific

input for your algorithm, show the solution found by the greedy algorithm, and justify that it is

not optimal.

(b) [5 Points] Design a greedy algorithm that solves this problem, i.e., on input [s1, f1), …, [sn, fn),

your algorithm either produces a valid schedule that uses the smallest number of intervals, or it

correctly states that no such schedule is possible.

(c) [2 Points] Analyze the running time of your algorithm.

(d) [8 Points] Prove the correctness of your algorithm.

Bonus Question

Q5 [20 Points] Voltage Optimization!

You have recently branched out into manufacturing bulbs! Your R&D department has produced

several di↵erent designs. They don’t know how much voltage each design can withstand, but using

some physics, they can compare di↵erent designs in terms of their maximum voltage.

You have, in front of you, n bulbs sorted in a non-increasing order of the maximum voltage they

can withstand. Your village uses 120V. You want to find the index r such that bulbs 1 through

r can withstand 120V, but bulbs r + 1 through n cannot. In O(1) time, you can test any bulb

at 120V. Your first thought is to do a binary search in O(log n) time, but the problem is that

every time you test a bulb that cannot withstand 120V, the bulb burns out. You want to limit the

number of bulbs wasted. Of course, you can do a linear search and solve the problem while wasting

at most one bulb, but that is too slow.

Suppose you are willing to waste at most k bulbs, where k is a constant. Design an algorithm for

this problem. What is the asymptotic number of bulbs your algorithm tests in the worst case as a

function of k?

[Note: As a warm start, design an O(

pn) algorithm for k = 2. To receive any partial credit, you

must solve the problem for at least k = 3 with an o(

pn) algorithm.]

3