Burt Rosenberg

Problem Set 3 _{Due: 29 September, 1994}^{Out: 22 September, 1994}

Goals

Learn predicate logic and its applications to program design.

Reading Assignment

Read in Program Derivation sections 2.1, 2.2, in section 2.3 subsections 2.3.1 through 2.3.3, pages 32–45, and in section 2.4 subsections 2.4.1 through 2.4.7, pages 54–69.

Written Homework

1. Exercise 2.1, pages 82–83.

2. Exercise 2.2, pages 83–84.

3. Prove the following statement:

Theorem 1 Suppose F and G are two tautologically equivalent logical statements, and S and T are two Pascal statements or statement blocks. Then the following two if-then-else statements are equivalent:

                            if F then S else T
                            if G then S else T

4. Exercise 2.5, pages 86–87.

An Experiment

How fast is your unique words program? Its run time depends on the size of the input. In your INBOX are several files, of several sizes. Try your program on them and graph the results, size versus run time, connecting the trial points with lines. How can you make the program faster?