15-105 SPRING 2009 [CORTINA]

HOMEWORK 2 - due Friday, January 30

WRITTEN PROBLEMS (8 pts)

Hand these problems in on paper in class on the due date specified.

1. (2 pts) Assume you can only give someone a sequence of instructions from the following set of two instructions:
   • Draw a square centered at ( x , y ) with a side length of s.

   • Draw a circle centered at ( x , y ) with a radius of r.

   Give an algorithm made up of instructions of the type shown above to draw the following pictures substituting in appropriate values for x, y, s and r in each instruction.

   

2. (2 pts) A precise algorithm is typically made up of instructions that consist of a set of known primitive operations that do not need explanation. For example, in arithmetic, the primitives add, subtract, multiply and divide are easily understood. Each of these operations can combine only two values at a time (e.g. "Add 2 and 3."). You may make reference to previous results in your instructions (e.g. "Multiply the result from step 3 by 10."). Using only these arithmetic primitive operations, write an algorithm that describes how to perform the following computations:

   

   The result of your last algorithmic step should be the final answer. NOTE: In the second computation, can you figure out how to write only four instructions to generate the answer?

3. (2 pts) Trace the following algorithm when c = 12 and when c = 35. Determine the output in each case and show your work. What is the significance of the answers?

   1. Input c.
   2. Set d = 0.
   3. While c ≠ 0, do the following:
      a. If c modulo 5 = 0, add c to d.
      b. Subtract 1 from c.
   4. Output d.
   

4. (2 pts) Given a vector A with n integers in it, n > 0, complete the algorithm below that computes and outputs the sum of the odd numbers stored in vector A. You may assume the data for the vector has already been input. Remember that a vector with n values is indexed from 0 to n-1.

   1. Set sum equal to __________.
   2. Set index equal to __________.
   3. While index ____ n, do the following:
      a. If __________________________, add A[index] to sum.
      b. Add 1 to index.
   4. Output sum.
   

COMPUTER PROBLEM (2 pts)

Hand this in electronically using the Electronic Handin System by 11:59PM on the due date indicated.

Write a short Python program on your computer named computesum.py that computes the sum of the positive integers up to n, where n > 0. For example, if n is 5, then the program should output 15 since 1 + 2 + 3 + 4 + 5 = 15. Use the python interpreter to test your work carefully for correctness.

Here is the general algorithm to follow:

1. Input n
2. Set answer = 0.
3. Set i = 0.
4. While i < n, do the following:
   a. Add 1 to i.
   b. Add i to answer.
5. Output answer.

You may assume the input value will always be a positive integer.