fx Y
X
Xm LY Yul
Say M is either
an opt solution XmYn EM or
0PTC
XmYn M
Define
Discussion 7
1. When their respective sport is not in season, USC’s student-athletes are very involved in their community, helping people and spreading goodwill for the school. Unfortunately, NCAA regulations limit each student-athlete to at most one community service project per semester, so the athletic department is not always able to help every deserving charity. For the upcoming semester, we have S student-athletes who want to volunteer their time, and B buses to help get them between campus and the location of their volunteering. There are F projects under consideration; project i requires si student- athletes and bi buses to accomplish, and will generate gi > 0 units of goodwill for the university. Our goal is to maximize the goodwill generated for the university subject to these constraints. Note that each project must be undertaken entirely or not done at all — we cannot choose, for example, to do half of project i to get half of gi goodwill.
2. Suppose you are organizing a company party. The corporation has a hierarchical ranking structure; that is, the CEO is the root node of the hierarchy tree, and the CEO’s immediate subordinates are the children of the root node, and so on in this fashion. To keep the party fun for all involved, you will not invite any employee whose immediate superior is invited. Each employee j has a value vj (a positive integer), representing how enjoyable their presence would be at the party. Our goal is to determine which employees to invite, subject to these constraints, to maximize the total value of invitees.
3. You are given a set of n types of rectangular 3-D boxes, where the ith box has height h(i), width w(i) and depth d(i) (all real numbers). You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. It is also allowable to use multiple instances of the same type of box.
Imagine starting with the given decimal number n, and repeatedly chopping off a digit from one end or the other (your choice), until only one digit is left. The square-depth SQD(n) of n is defined to be the maximum number of perfect squares you could observe among all such sequences. For example, SQD(32492) = 3 via the sequence
32492 → 3249 → 324 → 24 → 4
since 3249, 324, and 4 are perfect squares, and no other sequence of chops gives more than 3
perfect squares. Note that such a sequence may not be unique, e.g. 32492 → 3249 → 249 → 49 → 9
also gives you 3 perfect squares, viz. 3249, 49, and 9.
Describe an efficient algorithm to compute the square-depth SQD(n), of a given number n, written as a d-digit decimal number 𝑎𝑎1𝑎𝑎2 … 𝑎𝑎𝑑𝑑. Analyze your algorithm’s running time. Your algorithm should run in time polynomial in d. You may assume the availability of a function IS_SQUARE(x) that runs in constant time and returns 1 if x is a perfect square and 0 otherwise.