Compsci 100, Spring 2010, Recitation Feb. 26

submissions

Spreading News APT

In this part of recitation you'll answer a few questions to help you understand the SpreadingNews apt and to work toward a solution to it.

Understanding Structure and Input

  1. Consider the two supervisory structures below. The structure on the left corresponds. to the input [-1,0,1,2,3]. Explain why that's the case (in words) and what the input looks like for the supervisory structure on the right.

    two trees

  2. What is the answer for each of the inputs/structures above? Why?
  3. In the problem statement for the APT the input [-1,0,0,2,2] is shown with an answer of 3. That's a structure with 5 people (4 other than the manager) and an answer of 3. Draw a diagram and/or provide the input for a structure with 9 people (8 other than the manager) for which the answer is 5.

  4. In the last example from the APT, the input is reproduced below with the array-index beneath the corresponding array entry: 
     -1, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 12, 13, 14, 16, 16, 16

  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17  18  19  20  21  22  23

    A diagram of this structure is shown below, the answer to the problem for this structure is 7. Who should be called first, person 1 or person 2? Why?

    big diagram

    Toward a Solution

    Each person in the structure can be viewed as the manager of all those below in the diagrams shown above, e.g., 7 is the manager of five people in the diagram immediately above. This means you can view an index as the parameter to a recursive method that calculates the answer: public int minTime(int bossIndex) and the initial call of minTime(0) is the answer to the APT problem.

  5. If you know the minimum time for each of three subordinates, and these times are [10, 13, 17] (e.g., in minutes for them each to complete the task), which one of the three subordinates do you call first? Why? Who do you call second? Why?
  6. When does an employee take no time to complete the task of notifying subordinates? For example in the diagram with 24 employees above, which ones don't make any calls after receiving the news.
  7. Why is the answer to the problem 7 for the structure above?
  8. Describe in words and code how to create a structure from the array that's input to the problem so that it's straightforward (simple code) to find all the subordinates of the person/employee with index index, e.g., given a number/index find that person's subordinate-indexes.
  9. Given an array list of the times for all your subordinates, e.g., stored in subTimes below, explain why the call to sort shown is useful. public int minTime(int bossIndex) { ArrayList<Integer> subTimes = new ArrayList<Integer>(); for(int i : subOrdinates_of(bossIndex) { // pseudocode subTimes.add(minTime(i)); } Collections.sort(subTimes,Collections.reverseOrder()); // how do we use subTimes in solving problem?

Linked Questions

In all these problems assume that the inner classes Node and DNode exist as shown below. You'll write methods in a class LinkStuff for your solutions. You'll snarf a skeleton version of the code to write solutions in a group and then view them during recitation. You cannot use instance variables, all variables must be local to the methods you write. public class LinkStuff { public static class Node { int info; Node next; Node(int i, Node link) { info = i; next = link; } } public static class DNode { String info; DNode prev,next; public DNode(String s, DNode before, DNode after) { info = s; prev = before; next = after; } } // your methods here }

  1. Reversi

    2. Write the function makeReversed whose header follows. The function returns a list in which for each number k in the range [1..n], there are k nodes containing k, and the nodes are in reverse order: n, n-1, ..., 3, 2, 1

    For example:

    picture

    /** * Create a list whose first node contains a String representing * n, whose nodes are in reverse order, and in which for all * k in [1..n] there are k occurrences of a node containing k. * @param n is the number used to control creation of the list * @return the first node of the list created */ public Node makeReversed(int n)

  2. Two Links in One

    3. In a doubly-linked list each node has pointers to both the node before it and the node after it as in the picture below.

    double link

    Write a return to move the node pointed to by parameter list to the front of a linked list and return a pointer to list which is now the first node of the list. Be sure to update all links and watch out for special cases of the first ndoe (nothing to do) and the last node (no node after it).

    /** * Move node pointed to by list so that it's before front, return * list (which will be the first node if front was the first node). */ public DNode moveToFront(DNode front, DNode list) {