Exam Review

Some of the following questions will appear on the final exam in some form.

1. Given a number x write a method that returns true if x is prime and false if x is not prime.
   
2. Card swapping problem: 25 people in a circle, a deck of 50 cards with numbers 1,1,2,2,...,25,25 on them. Each person gets 2 randomly selected cards. At each step, each person looks at their two cards and passes a smallest card left.
   Prove that eventually some person will be holding two cards with the same number on them.
   
3. Write function compress(s) which returns the run length encoding of alphabetic String s. Example: compress("")="", compress("a")="1a", compress("aaaa")="4a", compress("aaaabbca")="4a2b1c1a"
   
4. Locker Room problem
   A locker room has lockers numbered 0,1,2,...,1023. All lockers are initially closed.

   The first person walks in and flips every locker
   The 2nd person flips every other locker (starting at 0)
   The 3rd person flips every third locker (starting at 0)
   .
   .
   .
   The 1023 person flips every 1023 locker (starting at 0)

   At the end, which lockers are open and which are closed?

5. Write recursive method isBuyable described below and determine
   buyability of 0,1,2,...,100
   
   isBuyable(integer n)
   Background: At McDonalds, you can only purchase 6,9 and 20 packs of Mc Nuggets. Call an amount of Mc Nuggets buyable if it is possible to purchase some number of 6,9 and 20 packs and total the target amount.
   
   For example 0, 6, 15, 18 are all buyable. 10 and 11 are not buyable.
   Input: n an integer
   Output: returns true if n is a buyable amount, false otherwise
   Example:
   
   isBuyable(0) returns true
   isBuyable(6) returns true
   isBuyable(15) returns true
   isBuyable(18) returns true
   isBuyable(10) returns false
   isBuyable(11) returns false
   
   Algorithm: Implement the following recursive algorithm
   if n < 0 then n is not buyable
   if n=0 then n is buyable
   if one of n-6, n-9 or n-20 is buyable then so is n
   
   Bonus: Is there a largest number of Mc Nuggets which is not buyable?
   If so, what is that number. Prove it.

6. Write a program that given an amount of money and a price finds the amount of change to be given back to the customer. The program should print the total amount of change as well as the least possible number of coins or bills. For example if the total change should be $4.57 the program would print:
   2 Toonies
   2 Quarters
   1 Nickel
   2 Pennies

©2003 C. Whittington