Showing 11-14 out of 16

FE-May18-Sol.pdf-Page 1 of 4 Computer Science

FE-May18-Sol.pdf-Page 1 of 4 Computer Science

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

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.

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

Ace your assessments! Get Better Grades

Browse thousands of Study Materials & Solutions from your Favorite Schools

University of Pune

University_of_Pune

School:

Computer_Science_I

Course:

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

#### Students also viewed documents

lab 18.docx

lab_18.docx

Course

Course

3

Module5QuizSTA2023.d...

Module5QuizSTA2023.docx.docx

Course

Course

10

Week 7 Test Math302....

Week_7_Test_Math302.docx.docx

Course

Course

30

Chapter 1 Assigment ...

Chapter_1_Assigment_Questions.docx.docx

Course

Course

5

Week 4 tests.docx.do...

Week_4_tests.docx.docx

Course

Course

23

Week 6 tests.docx.do...

Week_6_tests.docx.docx

Course

Course

106