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