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:
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
Know more
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
