Showing 12-15 out of 16

FE-Jan19.pdf-Page 1 of 4 Computer Science

FE-Jan19.pdf-Page 1 of 4 Computer Science

FE-Jan19.pdf-Page 1 of 4 Computer S...

FE-Jan19.pdf-Page 1 of 4 Computer Science

##### Page 12

Spring 2019

Algorithms and Analysis Tools Exam, Part A

Page

4

of

4

3)

(10 pts) ANL (Summations and Recurrence Relations)

Determine the following summation in terms of n (assume n is a positive integer 2 or greater),

expressing your answer in the form an

3

+ bn

2

+ cn, where a, b and c are rational numbers. (Hint: Try

rewriting the summation into an equivalent form that generates less algebra when solving.)

∑

( + 4)

2

+−4

=

2

−3

##### Page 13

Page

1

of

4

Computer Science Foundation Exam

January 12, 2019

Section II B

ALGORITHMS AND ANALYSIS TOOLS

NO books, notes, or calculators may be used,

and you must work entirely on your own.

Name:

___________________________________________

UCFID:

___________________________________________

NID:

___________________________________________

Question #

Max Pts

Category

Passing

Score

1

5

DSN

3

2

10

ALG

7

3

10

DSN

7

TOTAL

25

17

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.

##### Page 14

Spring 2019

Algorithms and Analysis Tools Exam, Part B

Page

2

of

4

1)

(5 pts) DSN (Recursive Coding)

Mathematically, given a function f, we recursively define f

k

(n) as follows: if k = 1, f

1

(n)

= f(n).

Otherwise, for k > 1, f

k

(n) = f(f

k-1

(n)). Assume that a function, f, which takes in a single integer and

returns an integer already exists. Write a

recursive

function fcomp, which takes in both n and k (k > 0),

and returns f

k

(n).

int f(int n);

int fcomp(int n, int k) {

}

##### Page 15

Spring 2019

Algorithms and Analysis Tools Exam, Part B

Page

3

of

4

2)

(10 pts) ALG (Sorting)

(a)

(5 pts) Consider using Merge Sort to sort the array shown below. What would the state of the

array be right before the

last

call to the Merge function occurs?

index

0

1

2

3

4

5

6

7

8

9

value

20

15

98

45

13

83

66

51

88

32

Answer:

index

0

1

2

3

4

5

6

7

8

9

value

(b)

(5 pts) An inversion in an array,

arr,

is a distinct pair of values

i

and

j

, such that

i

<

j

and

arr[i] >

arr[j].

The function below is attempting to count the number of inversions in its input array,

arr

,

of size

n

. Unfortunately, there is a bug in the program. Given that the array passed to the function

has all distinct values, what will the function always return (no matter the order of values in the

input array), in terms of n? Also, suggest a quick fix so that the function runs properly. (Note:

analyzing inversions is important to studying sorting algorithm run times.)

int countInversions(int arr[], int n) {

// line 1

int i, j, res = 0;

// line 2

for (i = 0; i < n; i++) {

// line 3

for (j = 0; j < n; j++) {

// line 4

if (arr[i] > arr[j])

// line 5

res++;

// line 6

}

// line 7

}

// line 8

return res;

// line 9

}

// line 10

Return value of the function in terms of n: _______________________

Line number to change to fix the function: _____________

Line of code to replace that line: _____________________________________________________

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