Summer 2018

Algorithms and Analysis Tools Exam, Part A

Page

3

of

4

2)

(5 pts) ANL (Algorithm Analysis)

An algorithm to process an array of size n takes O(

√

) time. For

n

= 640,000, the algorithm runs in

256 milliseconds. How many

seconds

should the algorithm take to run for an input size of

n

=

1,000,000?

Let the algorithm with input array size n have runtime

() = √

, where c is some constant.

Using the given information, we have:

(640000) = (640000)√640000

= 256

(640000)(800) = 256

(512 × 10

6

) = 256

=

256

512 × 10

6

=

1

2 × 10

6

Now, solve for the desired information:

(1000000) = (1000000)√1000000

=

1

2 × 10

6

× 10

6

× 10

3

=

10

3



2

=

1

2

=

1

2



Summer 2018

Algorithms and Analysis Tools Exam, Part A

Page

4

of

4

3)

(10 pts) ANL (Summations)

Recall that

∑

2



=2



−1

−1

=0

.

(a) (8 pts) Using this result, determine a closed-form solution in terms of

n

, for the summation below.

(b) (2 pts) Determine the numeric value of the summation for n = 9.

∑(∑ 2



−1

=0

)



=0

(a)

∑(∑ 2



−1

=0

)



=0

= ∑(2



− 1)



=0

=∑2





=0

−∑1



=0

=2

+1

− 1 − ( + 1)

=2

+1

−−2

(b) Plugging in n = 9 into the closed-form solution obtained in part (a), we get:

2

9+1

− 9 − 2 = 1024 − 11 = 

Grading: Part A -2 pts for inner sum, 2 pts split sum, 1 pt left sum, 2 pts right sum, 1 pt

simplifying difference, Part B - 2 pts correct answer, 1 pt plug in correct but made an arithmetic

error, 0 otherwise

Page

1

of

4

Computer Science Foundation Exam

May 19, 2018

Section II B

ALGORITHMS AND ANALYSIS TOOLS

SOLUTION

NO books, notes, or calculators may be used,

and you must work entirely on your own.

Question #

Max Pts

Category

Score

1

10

DSN

2

10

DSN

3

5

ALG

TOTAL

25

You must do all 3 problems in this section of the exam.

Problems will be graded based on the completeness of the solution steps and not

graded based on the answer alone.

Credit cannot be given unless all work is shown

and is readable. Be complete, yet concise, and above all be neat. For each coding

question, assume that all of the necessary includes (stdlib, stdio, math, string) for

that particular question have been made.

Summer 2018

Algorithms and Analysis Tools Exam, Part B

Page

2

of

4

1)

(10 pts) DSN (Recursive Coding)

Consider writing a recursive method that raises a polynomial to an exponent, calculating each of its coefficients

mod a given integer. One way this method could work is checking to see if the exponent is even. If so, raise the

polynomial to half of the original power. Then, take that result (a polynomial) and multiply it by itself for the

result. If the original exponent,

exp

, was odd, then we could simply first raise the polynomial to

exp

-1, and then

take that result and multiply it by the original polynomial. Implement this algorithm recursively below. You are

given the code for the multiply function and should call it accordingly. A polynomial is stored as an array of

integers, where poly[i] is the coefficient to x

i

. In the function signature, len is the length of the array poly, so poly

is of degree len-1, exp is the exponent to which we are raising the polynomial and mod is the modulus by which

we are calculating each coefficient.

int* power(int* poly, int len, int exp, int mod) {

if (exp == 0) {

int* res = malloc(sizeof(int));

res[0] = 1;

return res;

}

if (exp == 1) {

int* res = malloc(len*sizeof(int));

int i;

for (i=0; i<len; i++) res[i] = poly[i]%mod;

return res;

}

if (exp%2 == 0) {

int* tmp = power(poly,

len

,

exp/2

, mod);

int* prod = multiply(

tmp

,

(len-1)*exp/2+1

,

tmp

,

(len-1)*exp/2+1

, mod)

free(tmp);

return prod;

}

int* tmp = power(poly,

len

,

exp-1

, mod);

int* prod = multiply(

tmp

,

(len-1)*(exp-1)+1

,

poly, len, mod);

free(tmp);

return prod;

}

int* multiply(int* poly1, int len1, int* poly2, int len2, int mod) {

int* res = calloc(len1+len2-1, sizeof(int));

int i, j;

for (i=0; i<len1; i++)

for (j=0; j<len2; j++)

res[i+j] = (res[i+j] + poly1[i]*poly2[j])%mod;

return res;

}

Grading: 1 pt per slot, all or nothing per slot.