COSC 071: Computer Science I

Homework 1
Spring 2007

Due in class, Thursday., Jan 25
2 points

This homework is designed to get you thinking about algorithms.

1. Hoya Pizza sells a 9" square pizza with one topping for $9.99, and Saxa Pizza sells an 10" round pizza with one topping for $8.99. Which is the better buy?

2. An algorithm is just a step-by-step procedure for accomplishing a task. The steps you took above constitutes an algorithm, albeit a very specific algorithm. A limitation is that it only works for 9" square pizzas that cost $9.99 and for 10" round pizzas that cost $8.99. Instead of using the actual numbers provided, rewrite your previous "algorithm" using variables or symbols that represent the numbers. For example, instead of writing 9.99, write roundPizzaCost, and instead of writing 10, write roundPizzaSize.

   For example, if we had a triangle pizza, we might write something like:

   • trianglePizzaCost = 7.99
   • trianglePizzaBase = 6
   • trianglePizzaHeight = 9
   • trianglePizzaArea = 0.5 x trianglePizzaBase x trianglePizzaHeight
   • trianglePriceSqIn = trianglePizzaCost / trianglePizzaArea

   The advantage of doing this is that we've separated the procedure for calculating the price per square inch of a pizza from any set of specific numbers. To compute a new price per square inch, we simply reassign the variables that correspond to the cost and the size of the pizza, and apply the algorithm.

3. Assume that you are restricted to four instructions: INPUT, CALCULATE, OUTPUT, and decisions of the form IF <condition> THEN <instruction(s)>. Express your algorithm for deciding which pizza is the better buy in terms of these actions.

   For our triangle pizza example, we might write something like:

   • INPUT trianglePizzaCost
   • INPUT trianglePizzaBase
   • INPUT trianglePizzaHeight
   • CALCULATE trianglePizzaArea = 0.5 x trianglePizzaBase x trianglePizzaHeight
   • CALCULATE trianglePriceSqIn = trianglePizzaCost / trianglePizzaArea
   • OUTPUT trianglePriceSqIn

4. Draw a flowchart for Question 3's solution.

5. On page 42, the authors present Euclid's algorithm for computing the greatest common divisor (GCD) of two integers. Use the algorithm to calculate the GCD of m = 17 and n = 3.

6. Draw a flowchart for Euclid's algorithm.