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