CSE 373 Homework Assignment 1

All functions should be written in pseudocode. See the pseudocode manual for the recommended syntax and other tips. Please try to stick to this format, and print or type your answers neatly.

Problem 1

1. (5 pts) Write an iterative function CountI(A[] : integer array, n : integer) that is given an integer array A of size n and returns a count of the number of positions in the array in which A[i] is equal to i, which will be zero if there are no such positions.

2. (5 pts) Write a recursive function CountR(A[] : integer array, n : integer) that does the same thing, recursively. Identify your base case and recursive case in comments.

Both of these had better have one or more return statements to return the required counts.

Problem 2

(10 pts) Write an iterative (nonrecursive) function Add(P : poly pointer, Q : poly pointer) : poly pointer that performs polynomial addition without changing the two input polynomials. You may use the following "built-in" functions:

• CopyCell(P) creates and returns a pointer to a new cell, identical to the one pointed to by P.

• CopyPoly(P) creates and returns a pointer to a whole new polynomial identical to the one pointed to by P. This will be helpful when exactly one of the polynomials has no more terms.

Problem 3

(10 pts) Consider the following function, which computes the minimum value in an array of n integers:

	MinValue(A : integer array, n : integer) : integer {
		x : integer

		if n = 1 then return A[0]
		else {
			x := MinValue(A, n - 1)

			if x < A[n - 1] then return x
			else return A[n - 1]
		}
	}

Use induction to prove that this function is correct when called with n > 0. That is, prove that it really does return the minimum value in the array A. Your proof should include the basis step and the inductive step.