CSC152 2004F, Class 41: Discussion of Exam 2

Admin:
* Exams returned
* What to take next semester:
  * CSC201
    * Serves as a prerequisite to 211 (Arch), 213 (OS)
    * Teaches you a third cool programming language (C)
    * Gives you more formal strategies for evaluating your programs' correctness
  * Can we take computer networks?
    * You'll need to talk to Silkin
  * Can we take two CS classes?
    * If your advisor allows it
* Hashtable homework due Monday.
* Tuesday's homework in last Tuesday's eboard.
* Code question left on the whiteboard?

Overview:
* Problem 1: Documenting Binary Search
* Problem 2: Fixing Hash Tables
* Problems 3 and 4: Making Change

/Documenting Binary Search/

* Documentation always needs a one or two sentence description of *what* the procedure does.
  * The description probably doesn't give a *how*.
  * The description might include a note as to running time.
* GOAL of preconditions:
  * Specify the correct form of the input
  * The code need not work on incorrect input
  * Preconditions must be specified carefully; anything that meets the preconditions should work
* GOAL of postconditions
  * So that the client knows exactly what it's getting
  * So that the client can ensure that future preconditions are met

/Checking Preconditions in Binary Search/

* Programming War!  Do you check preconditions?
* Yes: Good to be careful
* No: Slows down the program for people who check in advance

* Should we run isInIncreasingOrder as part of binarySearch?
  * binarySearch is O(logn)
  * isInIncreasingOrder is O(n)

/Fixing Kevin's Cool Queues/

* Basic idea: When you reach the end of the array, wrap around to the beginning (assuming there is space at the beginning)
* Problem: What do we do when the queue fills?
  * Part one: Determine when the queue fills.
  * Part two: Build a new array and copy elements.
  * Part three: Decide how to copy elements.
  * Part four: Determine the new first and last.

* When is the queue full?
  * Based on this.first, this.last, and this.contents.length
  * Old way: this.last == this.contents.length
    * But under Kevin's model, it's not full if cell 0 is empty
  * New way: this.last == this.first and the queue is not empty

Coin Counting Grows Really Fast
Suppose coins were 1 and 2: Recursive call structure looks like Fibonacci.  Sam claimed Fibonacci is exponential

Improving Coin Counting: Dynamic Programming
* General philosophy: create an array, store values in the array, check the array

* Details:
  * Add an array field
  * Add code to make sure the array is big enough
  * Add code to check the array before doing the computation
  * Add code to fill in the array after the computation (if the computation is necessary)