MCS-375 Take-home Test 2 (Fall 2011)

This test is closed-book and mostly closed-notes. You may, however, use a single 8 1/2 by 11 sheet of paper with hand-written notes for reference. (Both sides of the sheet are OK.)

You are allowed to use a computer for programming and testing, but not for looking up additional information beyond the Python documentation. For example, you are not allowed to read some other algorithms textbook online or use google to see if anyone has posted a solution to a similar problem.

You are not allowed to consult with any other person about the test, with the exception of the course instructor.

By 1:30pm on Thursday, November 17, 2011, you must send me an email containing the following items:

You are welcome to contact me if you have any questions about the test. In particular, if you are stuck on any part of a multi-part problem, I may be able to get you unstuck so that you can earn points for later parts.

You can earn eight points for each of the four problems.

  1. You will analyze AnotherScopedMap class. Unless I let any bugs slip in, it is functionally equivalent to the BadScopedMap and GoodScopedMap classes you worked with previously.

    For this problem, you may use the following simplified cost model for Python, which is different from the one you used in the homework. Each use of a dot (.) costs one unit, regardless of whether it is used on the left of an assignment or the right, and regardless of whether it is used to select a method or an attribute. Using a dot on the left of an update assignment operator such as += still only costs one unit, even though an old value needs to be fetched and a new value stored. If the dot operator appears in the body of an if statement, it only incurs one unit of cost if it is actually executed. If the dot operator appears in a loop, it incurs one unit of cost each time it is executed.

    Because there are five dots in the initialization method for ScopedMapNode, creating a ScopedMapNode costs five units. This means that the total cost of the put method is 11, because there are also six uses of dots directly in put. This cost of 11 is both the best case and the worst case because there is no variability.

    In answering the following questions, you should assume that exitScope is never called at level 0. That is, each call to exitScope matches an earlier enterScope.

    1. For each of the following methods, give the best-case and worst-case costs, which may be the same: isLocal, enterScope, retrieve, and getNestingLevel.

    2. Let's use the variable m to indicate the number of prior method invocations on a particular scoped map, not counting the __init__ method done when the scoped map was created. Give the best-case and worst-case costs, expressed as functions of m, for exitScope.

    3. Let's use the variable n to indicate the number of distinct ScopedMapNodes reachable starting from a particular scoped map. Give the best-case and worst-case costs, expressed as functions of n, for exitScope.

    4. Let's use the variable k to indicate the number of distinct ScopedMapNodes reachable starting from a particular scoped map, counting only nodes that have the same level as the scoped map does. Give the best-case and worst-case costs, expressed as functions of k, for exitScope.

    5. Professor de Javue has decided to use the potential-function method to analyze the amortized cost of these methods. She is sure that a suitable potential function will have one of the following forms: Cm, Cn, or Ck, where in each case, C is a positive constant that she will choose later in her analysis. The variables m, n, and k are as defined in the previous parts of this problem. Which form should she use for the potential function? Why?

    6. Using the form of potential function you chose in the previous part, which methods change the potential? For each of these methods, give a formula for how much the potential changes. Each formula should involve C and may also involve one of the variables m, n, and k. Each formula should have a positive value if the potential increases and a negative value if the potential decreases.

    7. What would be a suitable value for C so that the amortized cost of each method has a constant bound?

  2. A two-person game is played using a sequence of positive integers. The two players take turns until the sequence is empty. When it is each player's turn, he chooses either to take the first integer from the sequence or to take the first two integers from the sequence. Each player's goal is to maximize the sum of the integers he takes over the full game. We will call the value of a game the difference between the first player's sum and the second player's sum, assuming that both players play optimally. For example, if the sequence is 4, 3, 2, 1, then the first player's optimal choice is to take two integers (4 and 3); the second player's optimal response is also to take two integers (2 and 1), which ends the game. The value of this game is (4+3)−(2+1), which equals 4.

    1. Give an example sequence of positive integers in which the first player gets a worse sum by being greedy and taking two integers than he would by taking one integer. Assume that after this first move, both players play optimally.

    2. I have linked a recursive, top-down version of gameValue procedure. Write either a bottom-up dynamic programming version or a memoized top-down version. Your version should produce the same values as mine does for short lists of positive integers. However, your version should complete in a reasonable amount of time even for longer lists.

  3. Modify the DisjointSets implementation we programmed so that there is one new method, size. If d is an instance of the DisjointSets class, then d.size(v) should return the size of the set to which the value v belongs. If v is not in any set, a KeyError should be raised. In addition to writing the new method, you may change the stored representation and any other methods. However, you should not change the asymptotic running time of any of the existing methods.

  4. Suppose the SkipList class we programmed was changed so that it kept track of one more node in addition to the start and end nodes; this node is the last node. This would just be an additional pointer to one of the nodes on the list, the one that comes immediately before the end node. (Note that if the list is empty, the last node is the same as the start node.)

    To be sure you understood the previous discussion, note that the following property should always hold for any SkipList s: s.last.successors[0]==s.end

    1. Which method or methods can now be written more efficiently by making use of last?

    2. Which method or methods would now need to be do extra work in order to keep last up to date?

    3. For each method you listed in the first two parts of this problem, what would the new asymptotic running time of the method be? (Give big-Theta answers in terms of n, the number of key/value pairs in the SkipList.) Is each of your answers any different than the running time before the change? Explain your answers. Your explanations may include modified Python code, but they need not.