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
- 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;
}
- 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);
}
- Using big-Oh, what is the value returned by the call
zcal(N)
? Justify.
- Using big-Oh, what is the runtime of the call
zcal(N)
?
- Using big-Oh, what is the value returned by the call
zcal(zcal(N))
? Justify.
- Using big-Oh, what is the runtime of the call
zcal(zcal(N))
? Justify.
-
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 list){
ListIterator 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 |
|
|
- 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?
- 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.)
- 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.
- 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 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.
- 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.
-
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;
}
-
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;
}
-
public int goduke(int n){
int sum = 0;
for(int k=1; k <= n; k = k * 2){
sum++;
}
return sum;
}
-
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);
}
- 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?
- 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?
- 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?
- 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) {
}
- 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
- What is the purpose of the first
if statement
, returning zero?
- What is the purpose of the second
if statement
, returning one?
- What is the purpose of the third
if statement
, returning zero?
- 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:
- 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.