Cse 373

Front 1

insert sorted array

Back 1

n

Front 2

look up sorted array

Back 2

log n

Front 3

deleted sorted array

Back 3

n

Front 4

getMin sorted array

Back 4

1

Front 5

getMax sorted array

Back 5

1

Front 6

getMax unsorted array

Back 6

n

Front 7

getMin unsorted array

Back 7

n

Front 8

deleted unsorted array

Back 8

n

Front 9

look up unsorted array

Back 9

n

Front 10

insert unsorted array

Back 10

1

Front 11

inser heap

Back 11

logn

Front 12

look up heap

Back 12

n

Front 13

delete heap

Back 13

n

Front 14

heap getMin

Back 14

1

Front 15

heap getMax

Back 15

n

Front 16

insert avl

Back 16

log n

Front 17

lookup avl

Back 17

log n

Front 18

delete avl

Back 18

log n

Front 19

getMin avl

Back 19

log n

Front 20

getMax avl

Back 20

log n

Front 21

chaining hash insert

Back 21

1

Front 22

chaining hash lookup

Back 22

n

Front 23

chaining hash delete

Back 23

n

Front 24

chaining hash getMin

Back 24

n

Front 25

chaining hash getMax

Back 25

n

Front 26

Suppose a graph has no edges. What is the asymptotic space cost of storing the graph as an adjacency list?

Back 26

v

Front 27

Suppose a graph has no edges. What is the asymptotic space cost of storing the graph as an adjacency matrix?

Back 27

V^2

Front 28

Suppose a graph has every possible edge. What is the asymptotic space cost of storing the graph as an adjacency list?

Back 28

V^2

Front 29

Suppose an undirected graph has one node A that is connected to every other node and the graphhas no other edges. What is the asymptotic space cost of storing the graph as an adjacency list?

Back 29

V

Front 30

Suppose an undirected graph has one node A that is connected to every other node and the graph has no other edges. What is the asymptotic space cost of storing the graph as an adjacency matrix?

Back 30

V^2

Front 31

Suppose a graph has every possible edge. What is the asymptotic space cost of storing the graph as an adjacency matrix?

Back 31

V^2

Front 32

Is an adjacency list faster or slower than an adjacency matrix for answering queries of the form,“is edge (u, v) in the graph”?

Back 32

slower

Front 33

Is an adjacency list faster or slower than an adjacency matrix for answering queries of the form,“are there any directed edges with u as the source node”?

Back 33

faster

Front 34

insertion sort

Back 34

void insertionSort(int [] array) {

for(int i=1; i < array.length; i++) {

int tmp = array[i];

int j;

for(j=i; j > 0 && tmp < array[j-1]; j--)

array[j] = array[j-1];

array[j] = tmp

}

};

Front 35

What is the worst-case asymptotic running time of heap-sort?

Back 35

n log n

Front 36

What is the worst-case asymptotic running time of merge-sort?

Back 36

n log n

Front 37

What is the worst-case asymptotic running time of quick-sort?

Back 37

n^2

Front 38

Can heap-sort be done in-place?

Back 38

yes

Front 39

Can merge-sort be done in-place?

Back 39

no

Front 40

Can quick-sort be done in-place?

Back 40

yes

Front 41

Consider one item in an array that is sorted with mergesort. In asymptotic (big-Oh) terms, howmany times can that one item move to a different location?

Back 41

log n

Front 42

What is the asymptotic running time of quick-sort if the array is already sorted (or almost sorted)and the pivot-selection strategy picks the leftmost element in the range-to-be-sorted?

Back 42

n^2

Front 43

What is the asymptotic running time of quick-sort if the array is already sorted (or almost sorted)and the pivot-selection strategy picks the rightmost element in the range-to-be-sorted?

Back 43

n^2

Front 44

What is the asymptotic running time of quick-sort if the array is already sorted (or almost sorted)and the pivot-selection strategy picks the middle element in the range-to-be-sorted?

Back 44

n log n

Front 45

Before starting a comparison sort for an array with n elements, how many possible orders arethere for the elements in the final result?

Back 45

n!

Front 46

If at some point during a comparison sort, the algorithm has enough information to narrow thefinal result down to k possibilities, what is the least number of possibilities that remain afterperforming an additional comparison?

Back 46

k/2

Front 47

insertion sort worst case

Back 47

n^2

Front 48

selection sort worst case

Back 48

n^2

Front 49

heap sort worst case

Back 49

n log n

Front 50

merge sort worst case

Back 50

n log n

Front 51

quick sort avg worst case

Back 51

n log n

Front 52

bubble sort worst case

Back 52

n^2

Front 53

quicksort

Back 53

1. pick pivot

2 partition data into 3 with pivot in middle

3 recursivley sort a,c

result a,pivot,c

Front 54

bucket sort

Back 54

count bucket

Front 55

radix sort

Back 55

sort by each number place each iteration

Front 56

bubble, insertion, selection sorts are good for

Back 56

below a cutoff

Front 57

Bin Tree max # leaves

Back 57

2^h

Front 58

max # nodes

Back 58

2^(n+1) -1

Front 59

mix # leaves

Back 59

1

Front 60

deletion bin tree

Back 60

move minmum from right

or

move maximum from left

Front 61

BuildTree sorted worst case

Back 61

n log n

Front 62

balance factor

Back 62

left and right subtree should have a height difference of 1

Front 63

double rotation

Back 63

1 rotate problematic into parent position

2 parent becomes the other child

Front 64

AVLbuildTree worst case

Back 64

n log n

Front 65

load factor

Back 65

n / table size

Front 66

union find uses

Back 66

connecnted components

parition an image my connected pixels of similiar color

type inference

Front 67

union worst case

Back 67

1

Front 68

find worst faces

Back 68

log n

Front 69

sorted cicular array insert w.c

Back 69

log n

Front 70

sorted circular array deleteMin w.c.

Back 70

1

Front 71

heap structure

Back 71

like bst except parent not as important

Front 72

delete min heap basic idea

Back 72

move right most and perculate down (n)

Front 73

insert heap basic idea

Back 73

insert right most and perculate up (logn)

Front 74

dense graph

Back 74

e theta (v^2)

Front 75

sparse graph

Back 75

O(V)

Front 76

minimum spanning tree

Back 76

connected graph

Front 77

topological sort

Back 77

mark in degree then out put when in degree equals 0

Front 78

kruskal

Back 78

1. Sort edges by weight (better: put in min-heap)2. Put each node in its own subset (of a UNION-FIND instance).3. While output size < |V|-1 – Consider next smallest edge (u,v)– if find(u) and find(v) indicate u and v are in different sets output (u,v) Perform union(find(u),find(v))

e log e

Front 79

hamiltonian cycle

Back 79

there is a cycle that visits all nodes exactly once

Front 80

SAT

Back 80

all satifiable cicuits c

Front 81

dfs

Back 81

pre order traversal

Front 82

bfs

Back 82

"level order traversal"

Front 83

shortest distance on network

Back 83

udirected weighted djsktras

Front 84

creates smallest driect weighted network

Back 84

directed weighted mst

Front 85

level spread

Back 85

undirected , unweighted , bfs