• Cornell University

• CS 4820

Introduction to Algorithms Problem Set 7 (3 problems)
CS 4820 Fall 2018 Due 11:59pm Thursday, October 25
Your homework submissions need to be typeset (hand-drawn figures are OK). See the course web
page for suggestions on typing formulas.
The solution to each question need to be uploaded to CMS as a separate pdf file. To help provide
anonymity in your grading, do not write your name on the homework (CMS will know it’s your submission). (Questions with multiple parts need to be uploaded as a single file.) Remember that when a
problem asks you to design an algorithm, you must also prove the algorithm’s correctness and analyze
its running time. The running time must be bounded by a polynomial function of the input size.
(3 from last time) Scheduling Interviews II. In Problem 2 from problem set 6, we were assigning
candidates to interviewers for a company without scheduling times for the interviews. In this problem,
you are asked to set up a more detailed schedule. As in the previous problem, you are scheduling
initial phone interviews for n job candidates at a company, with k ≤ n potential recruiters. Each
candidate needs only one interview for now: concretely, each candidate needs to be matched to exactly
one recruiter to be interviewed. The candidates are applying for different kinds of jobs, and recruiters
are qualified to interview candidates only for some of the jobs. For each candidate i, you are given a
list Li of the recruiters who are qualified to interview that candidate. You also don’t want to overload
the recruiters, so each recruiter j has a limit qj of the maximum number of interviews he or she can do.
Each interview will take one hour, and will be scheduled in one of T possible non-overlapping onehour time slots h1; : : : hT , each starting at the top of the hour (e.g. 10 AM, 1 PM, 5 PM . . . ). In
addition to the input above, each interviewer and each candidate is asked to list the hours that they
would be able to interview or be interviewed. Please note that each interviewer is asked to list strictly
more than qj possible slots to make scheduling easier.
Give an algorithm that finds an interview schedule if one exists. Let m = Pi jLij. Your algorithm
should run in time polynomial in n; k; m; and T.