Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CompSci 161 Design and Analysis of Algorithms Problem Set 6
Due date: Wednesday, March 1 at 10:30 AM. You will need to submit this via GradeScope. Late problem sets are not accepted.
In CompSci161, your response to each numbered question must be contained within a single piece of paper. Each numbered question must be responded to on a separate page. When you submit to GradeScope, you will need to inform the system which page of your scanned PDF contains the response you want graded. On occasion, we might request you to tag two (or more) parts, even though we know the two parts will be on the same page; when that happens, it usually means we are going to grade the parts separately. Failure to follow these directions will be treated as non-submission for the question(s) affected.
Please review the syllabus and course reference for the expectations of assignments in this class. Remember that problem sets are not online treasure hunts. You are welcome to discuss matters with classmates, but remember the Kenny Loggins rule. Remember that you may not seek help from any source where not all respondents are subject to UC Irvine’s academic honesty policy.
1. I am teaching a class that has n teaching assistants, each of whom hold office hours outside, at JavaCity. The ith TA holds office hours starting at time Si and ending at time Ei . Each TA holds exactly one office hour (which may last any amount of time, not necessarily one hour, and different TAs may have different interval lengths, which may overlap with one another). Attendance has been low because students, being ICS majors, are afraid of the sun, so the department announces that all TAs who do not have a student visit them this week will be fired1 . Because all of our teaching assistants are awesome2 , we want to ensure that none get fired. However, due to student fears of the sun, we want to minimize the total number of visits made to TAs.
For purposes of this problem, assume each TA’s office hour time is one continuous interval with no breaks, and that a student visiting the sundeck at time t counts as visiting all TAs whose office hours interval contains t. Also assume that student visits are “instantaneous,” in the sense that the amount of time a student stays in the sun is negligible – formally, each student visits the deck at a single point in time. This also helps to avoid exposing a student to the sun unnecessarily.
You propose the following: first, we sort all of the intervals by end time. We send a student to attend office hours at the moment immediately prior to the end of the first ending interval. We remove from our input all TAs who overlap with this time, and if the remaining set is non-empty, we repeat.
Prove that the greedy algorithm in the previous statement minimizes the number of students we need to send to visit TAs. For purposes of this homework this quarter, it is sufficient to demonstrate that for any optimal solution, there is an equally optimal choice of student visits that includes your first choice.
2. We’re asked to help the captain of the UCI’s tennis team to arrange a series of matches against Long Beach State’s team3 . Both teams have n players; the tennis rating (a positive number, where a higher number can be interpreted to mean a better player) of the ith member of UCI’s team is ai and the tennis rating for the kth member of LBSU’s team is sk. We would like to set up a competition in which each person plays one match against a player from the opposite school. Because we get to select who plays against whom, our goal is to make sure that in as many matches as possible, the UCI player has a higher tennis rating than their opponent.
One proposal has been to sort both rosters by tennis rating, and then pair our best player agaisnt their best player, our second best against their second best, and so on in that fashion. Give a complete counter-example to demonstrate that this does not solve the problem stated here. 3Not really.