CSCE4110 - Exam 1 Flashcards Preview

Programming > CSCE4110 - Exam 1 > Flashcards

Flashcards in CSCE4110 - Exam 1 Deck (37):
1

What is an algorithm

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

2

statement is true prior to the first iteration

initialization

3

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

maintenance

4

is true at the end of the loop

termination

5

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

initialization

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

maintenance

7

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

termination

8

time complexity of merge sort

theta(n log n)

9

how to get time complexity of merge sort

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

10

max-heap: parent

floor( i / 2 )

11

max-heap: left

2(i)

12

max-heap: right

2(i) + 1

13

counting sort

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

14

radix sort

start sorting with least significant digit

15

bucket sort

sort numbers into linked list based on first digit

16

counting sort assumption

maximum value in list is not especially large

17

radix sort assumption

d is significantly less than log(n)

18

bucket sort assumption

input is uniformly distributed

19

worst case time complexity of hash tables

O(n)

20

average case time complexity of hash tables

O(1)

21

chaining hash tables

put elements with same hash value into linked list

22

properties of good hash function

satisfies assumption of simple uniform hashing

derives hash values independent of any patterns in the data

23

open addressing hash tables

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

24

when should hash tables be used

where direct addressing is inefficient

25

preorder traversal

dot left of node

26

inorder traversal

dot bottom of node

27

postorder traversal

dot right of node

28

role of T.nil

ensures that every leaf is black

29

if node is red...

both children are black

30

the root of a red black tree is

black

31

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

contain the same number of black nodes

32

three advantages of red black trees

ensures some degree of balance

height is guaranteed O(log n)

rotations done in constant time

33

two key conditions for dynamic programming (greedy algorithms)

optimal substructure
overlapping subproblems

34

dynamic programming often uses

memorization

35

optimal substructure is

when an optimal solution contains optimal solutions to subproblems

36

overlapping subproblems is

recursive algorithms, records subproblems solutions for future use

37

Longest common subsequence is often used in

genome sequencing