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