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:

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