CSCE4110 - Exam 1

Question 1

What is an algorithm

Answer 1

a step-by-step procedure for solving a problem or accomplishing some end

Question 2

statement is true prior to the first iteration

Answer 2

initialization

Question 3

if it is true before the iteration of the loop it remains true before the next iteration

Answer 3

maintenance

Question 4

is true at the end of the loop

Answer 4

termination

Question 5

j=2, therefore A[i:j-1] is A[1], single element=>sorted

Answer 5

initialization

Question 6

we move elements until proper position of a[j] is found. therefore if a[1:j-1] is sorted after iteration j A[1:j] is sorted

Answer 6

maintenance

Question 7

ends when j=n+1; therefore based on maintenance criteria A[1:n] is sorted

Answer 7

termination

Question 8

time complexity of merge sort

Answer 8

theta(n log n)

Question 9

how to get time complexity of merge sort

Answer 9

split each node by 1/2 and there are log(n)+1 levels

Question 10

max-heap: parent

Answer 10

floor( i / 2 )

Question 11

max-heap: left

Answer 11

2(i)

Question 12

max-heap: right

Answer 12

2(i) + 1

Question 13

counting sort

Answer 13

one array of the input, one array of indexing each value, one array of input frequency

Question 14

radix sort

Answer 14

start sorting with least significant digit

Question 15

bucket sort

Answer 15

sort numbers into linked list based on first digit

Question 16

counting sort assumption

Answer 16

maximum value in list is not especially large

Question 17

radix sort assumption

Answer 17

d is significantly less than log(n)

Question 18

bucket sort assumption

Answer 18

input is uniformly distributed

Question 19

worst case time complexity of hash tables

Answer 19

O(n)

Question 20

average case time complexity of hash tables

Answer 20

O(1)

Question 21

chaining hash tables

Answer 21

put elements with same hash value into linked list

Question 22

properties of good hash function

Answer 22

satisfies assumption of simple uniform hashing

derives hash values independent of any patterns in the data

Question 23

open addressing hash tables

Answer 23

does not use linked list, in event of collision probe until open slot is found

Question 24

when should hash tables be used

Answer 24

where direct addressing is inefficient

Question 25

preorder traversal

Answer 25

dot left of node

Question 26

inorder traversal

Answer 26

dot bottom of node

Question 27

postorder traversal

Answer 27

dot right of node

Question 28

role of T.nil

Answer 28

ensures that every leaf is black

Question 29

if node is red…

Answer 29

both children are black

Question 30

the root of a red black tree is

Answer 30

black

Question 31

for each node, all paths from the node to descendant leaves…

Answer 31

contain the same number of black nodes

Question 32

three advantages of red black trees

Answer 32

ensures some degree of balance

height is guaranteed O(log n)

rotations done in constant time

Question 33

two key conditions for dynamic programming (greedy algorithms)

Answer 33

optimal substructure

overlapping subproblems

Question 34

dynamic programming often uses

Answer 34

memorization

Question 35

optimal substructure is

Answer 35

when an optimal solution contains optimal solutions to subproblems

Question 36

overlapping subproblems is

Answer 36

recursive algorithms, records subproblems solutions for future use

Question 37

Longest common subsequence is often used in

Answer 37

genome sequencing