Tutorial #4 Problems

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 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.

• Section 4.7

Note that this section discusses the running problem we used in class for greedy algorithms, although with a very small twist. (Essentially, they consider edge weights to be “dissimilarities” rather than “similarities”.)

Next up, we’ll be reading Chapter 5. We’ll work through 5.1-5.4. We’ll also discuss the Master Theorem.

(Without mentioning it specifically, Section 5.2 of the textbook describes many pieces needed to derive the Master Theorem.)

Slides #9: Completing greedy clustering

NOTE: Problem 2 should ask about a bound on a solution produced by the greedy algorithm in terms of the last intra-category edge across which it merged. (You can answer the question as it stands, and it remains an interesting question.. just not useful for the rest of the worksheet!)

• Section 4.6

I’m backdating this for my own future reference, but it didn’t go up until 2 Feb. So, no reading question, but do read the section!

Some Old Exams

Here are some old exams and sample exams (from previous terms). These are not my exams; so, I haven’t reviewed them, I do not have additional materials related to them that might be missing, and I don’t know how well they relate to what we’ve done so far.

(I can say that we have not yet discussed decision-theoretic lower bounds and may not do so, although many of you likely saw Ω(n lg n) bound on sorting by comparisons in CPSC 221, which is a decision-theoretic lower bound.)

Some of these require the login “cpsc320” and the solutions password for our course to access, which is posted on Piazza: