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 7
Due date: Wednesday, March 8 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. We’re asked to help the captain of the UCI’s tennis team to arrange a series of matches against Long Beach State’s team1 . 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. Give an efficient greedy algorithm for this problem and prove that it is correct (maximizes the number of matches in which our team has the player with the higher tennis rating).
For CompSci 161 this quarter, for the proof, it is sufficient to demonstrate that the repair of an arbitrary inversion in any alternate ordering, compared to yours, produces an ordering that is no worse. You may use the fact from lecture that any permutation that differs from yours has a consecutive pair of elements that are inverted relative to yours, however for this particular problem, the proof may not need the fact that they are adjacent.
2. Design a strategy that minimizes the expected number of questions you will ask in the following game. You have a deck of cards that consists of one one, two twos, three threes, and so on up to nine nines for a total of 45 cards. Someone draws a card from the shuffled deck and looks at its value (hiding it from you). The goal is to determine the value of the card through asking a series of questions, each of which must be answerable with “yes” or “no” (such as “Is the card a nine?”).
To answer this question, you should express your strategy as a decision tree. You may either explicitly draw the decision tree or describe its construction in sufficient detail so that I could draw it from your description. If you draw the tree instead of describing its construction, explain in a few sentences (2-4) how you came up with the tree.
Furthermore, briefly explain why this minimizes the expected number of questions you will ask in this game. You are not required to give a formal proof. 1Not really.
Hint: The first question to ask in the optimal decision tree is “Is the card one of {4, 5, 9}?” Equivalently, the question can be “Is the card one of {1, 2, 3, 6, 7, 8}?” Any incorrect solutions that disregard this hint are ineligible for partial credit on this question.