Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Data structures > Quiz 1 > Flashcards

Quiz 1 Flashcards

0
Q

If f(n) is in O(kg(n)) for any constant k>0 then

A

f(n) is in O(g(n))

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

If f(n) is in O(n) and g(n) is in O(h(n)) then…

A

f(n) is in O(h(n))

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

If f1(n) is in g1(n) and f2(n) is in g2(n) then f1(n) + f2(n) is

A

in O(max(g1(n),g2(n)))

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

If f1(n) is in O(g1(n)) and f2(n) is in O(g2(n)) then f1(n)f2(n) is

A

in O(g1(n)g2(n))

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

Growth ratefastest->slowest

A

constant, multi log, log, log squared, log^k, linear, nlogn, N^2, N^3, c^N

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

Form for an algebraic spec

A 
adt NAME
    uses \_\_\_\_\_
    operations:
    preconditions
    axioms
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Big O

A

T(N) is (f (N)) if there exists c, n such that T(N) = n. (upper bound)

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

Big Omega

A

T(N) is Omega(g(N)) if there exists c, n such that

T(N) >= cg(N) for all N >= n. (lower bound)

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

Big Theta

A

T(N) is Theta(h(N)) if and only if T(N)=(h(N)) and

T(N) = Omega(h(N)). (tight bound)

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

Little o

A

T(N) is o(p(N)) if for all c there exists n such that
T(N) < cp(N) when N > n. (loose upper bound: T(N)=(p(N))
but T(N) 6 != (p(N)) )

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

Array - indexing complexity

A

O(1)

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

Array - search

A

O(n)

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

Dynamic Array - indexing

A

O(1)

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

Dynamic Array - Search

A

O(n)

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

Dynamic Array - Insertion

A

O(n)

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

Dynamic Array - deletion

A

O(n)

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

Singly Linked List - indexing

A

O(n)

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

Singly Linked List - Search

A

O(n)

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

Singly Linked List - insertion

A

O(1)

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

Singly Linked List - deletion

A

O(1)

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

Doubly Linked List - indexing

A

O(n)

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

Doubly Linked List - Search

A

O(n)

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

Doubly-Linked List - insertion

A

O(1)

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

Doubly-Linked List - deletion

A

O(1)

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

Binary Search Tree - Indexing

A

O(log(n)), average. O(n) worst

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

Binary Search Tree - Search

A

O(log(n)), average. O(n) worst

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

Binary Search Tree - Insertion

A

O(log(n)), average. O(n) worst

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

Binary Search Tree- deletion

A

O(log(n)), average. O(n) worst

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

Splay Tree - Search

A

Always O(log(n))

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

Splay Tree - Insertion

A

Always O(log(n))

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

Splay Tree - deletion

A

Always O(log(n))

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

AVL Tree- Search

A

Always O(log(n))

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

AVL Tree- insertion

A

Always O(log(n))

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

AVL Tree - deletion

A

Always O(log(n))

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

Binary Search

A

O(log(n)) always on sorted array of n elements

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

Bubble Sort

A

Best, O(n).
Worst, O(n^2).
Average, O(n^2)

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

Merge Sort

A

always O(nlog(n))

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

Insertion Sort

A 
best O(n).
average O(n^2)
worst O(n^2)
39
Q

Bag Structure methods

A

add, remove, contains, size, clear, isEmpty

40
Q

Set Structure Methods

A

add, remove, size, isEmpty, contains, union, intersect

41
Q

Queue Structure Methods

A

enqueue, dequeue, front,

42
Q

Stack Structure Methods

A

push, pop, peek

43
Q

Tree

A

update, insert, delete, getValueFromKey

44
Q

amortized analysis of efficiency

A

method of anallyzing algorithms that consider the entire sequence of operation of the program. Its bigO notation.

45
Q

binary trees - how many children

A

2 most

46
Q

BST property

A

the key in any node is larger than all keys in that nodes left subtree and smaller than all keys in the right subtree.

47
Q

how many nodes fit in each level

A

2^i where i is the level

