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)