From Algorithms to Methods

The real science of Computer Science is writing algorithms and, for beginners, writing algorithms is much easier in pseudocode than it is in Java. Unfortunately, there are no standard programs to convert pseudocode into codes the computer can understand, so Java exists as a middle ground between a Computer Scientist's ideal (pseudocode) and the requirements of the computer (binary code). However, as you learn to program, we encourage you to write your algorithm is pseudocode first, then convert them to Java.

As an example, consider the following descriptions of Euclid's algorithm for finding the greatest common divisor (gcd) of two numbers. The gcd of 12 and 42 is 6 and gcd of 14 and 74 is 2.

START:
  Assign r the reminder of x divided by y
  If r equals 0 stop, gcd value is y
  Else
    Assign x the value of y
    Assign y the value of r
    goto START

Using Windows Calculator in Scientific mode to find the gcd of two numbers.
      
  1. The two numbers are small and big, where big is larger than small.
  2. Enter big, press the mod key, enter small, press the = key.
  3. If display shows zero, the gcd is small, stop.
  4. Replace big with small, and small with the number showing in the display. Go back to step 2.

Algorithms

For each of the following problems, start by writing an algorithm or sequence of steps that are specific enough for someone else to understand and use to solve the problem described.

Once you feel confident that your instructions solve the problem, you can begin to convert it into Java code. In some cases, this will be very straight forward, sometimes you will need to look up how to express a specific concept or see if there already is a standard way to do it in Java. Sometimes you will have to write some extra code to make your main task easier. We will explore all of these issues in the coming weeks.

For each of the folllowing problems, complete the code started for you using any standard text editor, then run and test them using the APT testing page within your browser.

1. OneHeapNim
2. Laundry
3. Pancakes
4. TippingWaiters
   Here are some notes on this problem:
   1. The wording is a bit tricky. Note that the tip is between 5% and 10% of the final sum.
      For example: suppose the bill is 17100 and the cash is 18000.
      The minimum amount you could pay (not rounded up to a five yet) is NOT 17100 + 17100* 0.5 = 17955.
      Instead, the minimum amount you could pay (not rounded up to a five yet) is 17100/0.95 = 18000.
      Note that 5% of 18000 is 900. 17100 +900 = 18000.
      In Java, you can write this as int minpay = (int)Math.ceil(bill/0.95);
      
   2. Compute the minimum you can pay rounded up by 5. Compute the maximum you can pay rounded up by 5. You do not need a loop to figure out how many payments in increments of 5 can be paid. Instead, use a formula.

Submitting Your Work

When you are satisfied you have completed the problems above, you should electronically submit your project through Eclipse. A submission is not considered complete unless it includes all the Java code for the project (both what you have written and the code provided when you downloaded the project) and a README file as described here.