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/