Note: This tutorial will last for two weeks (2 Feb through 13 Feb). Your tutorial section may end up working on the midterm practice problems one week and the tutorial the other (or even reviewing especially challenging exam problems). Enjoy!

1. Alice wants to throw a party and is deciding whom to call. She has n people to choose from, and she has made up a list of which pairs of these people know each other. She wants to pick as many people as possible, subject to two constraints: at the party, each person should have at least five other people whom they know and five other people whom they don’t know. Give a greedy algorithm that takes as input the list of n people and the list of pairs who know each other and outputs the best choice of party invitees. If there is no subset that satisfies the conditions, then your algorithm should return the empty set. Hint: Try to identify people who should not be invited.
2. Timing circuits are a crucial component of VLSI chips. Here is a simple model of such a timing circuit. Consider a complete balanced binary tree with n leaves, where n is a power of 2. Each edge e of the tree has an associated length l(e) which is a positive integer. The distance from the root to the given leaf is the sum of the lengths of all the edges on the path from the root to the leaf. The root generates a clock signal that is propagated along the edges to the leaves. We will assume that the time it takes for the signal to reach a given leaf is proportional to the distance from the root to the leaf. For instance, in the following tree, the clock signal will take 4 units of time to reach node b, but only 2 units of time to reach f.If all leaves do not have the same distance from the root, as was the case in the example, then the signal will not reach the leaves at the same time, and this is a big problem. We want the leaves to be completely synchronized, and all to receive the signal at the same time. To make this happen, we will have to increase the lengths of certain edges, so that all root-to-leaf paths have the same length (we are not able to shrink edges lengths). If we achieve this, then the tree (with its new edge lengths) will be said to have zero skew. Our goal is to achieve zero skew in a way that keeps the sum of all the edge lengths as small as possible.Give an algorithm that increases the lengths of certain edges so that the resulting tree has zero skew, and the total edge length is as small as possible. For instance, the unique solution for the tree in the figure would be to take the three length 1 edges and increase each of their lengths to 2. The resulting tree has zero skew, and the total edge length is 12, the smallest possible.

1. Consider the problem of making change for n cents, using the least number of coins. The input to this problem is the integer n, and the output is a sequence of coin values (where each value is allowed to appear multiple times) whose sum adds up to n.
   1. Describe a greedy algorithm to make change consisting of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent, a blast from the past).
   2. Give an example showing that there are set of coin values (although obviously not quarters, dimes, nickels, and pennies) for which the greedy algorithm does not always return a solution using the least possible number of coins.
2. In the Exhibition Guarding Problem, we are given a line L that represents a long hallway in a show room. We are also given an unordered set X = {x₀, x₁, … x_n-1} of real numbers that represent the positions of precious objects or sculptures in this hallway. Suppose that a single guard can protect all the objects within distance at most d of his or her position, on both sides.
   1. Design an algorithm for finding a placements of guards that uses the minimum number of guards to guard all the objects with positions in X.
   2. Analyze the running time of your algorithm as a function of n, the number of objects that need guarding.
   3. Prove that your algorithm works (write as complete an argument as you can in the time available in the tutorial).

1. Rank the following functions by order of growth. That is, order them so that f₁ ∈ O(f₂), f₂ ∈ O(f₃), etc. Make sure to indicate whether or not f_i ∈ Θ(f_i+1). For instance you could use the notation O(n) ⊂ O(n^2) = O(2n^2) ⊂ O(n^4)...
   

   n3 – n √ n	n!	log (log n)	1.01n
   √ n log n	17	4913n289	32n-17
   1.011.01n	√ n	3n	nn
   n18/17	n log17 n	32n	n3 + log n

2. Prove that for each fixed value of k > 0, 1^k + 2^k + … + (t-1)^k + t^k ∈ Θ(t^k+1). Hint: do not use induction. Instead, treat k as a constant, and do O and Ω separately. (Remember that for Ω bounds, it is legal to drop positive terms and reduce the size of positive terms, since you can guarantee that the resulting function is still a lower bound on the original.)
3. Analyze the running time of the following algorithm as a function of n, assuming that each arithmetic operation takes constant time. Use O, Ω or Θ notation as appropriate to express your result as simply and as precisely as possible. Give an informal argument (not necessarily a full proof) to support your answer. (It may help to think about the “measure of progress” approach the book used to analyze the while loop in the Gale-Shapley Algorithm.)

   Algorithm Strange(n)
       sum ← 0
       while (n > 3) do
           sum ← sum + n
           if (n is even) then
               n ← n / 2
           else
               n ← n + 3
           endif
       return sum
   

Problems for tutorial #1

1. Consider the Coop Student/Company Matching Problem: n students apply for jobs at m companies, where company i is looking for n_i COOP students. There are at least enough students to fill all of the positions (and there may be too many). Every student has a ranking of companies in order of preference, and each company has a ranking of students in order of preference. An assignment of students to companies is stable if neither of the following situations arises:
   • There are two students s and s' and a company c such that s is assigned to c, s' is unemployed, and c prefers s' to s.
   • There are two students s and s', and companies c and c', such that s is assigned to c, s' is assigned to c', s prefers c' to c, and c'prefers s to s' (the usual type of instability).

   Describe an efficient algorithm that will produce a stable assignment of students to companies, first using a reduction and the Gale-Shapley Algorithm, and then by modifying the G-S Algorithm so that it works directly on this problem.

2. Prove or disprove each of the following two statements. That is, either prove that the statement is true, or give an example to show that it is false. Hint: exactly one of the statements is true.
   1. In every instance of the Stable Matching Problem, there is a stable matching containing a pair (w, m) such that w is ranked first on the preference list of m and m is ranked first on the preference list of w.
   2. Consider an instance of the Stable Matching Problem in which there exists a man m and a woman w such that m is ranked first on the preference list of w and w is ranked first on the preference list of m. Then in every stable matching S for this instance, the pair (w, m) belongs to S.
3. (Induction review) Suppose you begin with a pile of n stones, and split this pile into n piles of one stone each by successively splitting a pile of stones into two smaller piles. Each time you split a pile you multiply the number of stones in each of the two smaller piles you form, so that if these piles have r and s stones in them, respectively, you compute rs. Show that no matter how you split the pile, the sum of the products computed at each step equals n(n-1)/2. Here is an example that shows how the computation proceeds:
   

   

   The sum is 21+2+12+1+3+2+2+1+1 = 45, which is indeed 10 * 9 / 2.