- Home
- Uncategorized
- CPSC 331 — Assignment #1 Proving the Correctness of Simple Algorithms — and Implementing Them as Java Programs

$30.00

Category: Uncategorized

Description

5/5 - (2 votes)

The Problem To Be Solved: The Grindelwald Gaggle

At the Hogwarts School of Witchcraft and Wizardry, significant time is spent studying the mystical properties of various sequence of integers. These include the Grindelwald Gaggle — a

1

sequence of numbers G0, G1, G2, G3, . . . defined as follows: For every integer i ≥ 0,

Gi =

1 if i = 0,

2 if i = 1,

3 if i = 2,

4 if i = 3,

2Gi−1 − 2Gi−3 + Gi−4 if i ≥ 4 and i is even,

Gi−1 + 3Gi−2 − 5Gi−3 + 2Gi−4 if i ≥ 4 and i is odd.

Consequently, Hermione Granger is interested in the following computational problem:

Grindelwald Gaggle Computation

Precondition: A non-negative integer n is given as input.

Postcondition: The n

th Grindelwald number, Gn, is returned as output.

A Simple — But Slow — Algorithm for This Computation

Hermione has written a Java program that implements the algorithm shown in Figure 1 on

page 3.

1. Give a reasonably short proof that the function f(n) = n is a bound function for this

recursive algorithm.

2. Prove that the sGrin algorithm correctly solves the “Grindelwald Gaggle Computation”

problem.

3. Write a Java program, SGrindelwald.java, that satisfies the following properties:

• It is part of the cpsc331.assignment1 package.

• Integer inputs and outputs are represented using Java’s int data type.

• It includes a method, sGrin, which receives an integer n as input and which computes the n

th Grindelwald number if n ≥ 0, using the algorithm which has now been

analyzed, but which actually solves a more general computational problem than the

one given above:

Extended Grindelwald Gaggle Computation

Precondition: An integer n is given as input.

Postcondition: If n ≥ 0 then the n

th Grindelwald number, Gn, is returned as output. An IllegalArgumentException is thrown otherwise.

2

integer sGrin (integer n) {

// Assertion: A non-negative integer n has been given as input.

1. if (n == 0) {

2. return 1

3. } else if (n == 1) {

4. return 2

5. } else if (n == 2) {

6. return 3

7. } else if (n == 3) {

8. return 4

9. } else if ((n mod 2) == 0) {

10. return 2 × sGrin(n − 1) − 2 × sGrin(n − 3) + sGrin(n − 4)

} else {

11. return sGrin(n − 1) + 3 × sGrin(n − 2) − 5 × sGrin(n − 3)

+2 × sGrin(n − 4)

}

}

Figure 1: A Slow Algorithm for the “Grindelwald Gaggle Computation” Problem

The method should not be public but should be accessible by other classes in the

cpsc331.assignment1 package.

• The main method should read its input from the command line. If either the number

of inputs is incorrect, or the input is not an integer, then it should return the message

Gadzooks! One integer input is required.

If there is a single integer input, but it is negative, then the main method should

return the message

Gadzooks! The integer input cannot be negative.

Otherwise —- when given a non-negative integer input n – it should report the

corresponding Grindelwald number Gn.

A few sample runs of the program should therefore look like the following.

> java cpsc331.assignment1.SGrindelwald 0

> 1

3

> java cpsc331.assignment1.SGrindelwald 1

> 2

> java cpsc331.assignment1.SGrindelwald 2

> 3

> java cpsc331.assignment1.SGrindelwald 3

> 4

> java cpsc331.assignment1.SGrindelwald 4

> 5

> java cpsc331.assignment1.SGrindelwald -1

> Gadzooks! The input integer cannot be negative.

> java cpsc331.assignment1.SGrindelwald

> Gadzooks! One integer input is required.

> java cpsc331.assignment1.SGrindelwald xyz

> Gadzooks! One integer input is required.

The following files are available and can be used before you submit your program for

assessment:

• test sGrin.java: A program that can be executed using JUnit to perform unit

tests of the method sGrin. See Java Development Exercise #5 for information

about how to use this.

• test SGrindelwald.sh: A Unix shell script that can be used to perform testing

of the main method. See Java Development Exercise #6 for information about how

to use this.

4. Let TsGrin(n) be the number of steps included in the execution of the algorithm, sGrin,

shown in Figure 1 on input n, for a non-negative integer n — assuming that the uniform

cost criterion is used to define this and the only steps counted are the numbered steps

shown in Figure 1.

Give a recurrence for TsGrin(n).

Note: If your answer is correct then you should be able to use your recurrence to show

that TsGrin(0) = 2, TsGrin(1) = 3, TsGrin(2) = 4, TsGrin(3) = 5, TsGrin(4) = 16, and

TsGrin(5) = 30.

5. Use your recurrence to prove that TsGrin(n) ≥

3

2

n

for every non-negative integer n.

Thus the number of steps executed by the sGrin algorithm is at least exponential in its

input.

An Asymptotically Faster Algorithm for This Computation

After a discovery of what is considered when solving the above problem, Ms. Granger realized

