CSC152 2005F, Class 43: Discussion of Exam 2
Admin:
* Tomorrow: Wrapup of linear structures (a better implementation of
priority queues)
* Tomorrow: Present your results from Monday.
* About DC.
Overview:
* Problem 1
* Problem 2
* Problem 3
* Problem 4
Problem 1: Expandable Arrays
Integer[] contents;
int size;
public void set(int index, Integer val)
throws Exception
{
if (index < 0) {
throw new Exception("Arrays only accept positive indices");
}
if (this.contents.length <= index) {
this.expand(index+1);
}
this.contents[index] = val;
if (this.size < index) {
this.size = index;
}
}
/**
* Expand the underlying array to size at least newsize.
*/
void expand(int newsize)
{
// Create the new array
Integer newcontents = new Integer[newsize];
// Copy over the values
for (int i = 0; i < this.contents.length; i++)
{
newcontents[i] = this.contents[i];
} // for
// Update the field
this.contents = newcontents;
}
Sam's concern: How long does the following code take?
ArbitrarilyLargeIntegerArray a = new ArbitrarilyLargeIntegerArray();
for (int i = 0; i < n; i++)
{
a.set(i, new Integer(i*i));
} // for
* How long (in big O) would you hope this would take?
O(n)
* How long does it take given the definition of expand above?
1 + 2 + 3 + 4 + 5 + 6 + ... + n-2 + n-1 + n is in O(n^2)
* Can we make set a little bit more efficient? (Perhaps by
changing expand)
* Expand will provide some extra space
* Space/time tradeoff
* Strategy: Keep doubling the size of the underlying array until it's big enough
* Doesn't waste too much space (nor more than twice as much space as we need)
* Should lead to more efficient code
1 + 2 + 4 + 8 + 16 + 32 + ... + n is approximately 2N in O(N)
Examples:
N = 1; 1 = 1
N = 2; 1 + 2 = 3
N = 4: 1 + 2 + 4 = 7
N = 8: 1 + ... + 8 = 15
N = 16: 1 + ... + 16 = 31
The pattern: the sum is 2*N-1
* How general should your code be?
* Strategy one: Programmers are clueless
* Pick whichever you think is best
* But programmers are smart
* Strategy two: Alternate implementations
* But duplicated code
* Strategy three: Give two different calls to set
* But then someone has to go back and change all the calls
to switch expansition protocols
* Strategy four: Use doubling, but add setSize for those who
want a smaller expansion
* Strategy five: Let the programmer specify the expansion
protocol when creating the structure.
Counting coins:
* ln(steps) grows linearly with n
* Hence steps grows exponentially with n
* Strategy: Dynamic programming (caching of intermediate results)
* Problem: Need to remember to store the values
* Problem: Need to remember to store FAILURE too