Compsci 100, Fall 2009, September 18

You can work with one or two people in answering recitation questions.

Name: _____________________  Netid: _________________


Name: _____________________  Netid: _________________
 

Name: _____________________  Netid: _________________


Runtime

  1. Given the method below determine the value returned by the call calculate(2043). What is the runtime complexity of this code for the call calculate(N). Use big-Oh, justify your answer. public int calculate(int n) { int prod = 1; while (prod < n) { prod *= 2; } return prod; }
  2. The method zcal is shown below, the call zcal(5) evaluates/returns 15. A series of questions related to zcal follows the method. public int zcal(int n){ if (n == 0) return 0; return n + zcal(n-1); }
    1. Using big-Oh, what is the value returned by the call zcal(N)? Justify.
      
      
      
      
    2. Using big-Oh, what is the runtime of the call zcal(N)?
      
      
      
    3. Using big-Oh, what is the value returned by the call zcal(zcal(N))? Justify.
      
      
      
    4. Using big-Oh, what is the runtime of the call zcal(zcal(N))? Justify.
      
      
      
      
  3. The method duplicate in the code shown below changes parameter list so that it's doubled in place -- for example, the list
      ("ape", "bat", "cat", "dog")
    
    is changed to the list below as a result of the call duplicate(list).
      ("ape", "ape", "bat", "bat", "cat", "cat", "dog", "dog")
    
    The method duplicate is called with both an ArrayList and a LinkedList as parameters -- the times for duplicating the different lists are shown tabularly and graphically below the code where the size of the list varies from 10,000 to 100,000. public void duplicate(List<String> list){ ListIterator<String> iter = list.listIterator(); while (iter.hasNext()){ String s = iter.next(); iter.add(s); } }
    size (103) link array
    10 0.008 0.053
    20 0.002 0.176
    30 0.005 0.388
    40 0.009 0.686
    50 0.009 1.069
    60 0.014 1.574
    70 0.015 2.120
    80 0.049 2.729
    90 0.019 3.443
    100 0.023 4.234
    graph

    1. Using big-Oh, the ArrayList code is O(N2) and the LinkedList code is O(N). Why are those complexities correct despite numbers like the timing for 80 above that is 0.49?
      
      
      
      
      

    2. Using the same code on the same computer how much time will it take to duplicate both an ArrayList and a LinkedList list with 1,000,000 (one million) values. Justify your answers (your answer will be considered approximate, we're looking for close enough.)
      
      
      
      
      
      

    3. Although we haven't discussed ListIterator in class, explain the differences in the observed times of duplicating an ArrayList and a LinkedList based on your understanding of how these classes are implemented.
      
      
      
      
      

    4. The following suggestion is offered as an alternative to the duplicate code above. This code correctly modifies list so that it is doubled-in-place. public void duplicate2(List<String> list){ int originalSize = list.size(); list.addAll(list); for(int k=originalSize-1; k >= 0; k--){ String current = list.get(k); list.set(2*k, current); list.set(2*k+1,current); } } Explain why the for loop runs down to zero rather than up from zero (which would not work). Provide a justification for why this code runs very quickly for ArrayList parameters and very slowly for LinkedList parameters.
      
      
      
      
      
  4. For each of the methods below indicate the running time of the method, in terms of n, using O-notation. You must justify your answers for credit. In all examples assume n is positive.
    1. public int calc(int n){ int sum = 0; for(int k=0; k < n; k++){ sum++; } for(int k=0; k < n; k++){ sum++; } return sum; }

    2. public int clunk(int n){ int sum = 0; for(int j=0; j < n; j++){ for(int k=0; k < j; k++){ sum++; } } return sum; }
    3. public int goduke(int n){ int sum = 0; for(int k=1; k <= n; k = k * 2){ sum++; } return sum; }
    4. public int stuff(int n){ int p = 0; while (p*p < n){ p++; } return p; }

Blobs and Floods

In class we discussed Blob Counting code and the flood-fill algorithm for visiting all adjacent/connected nodes in a grid.

In the coming week you'll do these APTs: RatRoute, NumberFill, and FloodRelief which all use variations on the flood-fill code from the Blob program.

Our APTs usually provide input parameters as an array of Strings, but your code will be easier to write if you have a two-dimensional array of characters (or ints or booleans). Here's code that translates the RatRoute parameter into a grid; questions follow the code.

public class RatRoute { private char[][] myGrid; private int myRows, myCols ; private int myCheeseRow, myCheeseCol; public int numRoutes(String[] enc){ myRows = enc.length; myCols = enc[0].length(); myGrid = new char[myRows][myCols]; int ratRow=0,ratCol=0; for(int r=0; r < myRows; r++){ Arrays.fill(myGrid[r], '.'); for(int c=0; c < myCols; c++){ char ch = enc[r].charAt(c); if (ch == 'R'){ ratRow = r; ratCol = c; } else if (ch == 'C'){ myCheeseRow = r; myCheeseCol = c; myGrid[r][c] = 'C'; } else if (ch == 'X'){ myGrid[r][c] = 'X'; } } } // find current distance and count # routes int currentDistance = cheeseDistance(ratRow,ratCol); return routeCount(ratRow,ratCol, currentDistance+1); }
  1. What's the purpose of the line Arrays.fill(myGrid[r], '.') and how could you use another else if in the chain of code assigning values to myGrid in place of it?
    
    
    
    
    
  2. Our convention at Duke (and used in other places as well) is that instance variables begin with the prefix my. What are the names and purposes (best guess) of the five instance variables in the program?
    
    
    
    
    
    
    
  3. The variables ratRow and ratCol are not instance variables. What does this mean about accessing these values in other methods that you'll write in solving this problem?
    
    
    
    
    
  4. Write a method whose prototype/header is given below that returns the distance from a grid point to the location of the cheese using the Manhattan distance (aka taxicab geometry) formula in which distances are measured along rectilinear grid points. The distance between points (a,b) and (c,d) in this distance is |a-c| + |b-d| where absolute value is used to ensure distances are non-negative. Use Math.abs(..) to compute absolute value, use instance variables as appropriate.

      /**
       * Returns the distance (Manhattan) from (row,col) to location of cheese
       * in the grid.
       * @param row is row coordinate
       * @param col is col coordinate
       * @return the distance from (row,col) to location of cheese
       */
      private int cheeseDistance(int row, int col) {
    
    
    
    
    
      }
    
  5. One way to develop the code to solve the APT is to write the helper method whose prototype/header follows below -- this method is called in the numRoutes code above: /** * Returns the number of ways of getting from (row,col) to cheese * @param lastDistance is the distance to the cheese from the location visited * just prior to getting to (row,col), e.g., the last cheese-distance of * the rat before moving to (row,col) */ private int routeCount(int row, int col, int lastDistance){ if (row < 0 || col < 0 || row >= myRows || col >= myCols) return 0; if (myGrid[row][col] == 'C') return 1; if (myGrid[row][col] == 'X') return 0; // more code here
    1. What is the purpose of the first if statement, returning zero?
      
      
      
      
      
    2. What is the purpose of the second if statement, returning one?
      
      
      
      
    3. What is the purpose of the third if statement, returning zero?
      
      
      
      
      
    4. After the code has taken care of several base-cases above one more base case must be considered: the case that the rat has moved to (row,col) and away from the cheese. Before moving to (row,col) the distance from the cheese is in the parameter lastDistance. Take care of the base case when the rat has moved farther from the cheese and thus there are no routes to the cheese by writing code here:
      
      
      
      
      
      
      
      
    5. There are four recursive calls needed to complete the method, be sure to accumulate the result returned by each call. Do this when you complete the APT.