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/