In class, we looked at the goal of attending as many parties as possible, when you...

 

Transcribed Image Text:

In class, we looked at the goal of attending as many parties as possible, when you couldn't be at two parties at the same time. There, we assumed that you had to stay for the entire time. An opposite type of problem is one where you just quickly want to "show your face" at each party, but don't intend to stay around at all. But in return, you now want to attend all of the parties, to win the "party animal" badge. Let's assume that you live far enough off campus that getting to USC is really the bottleneck. Once you're on campus, the locations of all parties on campus are close enough to each other that you can - for our purposes - drop in on a party in 0 time, and in 0 time go to any other party that may be happening, too. We'll model this as follows. There are n parties, with party i starting at time s; and finishing at time fi. Our model is that one "party trip" at time t means that you drive to campus, get there at time t, visit all parties that are ongoing at that time, and then immediately drive back home. So you never stay around on campus. You would like to find a smallest (minimum-cardinality) set of times at which to visit campus, so that you quickly drop in on every one of the parties. Give (and of course analyze, meaning prove correct and analyze the running time) an algorithm that runs in time O(n log n) and finds a smallest set of times to visit campus so that you can visit all parties. (2) [10 points] Solving this problem will likely be easier after Friday's Review Session, and even more so after Monday's lecture. Or you could read ahead in the textbook on the analysis of the Earliest Deadline First algorithm. In this problem, we will look at how to manipulate the outcome of an election. In many elections, voters can only vote for one candidate if so, there is really only one reasonable voting rule, which is to choose the candidate with the largest total. But as you probably know, this leads to a lot of speculating to avoid wasting one's vote on a candidate who won't win anyway. For that reason, some elections ask voters to rank all candidates from most favorite to least favorite; with this extra information, one can then do a better job picking a "good" candidate. There are a lot of different voting rules for choosing a candidate you may have heard about Single Transferable Vote (STV), also known as Ranked Choice voting. Another well-known method, and the one we will consider here, is the Borda Count, named after Jean-Charles de Borda, who invented it in the late 18th century. Assume that there are m 2 candidates and n voters. Each voter ranks all m candidates from most to least favorite. For voter v = 1,..., n, their order is a permutation Tv, and we write (i) for the candidate that voter v has in position i. Voter v's most favorite candidate is (1), and their least favorite is (m). Under the Borda count rule, candidate c gets m - 1 points for each first-place vote they get, m - 2 for each second-place vote they get, and so on; with 0 points for each last-place vote they get. The points are added up, and the candidate with the largest total number of points wins. As an example, suppose that there are three voters and four candidates, and the rankings of the voters are (A, B, C, D), (B, C, A, D), (C, D, A, B). Because m = 4, candidate A gets 3 + 1 + 1 = 5 points, B gets 2+3+0 = 5 points, C gets 1+2+3 = 6 points, and D gets 0+0+2 = 2 points. Here, C would win. Now assume that you are voter n, and your favorite candidate would be A. You would like A to win. You can see all the ballots of all other voters. The question is: is there some ranking you can put on your ballot such that A is the unique winner, i.e., A gets strictly more points than every other candidate (no ties)? Clearly, sometimes this will be impossible, and other times, it is possible. For instance, in the example above, if you were the fourth voter, you could write (A, B, D, C) on the ballot, and now, A would have 8 points, would have 7 points, C would have 6 points, and D would have Let's not worry about tie breaking for now. 3 points, so A would win. On the other hand, if everyone else had ranked A last and B first, there would have been nothing you could do. Give a polynomial-time algorithm to compute a ballot you can submit to make A win, or correctly conclude that no such ballot exists. Prove the correctness of your algorithm, and analyze its running time. In class, we looked at the goal of attending as many parties as possible, when you couldn't be at two parties at the same time. There, we assumed that you had to stay for the entire time. An opposite type of problem is one where you just quickly want to "show your face" at each party, but don't intend to stay around at all. But in return, you now want to attend all of the parties, to win the "party animal" badge. Let's assume that you live far enough off campus that getting to USC is really the bottleneck. Once you're on campus, the locations of all parties on campus are close enough to each other that you can - for our purposes - drop in on a party in 0 time, and in 0 time go to any other party that may be happening, too. We'll model this as follows. There are n parties, with party i starting at time s; and finishing at time fi. Our model is that one "party trip" at time t means that you drive to campus, get there at time t, visit all parties that are ongoing at that time, and then immediately drive back home. So you never stay around on campus. You would like to find a smallest (minimum-cardinality) set of times at which to visit campus, so that you quickly drop in on every one of the parties. Give (and of course analyze, meaning prove correct and analyze the running time) an algorithm that runs in time O(n log n) and finds a smallest set of times to visit campus so that you can visit all parties. (2) [10 points] Solving this problem will likely be easier after Friday's Review Session, and even more so after Monday's lecture. Or you could read ahead in the textbook on the analysis of the Earliest Deadline First algorithm. In this problem, we will look at how to manipulate the outcome of an election. In many elections, voters can only vote for one candidate if so, there is really only one reasonable voting rule, which is to choose the candidate with the largest total. But as you probably know, this leads to a lot of speculating to avoid wasting one's vote on a candidate who won't win anyway. For that reason, some elections ask voters to rank all candidates from most favorite to least favorite; with this extra information, one can then do a better job picking a "good" candidate. There are a lot of different voting rules for choosing a candidate you may have heard about Single Transferable Vote (STV), also known as Ranked Choice voting. Another well-known method, and the one we will consider here, is the Borda Count, named after Jean-Charles de Borda, who invented it in the late 18th century. Assume that there are m 2 candidates and n voters. Each voter ranks all m candidates from most to least favorite. For voter v = 1,..., n, their order is a permutation Tv, and we write (i) for the candidate that voter v has in position i. Voter v's most favorite candidate is (1), and their least favorite is (m). Under the Borda count rule, candidate c gets m - 1 points for each first-place vote they get, m - 2 for each second-place vote they get, and so on; with 0 points for each last-place vote they get. The points are added up, and the candidate with the largest total number of points wins. As an example, suppose that there are three voters and four candidates, and the rankings of the voters are (A, B, C, D), (B, C, A, D), (C, D, A, B). Because m = 4, candidate A gets 3 + 1 + 1 = 5 points, B gets 2+3+0 = 5 points, C gets 1+2+3 = 6 points, and D gets 0+0+2 = 2 points. Here, C would win. Now assume that you are voter n, and your favorite candidate would be A. You would like A to win. You can see all the ballots of all other voters. The question is: is there some ranking you can put on your ballot such that A is the unique winner, i.e., A gets strictly more points than every other candidate (no ties)? Clearly, sometimes this will be impossible, and other times, it is possible. For instance, in the example above, if you were the fourth voter, you could write (A, B, D, C) on the ballot, and now, A would have 8 points, would have 7 points, C would have 6 points, and D would have Let's not worry about tie breaking for now. 3 points, so A would win. On the other hand, if everyone else had ranked A last and B first, there would have been nothing you could do. Give a polynomial-time algorithm to compute a ballot you can submit to make A win, or correctly conclude that no such ballot exists. Prove the correctness of your algorithm, and analyze its running time.