CSC152 2005S, Class 48: About Exam 2

Admin:
* Exam 2 returned
* Changed dates for exam 3: Assigned next Friday, due Friday of 14th week (ick)

Overview:
* General Issues
* Problem 1: Implementation Issues
* Problem 2: Making Change
* Problem 3: Random Lists
* Problem 4: Heaps

/General Issues/

Things Sam hates to hear
* "I really didn't understand this problem."
  * You can brave the entropy and come talk to me.
  * You can ask questions in class.
* "I spent three hours trying to understand random numbers in Java"
  * If you spend more than fifteen minutes banging your head against the wall
    * (a) it hurts
    * (b) you are unlikely to make much more progress in a short period
    * (c) therefore you should come get help
* "I know my program has a subtle bug, but I can't find it."

Making Sam happy!
* Start early
* Ask questions *every day* in class
* Remember: Even though there are dumb questions, I don't mind if you ask them, and your classmates probably don't either.
* Visit Sam in entropyland

Trimodal Distribution
* A few at 100+
* A few at "almost 80"
* A few at "way below 80"
  * Need to talk to me

/Choosing an Implementation/

* Goal: General

/Making Change/

* Didn't understand the original "exhaustive search" algorithm
  * Problem: Minimum of coins to exactly make price (p) given denominations (d1 .. dk)
    * Suppose the optimal solution has a coin of price d1.  How many coins does it take to make the remainder?
    * Suppose the optimal solution has a coin of price d2.  How many coins does it take to make the remainder?
    * Suppose the optimal solution has a coin of price dk.  How many coins does it take to make the remainder?
  * Coding that idea:
    int fewest = price+1;
    // For each denomination
    for (int i = 0; i < denominations.length; i++) {
      // Suppose the optimal solution has a coin of price di
      // How many coins does it take for the rest?
      int tmp = this.fewestCoins(price - demominations[i]);
      int this_solution = 1+ tmp;
      // If the solution using a coin of price di is better
      // than the best solution we've seen so far, update
      // our solution.
      if (fewest > this_solution)
        fewest = this_solution;
    }

* Didn't remember how to count recursive calls
* Couldn't figure out the array stuff

/Random Lists/

* Designing the ADT
  * Much like a linear structure except the policy is specified.
/Heaps/