SUNY Geneseo Department of Computer Science

Problem Set 1 -- Pre- and Postconditions

CSci 240, Spring 2007

Prof. Doug Baldwin

Due Monday, January 22

Purpose

The purpose of this exercise is to increase your comfort thinking about and designing with preconditions and postconditions.

Background

Preconditions and postconditions are defined in Section 2.2 of our text; their application to algorithm design is demonstrated in Section 2.3. These ideas are also discussed in the January 19 lecture.

Exercise

Solve each of the following problems.

Problem 1

Recipes are a favorite non-programming example of algorithms. Here is a simple recipe/algorithm for making a hot (or at least warm) fudge sundae:

Ingredients: ice cream, 1 jar prepared fudge sauce
Open jar of fudge sauce and place in pan of water over low heat; heat until water is not quite boiling
Place 1 to 3 scoops of ice cream in a bowl
Remove fudge sauce from water, pour over ice cream

What are the preconditions for carrying out this algorithm? What are the postconditions?

Problem 2

Text exercise 2.10

Problem 3

Suppose you are given an array, A, containing n numbers. The array's indices range from 0 to n-1. You are supposed to find the largest number in the array. This problem can be more precisely defined by saying that you are to establish the postcondition that "i is an integer such that 0 ≤ i ≤ n-1 and for all integers j such that 0 ≤ j ≤ n-1, A[i] ≥ A[j]."

What, if anything, are the preconditions for establishing this postcondition?

What, if anything, does the postcondition suggest about the design of an algorithm to solve the problem?

Follow-Up

I will grade this exercise in a face-to-face meeting with you. Make an appointment to meet with me at some time convenient for you, as long as that time is before the end of the due date above. Meetings only need to be 15 minutes long. You can make an appointment by signing up on the copy of my schedule on the bulletin board outside my office. Please bring written answers to each of the problems to the meeting.