that this algorithm is far too slow to be used on Muggles computers to compute the n

th Grindelwald number, Gn, when n is very large. Indeed, one should not even try to use it to compute

G1000.

Happily, Hermione was familiar with one of the Muggles arts that you will learn about in

CPSC 413 — Dynamic Programming.

1 Another algorithm for the “Grindelwald Gaggle Computation” problem, making use of this technique, is shown in Figure 2 on page 6. This algorithm

is not recursive; instead, it creates and accesses an array.

6. State a loop invariant for the while loop at lines 15–19 of this algorithm.

For full marks (or even very many part marks) your answer should have the following

properties:

• It is correct. That is it really is a loop invariant for this while loop.

• It is complete enough to be used to establish the partial correctness of this algorithm.

• It is not necessary to make any guesses about the value of Gn, for n ≥ 4, in order

to see that this is the case.

7. Prove that your answer for the previous question really is a loop invariant for the while

loop in this algorithm.

8. Use this to prove that this algorithm is partially correct.

9. State a bound function for the while loop in this algorithm and prove that your answer

is correct.

10. Prove that if this algorithm is executed when the precondition for the “Grindelwald Gaggle

Computation” problem is satisfied, and the while loop is reached and executed, then

the execution of the loop eventually ends.

11. Using what has been proved so far, complete a proof that the fGrin algorithm correctly

solves the “Grindelwald Gaggle Computation” problem.

12. Let TfGrin(n) be the number of steps executed by the algorithm fGrin when executed

on input n, for a natural number n — as defined using the Uniform Cost Criterion (and

1Ms. Granger wonders why Muggles insist on giving such confusing names to simple ideas — like storing a

solution for an instance of a problem and reusing this solution, instead of solving the same instance of the problem

over and over again, as if you hadn’t already solved it before!

5

integer fGrin (integer n) {

// Assertion: A non-negative integer n has been given as input.

1. if (n == 0) {

2. return 1

3. } else if (n == 1) {

4. return 2

5. } else if (n == 2) {

6. return 3

7. } else if (n == 3) {

8. return 4

} else {

9. int[] G := new int[n + 1]

10. G[0] := 1

11. G[1] := 2

12. G[2] := 3

13. G[3] := 4

14. int i := 4

15. while (i ≤ n) {

16. if (i mod 2 == 0) {

17. G[i] := 2 × G[i − 1] − 2 × G[i − 3] + G[i − 4]

} else {

18. G[i] := G[i − 1] + 3 × G[i − 2] − 5 × G[i − 3] + 2 × G[i − 4]

}

19. i := i + 1

}

20. return G[n]

}

}

Figure 2: Another Algorithm for the “Grindelwald Gaggle Computation” Problem

counting only the numbered steps shown in Figure 2) — so that, for example, TfGrin(0) =

2, because the steps at lines 1 and 2 are carried out when this algorithm is executed on

input 0.

Using techniques introduce in this course, give an upper bound for TfGrin(n), as a func6

tion of n, that is as precise as you can. Your final answer should be “in closed form”, so

that it does not include any summations or recurrences.

13. Write a Java program, FGrindelwald.java, that satisfies the following properties:

• It is part of the cpsc331.assignment1 package.

• Integer inputs and outputs are represented using Java’s int data type.

• It includes a method, fGrin, which receives an integer n as input and which computes the n

th Grindelwald number if n ≥ 0, using the algorithm which has now been

analyzed, but which solves the more general “Extended Grindelwald Gaggle Computation” problem that has also been defined. The method should not be public but

should be accessible by other classes in the cpsc331.assignment1 package.

• The main method should read its input from the command line. If either the number

of inputs is incorrect, or the input is not an integer, then it should return the message

Gadzooks! One integer input is required.

If there is a single integer input, but it is negative, then the main method should

return the message

Gadzooks! The integer input cannot be negative.

Otherwise —- when given a non-negative integer input n – it should report the

corresponding Grindelwald number Gn.

A few sample runs of the program should therefore look like the following.

> java cpsc331.assignment1.FGrindelwald 0

> 1

> java cpsc331.assignment1.FGrindelwald 1

> 2

> java cpsc331.assignment1.FGrindelwald 2

> 3

> java cpsc331.assignment1.FGrindelwald 3

> 4

> java cpsc331.assignment1.FGrindelwald 4

> 5

> java cpsc331.assignment1.FGrindelwald -1

> Gadzooks! The input integer cannot be negative.

7

> java cpsc331.assignment1.FGrindelwald

> Gadzooks! One integer input is required.

> java cpsc331.assignment1.FGrindelwald xyz

> Gadzooks! One integer input is required.

The following files are available and can be used before you submit your program for

assessment:

• test fGrin.java: A program that can be executed using JUnit to perform unit

tests of the method sGrin.

• test FGrindelwald.sh: A Unix shell script that can be used to perform testing

of the main method.

Finding a Closed Form

14. Find an expression for the n

th Grindelwald number, as a function of n, in closed form —

so that it does not include a summation or recurrence — and prove that your answer is

correct.

8