FE-May18-Sol.pdf-Page 1 of 4 Computer Sc...
FE-May18-Sol.pdf-Page 1 of 4 Computer Science
Showing 11-14 out of 16
FE-May18-Sol.pdf-Page 1 of 4 Comput...
FE-May18-Sol.pdf-Page 1 of 4 Computer Science
##### Page 11
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

Grading: 2 pts solving for c, 2 pts for plugging 10
6
and canceling to get to 1000/2 ms, 1 pt to
answer 1/2 second as the question requests.

##### Page 12
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 13
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
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.

##### Page 14
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.

Browse thousands of Study Materials & Solutions from your Favorite Schools
University of Pune
University_of_Pune
School:
Computer_Science_I
Course:
Great resource for chem class. Had all the past labs and assignments
Leland P.
Santa Clara University
Introducing Study Plan
Using AI Tools to Help you understand and remember your course concepts better and faster than any other resource.
Find the best videos to learn every concept in that course from Youtube and Tiktok without searching.
Save All Relavent Videos & Materials and access anytime and anywhere
Prepare Smart and Guarantee better grades