Brainscape's Knowledge GenomeTM

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


See full index

CSC 225 > Final Exam > Flashcards

Final Exam Flashcards

1
Q

How are items inserted and removed in a Stack?

A

LIFO

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

What methods does the Stack ADT support?

A 
push()
pop()
isEmpty()
top()
size()
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

pro/cons of Array-based Stack

A

O(1) per operation, but size must have an upper bound

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

How are items inserted/removed in a queue?

A

FIFO

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

What methods does queue support?

A 
enqueue()
dequeue()
isEmpty()
front()
size()
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Pro/cons for array implementation of the queue

A

O(1) per operation

needs to have a fixed size

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

Methods that Index Based List supports

A

get(index)
set(index, element)
add(index, element)
remove(index)

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

Running times of array based index-based list

A

get - O(1)
set - O(1)
add - O(n)
remove - O(n)

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

Running times of various linked list methods

A 
first() - O(1)
last() - O(1)
before() - O(1)
after() - O(1)
element() - O(1)
remove - O(1)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Steps of MergeSort

A

1) Divide: sequence into 2 sequences
2) Recur: until all sequences have zero or one element
3) Conquer: merge the sequences all back together

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

Steps of QuickSort

A

1) Pick a pivot element
2) Sort list into 2 new lists less than pivot and greater than pivot
3) recur
4) conquer

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

What is a Priority Queue?

A

A container of elements, each with a key which determines the priority used to remove elements

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

Pros/Cons of unsorted vs sorted Priority Queue?

A

Unsorted: insert takes O(1) but remove takes O(n)
Sorted: insert takes O(n) time but remove takes O(1)

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

How to use a priority queue to sort elements?

A

Insert comparable elements one by one, and then remove them

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

PQ-sort where the priority queue is implemented with an unsorted sequence is like…

A

Selection sort!

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

PQ-sort where the priority queue is implemented with a sorted sequence is like….

A

Insertion-Sort!

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

A heap is what kind of tree

A

A complete binary tree

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

What is the Heap-Order Property?

A

for every node v other than the root, the key stored at v is geq than the key stored at v’s parent

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

What is a complete binary tree

A

A tree that fills from the left to the right

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

General idea of inserting into Heap

A

insert at first available spot, and then bubble up the tree

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

removing min element from a heap

A

remove root, select last element and put it at root position, and bubble down to restore tree

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

What is the height of a balanced tree?

A

log(n)

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

What is the worst case time of insertion sort?

A

O(n^2)

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

What is the worst case time of bubblesort?

A

O(n^2)

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

What is the worst case time of selection sort?

A

O(n^2)

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

What is the worst case time of quick sort?

A

O(n^2)

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

What is the worst case time of heap sort?

A

O(n log n)

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

What is the worst case time of merge sort

A

O(n log n)

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

What is the best case time of insertion sort?

A

O(n)

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

What is the best case time of bubble sort?

A

O(n)

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

What is the best case time of selection sort?

A

O(n)

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

What is the best case time of quick sort?

A

O(n log n)

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

What is the best case time of heap sort?

A

O(n log n)

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

What is the best case time of merge sort?

A

O(n log n)

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

What is the average case time of insertion sort?

A

O(n^2)

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

What is the average case time of bubble sort?

A

O(n^2)

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

What is the average case time of selection sort?

A

O(n^2)

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

What is the average case time of quick sort?

A

O(n log n)

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

What is the average case time of heap sort?

A

O(n log n)

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

What is the average case time of merge sort?

A

O(n log n)

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

What are some properties of Insertion sort?

A

adaptive, stable, in place

42
Q

What are some properties of bubble sort?

A

in place

43
Q

What are some properties of selection sort?

A

in place

44
Q

What are some properties of quick sort?

A

in place

45
Q

What are some properties of heap sort?

A

in place

46
Q

What are some properties of merge sort?

A

not in place

47
Q

What’s Stirling’s formula? (utter bullshit)

A

n! ~= (2npi)^(1/2)*(n/e)^n

48
Q

What is the time complexity of radix sort with d keys?

A

O(dn)

49
Q

Methods for Tree ADT

A 
isInternal()
isExternal()
isRoot()
size()
elements()
positions()
swapElements()
replaceElements()
50
Q

What is a binary tree

A

Every node that is not a leaf has exactly 2 children

51
Q

What kind of search is pre-order traversal? What ADT does it use?

A

Depth first, stack

52
Q

What kind of search is in-order traversal? What ADT does it use?

A

symmetric, stack

53
Q

What kind of search is post-order traversal? What ADT does it use?

A

bottom up, stack

54
Q

What kind of search is level-order traversal? What ADT does it use?

A

breadth first, queue

55
Q

What happens in a removal from a BST if the node has children?

A

find the node that would follow the removed node in an inorder traversal, and put it in it’s place.

56
Q

Time complexity of size, IsEmpty, find, insert, remove on BSTs

A 
size - O(1)
isEmpty - O(1)
find - O(h)
insert - O(h)
remove - O(h)
57
Q

Worst case BST height

Best case BST height

A

O(n)

O(log n)

58
Q

Efficiency of 2-3 search and insertion

A

both O(log n)

59
Q

what is the height of a RBT with n keys

A

O(log n)

60
Q

What is a walk with no repeated edges

A

A trail

61
Q

A closed trail is a

A

circuit

62
Q

A walk with no repeated vertices is a

A

path

63
Q

A closed path is a

A

cycle

64
Q

What is a simple graph?

A

A graph with no self loops, parallel, or multi edges

65
Q

The sum of the degrees of all vertices =

A

2*number of edges

66
Q

the number of edges (m) is leq than THIS equation for the number of vertices (n)

A

(n(n-1)) / 2

67
Q

How many edges does a complete graph have?

A

(n(n-1)) / 2

68
Q

What is a spanning subgraph ?

A

A subgraph which contains all of the vertices of G

69
Q

A tree is

A

a connected, undirected graph with no cycles

70
Q

A forest is

A

an undirected graph without cycles (not necessarily connected! is made of many trees)

71
Q

Let G be an undirected graph with n vertices and m edges:

1) if G is connected, then m geq
2) if G is a tree, then m =
3) if G is a forest, then m leq

A

1) n-1
2) n-1
3) n-1

72
Q

In a simple digraph, the indegree of all vertexs =

A

outdegree of all vertex

=

number of edges

73
Q

For a digraph G, a pair of vertices is connected iff

A

every pair of vertices is connected

74
Q

For a digraph G, a pair of vertices is strongly connected iff

A

for all pairs of vertices u and v, u is reachable from v and v from u

75
Q

What is a DAG

A

a directed acyclid graph with no cycles

76
Q

The outdegree of a vertex k is the sum of the adjacency matrix

A

elements in row k

77
Q

The indegree of a vertex k is the sum of the adjacency matrix

A

elements in column k

78
Q

When do you use adjacency matrix structure over adjacency list structure

A

when there is a large number of edges

79
Q

What ADT does DFS use?

A

Stack

80
Q

What ADT does BFS use?

A

queue

81
Q

2 properties of DFS

A

1) DFS visits all the vertices and edges in the connected component of starting vertex
2) the discovery edges labeled by DFS form a spanning tree of v

82
Q

Time complexity of DFS for a graph G = (V, E) is

A

O(n+m) for n vertices and m edges

83
Q

The BFS traversal of a graph visits

A

all vertices and edges

84
Q

the discover edges of a BFS

A

form a spanning tree

85
Q

What does it mean if (v, w) is a backedge in DFS

A

w is an ancestor of v

86
Q

What does it mean if (v, w) is a cross edgein BFS

A

w is either on the same level as v or in the next level

87
Q

What is the time complexity of BFS?

A

O(n + m) n vertices and m edges

88
Q

What is a discovery arc in BFS?

A

arcs leading to unvisited nodes (form a forest)

89
Q

What is a back arc in DFS

A

goes from a node to its ancestor

90
Q

What is a forward arc in DFS?

A

a non-spanning arc that goes from a node to a proper desendent

91
Q

What is a cross arc in DFS?

A

arcs that go from one node to another that are neither ancestor nor desendant

92
Q

Steps to Kosarajus algorithm

A

1) perform a post order DFS on G=(V, A)
2) construct G^-1 = (V, A^-1) by reversing each arc
3) redo DFS starting with highest numbered postorder DFS
4) resulting trees are Strongly connected components

93
Q

Topological sort is the same as

A

reverse postorder DFS

94
Q

The sum of i from 1 to n

A

(n(n+1)) / 2

95
Q

the sum of all a^i from 1 to n

A

(1-(a^(n+1))) / (1-a)

96
Q

f(n) is big-Oh g(n) if

A

f(n) leq g(n)

97
Q

f(n) is little-Oh g(n) if

A

f(n) < g(n)

98
Q

f(n) is big-Theta g(n) if

A

f(n) = g(n)

99
Q

f(n) is big-Omega g(n) if

A

f(n) geq g(n)

100
Q

f(n) is little-Omega g(n) if

A

f(n) > g(n)

101
Q

Def of Big-Oh

A

Let f, g: Z+ -> R
f(n) is O(g(n)) iff /exists constant c>0, c \in R and n_o>0, n \in Z such that
f(n) leq cg(n) for all n>n_o

CSC 225 (1 decks)

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