48
Q

how many nodes can a tree with h levels store

A

(2^h) - 1

49
Q

depth of root

A

0

50
Q

depth of node generally

A

1 + depth of parent

51
Q

heigh of tree

A

leaves have 0.

Generally - 1 + heigh of children

52
Q

AVL Tree condition

A

every node in tree, heigh of left and right differ by <= 1

53
Q

breadth first print

A

Starts at root, prints left to right before going to next level down

54
Q

depth first preorder

A

visit current node, then entire left tree, then entire right subtree

55
Q

depth first postorder

A

visit entire left, then entire right tree - then current node.

56
Q

Binary Search

A

O(logn)

57
Q

find place to check binary search

A

(start +end )/2

58
Q

deque

A

removeal and insertion at both ends “double ended queue”

59
Q

bubble sort

A

bubble biggest rightward. O(N^2)

60
Q

selection sort

A

find smallest each time O(N^2)

61
Q

insertion sort

A

swap adjacent each time two insert O(N^2)

62
Q

merge sort

A

O(NlgN)

63
Q

heap sort

A

bottum up build + N removals O(NlgN)

64
Q

quick sort time complexity

A 
worst O(N^2)
best O(NlgN)
65
Q

bottom up heap build time complexity

A

O(N)

66
Q

insert/removemax for heap

A

o(lgN)

67
Q

degree

A

number of incident edges

68
Q

adjacent edges

A

edge between u and v exists

69
Q

multigraph

A

a graph that can have repeated edges

70
Q

Cycle

A

a path of length >= whose first and last are the same

71
Q

connected graph G

A

there is a path in g from every vertex to everyother

72
Q

acyclic graph

A

a graph with no cycles

73
Q

tree

A

an acyclic connected graph

74
Q

forrest

A

a disjoint set of trees

75
Q

subgraph of G

A

subset of graph G’s edges and verts

76
Q

spanning tree of a connected graph G

A

a subgraph that contains all of G’s verticies and is a single tree

77
Q

summ of all degrees in normal graph

A

2M

78
Q

undirected graph

A

M<= (N(N-1)/2)

79
Q

directed graph M

A

M <= N(N-1)

80
Q

connected graph M

A

M >= N -1

81
Q

tree M

A

M = N - 1

82
Q

forrest M

A

M <= N - 1

83
Q

graph small scale operations

A

getnumVerts, getNumEdges, boolean adjacent(u,v), neighbors(V), int degree (v), boolean incident(v,e), bolean connected(u,v)

84
Q

graph large scale operations

A

depth first search, breadth first search, find spanning tree, shortest path between verts, connected components, isConnected, isTree, hamiltonianTour, Eulerian Path

85
Q

Hamiltonian Tour

A

visit every vertex exactly 1x

86
Q

Eulerian Path

A

visit all edges exactly 1x

87
Q

adjacency matrix

A

store a v x v boolean array that is true exactly when an edge v-w exists

88
Q

array of edges

A

stores a list of edge objects where each one has two int instance variables

89
Q

adjacency list

A

store a vertex index array of lists of vertices. VertexArray[i] is linked list of verticies adjacent to vertex[i]

90
Q

Topological Sort

A

order vertices so that each v comes earlier in list than any other vertex to which an edge leads from v

91
Q

strongly connected graph

A

are all vertex pairs(v,w) s.t. v is reachable from w and w is reachable from v

92
Q

single source unweighted shortest path

A 
O(N+M).
Set all distances to infinity
Set all previous to null.
Set source to 0.
Begin BFS: 
Q.enqueue(s) 
While Q is not empty: 
v = Q.dequeue()
for all u in neighbors(v) with prev[u]==null 
dist[u] = dist[v] + 1
prev[u] = v 
Q.enqueue(u)
93
Q

Complexity of Dijkstras Algorithm

A

O(MlgN) with adaptable heap

94
Q

Topological Sort time complexity

A

O(N+M) to compute indegrees
O(N+M) to determine ordering
O(N+M) total

Data structures (2 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions