## Description

CMSC 451 Homework 1

1. Consider the following iterative function:

int pentagonal(int n)

{

int result = 0;

for (int i = 1; i <= n; i++)

result += 3 * i – 2;

return result;

}

Rewrite the function pentagonal using recursion and add preconditions and

postconditions as comments. Then prove by induction that the recursive function you

wrote is correct.

2. Suppose the number of steps required in the worst case for two algorithms are as follows:

Algorithm 1: f(n) = 10n

2 + 6

Algorithm 2: g(n) = 21n + 7

Determine at what point algorithm 2 becomes more efficient than algorithm 1.

3. Given the following function that evaluates a polynomial whose coefficients are stored in

an array:

double evaluate(double[] coefficients, double x)

{

double result = coefficients[0];

double power = 1;

for (int i = 1; i < coefficients.length; i++)

{

power = power * x;

result = result + coefficients[i] * power;

}

return result;

}

Let n be the length of the array. Determine the number of additions and multiplications

that are performed in the worst case as a function of n.

4. Given the following recursive binary search algorithm for finding an element in a sorted

array of integers:

int recursiveBinarySearch(int[] array, int target, int left, int right)

{

if (left > right)

return -1;

int middle = (left + right) / 2;

if (array[middle] == target)

return middle;

if (array[middle] > target)

return recursiveBinarySearch(array, target, left, middle – 1);

return recursiveBinarySearch(array, target, middle + 1, right);

}

Assume n is the length of the array. Find the initial condition and recurrence equation that

expresses the execution time for the worst case of this algorithm and then solve that

recurrence.

Grading Rubric

Problem Meets Does Not Meet

Problem 1

10 points 0 points

Recursive version correctly written (3) Recursive version not correctly written

(0)

Precondition is correct (1) Precondition is not correct (0)

Postcondition is correct (1) Postcondition is not correct (0)

Base case is correct (1) Base case is not correct (0)

Inductive case is correct (4) Inductive case is not correct (0)

Problem 2

10 points 0 points

Determined correct value for n (5) Did not determine correct value for n

(0)

Show calculation for determining n (5) Did not show calculation for

determining n (0)

Problem 3

10 points 0 points

Provided correct formulas for additions

(5)

Did not provide correct formulas for

additions (0)

Provided correct formulas for

multiplications (5)

Did not provide correct formulas for

multiplications (0)

Problem 4

10 points 0 points

Provided correct initial condition (2) Did not provide correct initial condition

(0)

Provided correct recurrence equation

(4)

Did not provide correct recurrence

equation (0)

Provided correct solution to recurrence

equation (4)

Did not provide correct solution to

recurrence equation (0)