CSCE4110 - Exam 1 Flashcards

1
Q

What is an algorithm

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

statement is true prior to the first iteration

A

initialization

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

maintenance

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

is true at the end of the loop

A

termination

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

initialization

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

maintenance

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

termination

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

time complexity of merge sort

A

theta(n log n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

how to get time complexity of merge sort

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

max-heap: parent

A

floor( i / 2 )

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

max-heap: left

A

2(i)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

max-heap: right

A

2(i) + 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

counting sort

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

radix sort

A

start sorting with least significant digit

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

bucket sort

A

sort numbers into linked list based on first digit

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

counting sort assumption

A

maximum value in list is not especially large

17
Q

radix sort assumption

A

d is significantly less than log(n)

18
Q

bucket sort assumption

A

input is uniformly distributed

19
Q

worst case time complexity of hash tables

20
Q

average case time complexity of hash tables

21
Q

chaining hash tables

A

put elements with same hash value into linked list

22
Q

properties of good hash function

A

satisfies assumption of simple uniform hashing

derives hash values independent of any patterns in the data

23
Q

open addressing hash tables

A

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

24
Q

when should hash tables be used

A

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