Showing 8-11 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 8
Spring 2019
Data Structures Exam, Part B
Page
4
of
4
3)
(10 pts) ALG (AVL Trees)
a)
Show the result of inserting 37 into the following AVL tree:
84
/
\
25
106
/
\
\
12
39
212
/
30
b)
Using big-oh notation, give the
best-case
runtime for inserting a new element into an AVL tree with
n
nodes:
c)
Using big-oh notation, give the
worst-case
runtime for inserting a new element into an AVL tree
with
n
nodes:
d)
Using big-oh notation, give the
best-case
runtime for inserting a new element into a binary search
tree with
n
nodes:
e)
Using big-oh notation, give the
worst-case
runtime for inserting a new element into a binary search
tree with
n
nodes:
Page 9
Page
1
of
4
Computer Science Foundation Exam
January 12, 2019
Section II A
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
10
ANL
7
2
5
ANL
3
3
10
ANL
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. For each coding
question, assume that all of the necessary includes (stdlib, stdio, math, string) for
that particular question have been made.
Page 10
Spring 2019
Algorithms and Analysis Tools Exam, Part A
Page
2
of
4
1)
(10 pts) ANL (Algorithm Analysis)
With proof, determine the Big-Oh run time of the function, f, below, in terms of the input parameter n.
(Note: You may use results from algorithms studied previously in COP 3502 without restating the full
proof of run time.)
#include <math.h>
int f(int array[], int n) {
return frec(array, 0, n-1);
}
int frec(int array[], int lo, int hi) {
if (lo == hi) return array[lo];
int left = frec(array, lo, (lo+hi)/2);
int right = frec(array, (lo+hi)/2+1, hi);
int i, lCnt = 0, rCnt = 0;
for (i=lo; i<=hi; i++) {
if (abs(array[i]-left) < abs(array[i]-right))
lCnt++;
else
rCnt++;
}
if (lCnt > rCnt) return lCnt;
return rCnt;
}
Page 11
Spring 2019
Algorithms and Analysis Tools Exam, Part A
Page
3
of
4
2)
(5 pts) ANL (Algorithm Analysis)
An algorithm processing a two dimensional array with R rows and C columns runs in
(
2
)
time. For
an array with 100 rows and 200 columns, the algorithm processes the array in 120 ms. How long would
it be expected for the algorithm to take when processing an array with 200 rows and 500 columns?
Please express your answer in
seconds.
________________
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
