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 your answers neatly.

Problem 1

1. (5 pts) Write a function ReverseArray(A[] : integer array, n : integer) that reverses an integer array A of size n. This function should change A, not create a new array. The main job is to write a recursive helper function Reverse(A[] : integer array, i : integer, j : integer) to be called by ReverseArray with the appropriate arguments. Reverse reverses all elements between indices i and j. It should use the following strategy:

   • If the part of A we're concerned with has more than one element, it must have a first element and a last element. Swap the values at these two locations, then reverse the remaining elements recursively.

   Keep in mind:

   • A is indexed 0 through n - 1.
   • Your function needs to have a base case.

2. (5 pts) If A has n elements (0 through n - 1), how many times is your helper function called?

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 maximum value in an array of n integers:

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

		if n = 1 then return A[0]
		else {
			x := MaxValue(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 maximum value in the array A. Your proof should include the basis step and the inductive step.