Time complexity: (disjoint set operations) findSet
O(log n)
Time complexity: (disjoint set operations) makeSet
O(n) [trivial for each element] [not sure about this]
Time complexity: (disjoint set operations) union
O(n log n)
Time complexity: (RB trees) insert
O(log n)
Time complexity: (RB trees) delete
O(log n)
Time complexity: (RB trees) findSuccessor
O(log n)
Time complexity: (RB trees) findPredecessor
O(log n)
Time complexity: (BST) insert
O(n)
Time complexity: (BST) delete
O(n)
Time complexity: (BST) successor
O(n)
Time complexity: (BST) predecessor
O(n)
Time complexity: (RB tree) create tree insertion by insertion
O(n log n)
Time complexity: (sort methods) mergeSort
O(n log n)
Time complexity: (sort methods) heapSort
O(n log n)
Time complexity: build BST by repeated insertions
O(n^2)
Time complexity: (sort methods) bubble sort
O(n^2)
Time complexity: (sort methods) insertion sort
O(n^2)
Time complexity: (table lookup) is u connected to v in Floyd-Warshall?
O(1)
Time complexity: (list lookup) is u connected to v in adjacency list representation?
O(deg u)
Time complexity: Extract min in Prim
O(log E) = O(log V)
Time complexity: Extract min in Dijkstra
O(log E) = O(log V)
Time complexity: findSet in Kruskal
O(log E) = O(log V)
Time complexity: union in Kruskal
O(log E) = O(log V)
Time complexity: BFS
O(E + V)
Time complexity: DFS
O(E + V)
Time complexity: TopoSort
O(E + V)
Time complexity: Prim
O(E log V)
Time complexity: Dijkstra
O(E log V)
Time complexity: Kruskal
O(E log V)
Time complexity: Floyd-Warshall (all pairs shortest paths)
O(EV) = O(V^3)
Time complexity: Bellman-Ford (single source shortest path)
O(EV) = O(V^3)
How: insertionSort
1st position is considered to be sorted. Repeatedly take first item from non-sorted and put into sorted.
How: mergeSort
Split all items to be sorted (n, n/2, ..., 1). Merge one level at a time (1, 2, 4, ..., n), sorting the sub-arrays into a merged array.
Heap property
A[i] is larger/smaller than its children
What heap method is used to enforce the heap property, and what is its time complexity?
Heapify. O(h) (Height) = O(log n) (n = number of items in heap)
What is the time complexity of Buile-Heap?
O(n) (because the heights of most nodes in the tree are small)
How: heapSort
Build a max or min heap. Take the max or min item and exchange it with the last item in the array. Decrease heapsize by 1. Repeat until heap is empty.
What is a Priority Queue?
A priority queue is a max or min heap used to extract the items in increasing (max) or decreasing (min) order.
The Heap-Increase-Key (or decrease) is used to maintain the heap property. What is its time complexity?
O(log n)
The Max- or Min-Heap-Insert method is used to insert an item into a heap. What is its time complexity?
O(log n)
What is the Binary Search Tree Property?
left <= parent; right >= parent for every node
How do you find the minimum value in a binary search tree?
Go left and down until you can't anymore.
How do you find the maximum value in a binary search tree?
Go right and down until you can't anymore.
BST methods include search, minimum, maximum, successor, and predecessor. They all share the same time complexity. What is it?
O(log n) [the complexity is related to the height of the tree]
A red-black tree is a special kind of binary search tree that is ______________.
balanced
What is used to balance RB trees?
An extra bit of information - color: red or black.
What is the height of a tree?
The number of edges in the longest path to a leaf.
What is the black height of a tree?
The number of black nodes (including nil nodes) on the path from x to leaf, not counting x.
Maintaining RB tree properties upon insertion involves _________.
rotations
New nodes are inserted into RB trees as ______ _________.
red, leaves
Three cases for red-red violations:
1) red uncle, 2) black uncle and zig-zagging, 3) black uncle without zig-zagging
A graph consists of ____________.
a set of vertices and a set of edges
Two ways to represent edges in graphs are __________.
adjacency lists and adjacency matrices
How: BFS
Need graph and source vertex. Send out a wave from s. First hits all vertices 1 edge from s. Next wave hits all vertices 2 edges from s. Etc.
What data structure is used to maintain wavefront in BFS?
FIFO queue. Node is in queue once wave hits, and not once wave leaves it.
Does BFS reach all nodes in the graph?
No. Only those reachable from the source node.
How: DFS
Need graph, NO source vertex. Output 2 timestamps on each vertex - discovery time and finishing time. Parent can also be computed.
Does DFS reach all vertices in the graph?
Yes. The result of DFS is a forest of DFS trees.
As DFS progressess, every vertex has a ___________.
Color. White, gray, or black.
What is meant by the parenthesis structure of DFS?
If v's discovery and finish times are entirely within u's discovery and finish times, then v is a descendant of u. If the discovery and finish times are not nested, then neither vertex is a descendant of the other.
What can be said about u and v if the edge (u,v) is a back edge?
u is a descendant of v
What is a DAG?
A directed graph with no cycles.
How: Topological Sort
Run DFS on the graph. When a vertes is finished, insert it onto the front of a linked list (or on top of a stack). Return the linked list of vertices.
What is union by rank?
Make the root with the smaller rank into a child of the root with the larger rank. Rank is an upper bound on the height of the node.
What is a minimum spanning tree?
For a connected graph G with positive edge weights, a MST is a minimum weight set of edges that connects all of the vertices.
(T/F) A MST can have cycles.
False.
(T/F) For a graph with V vertices, the MST has V edges.
False. V - 1 edges.
List both methods for finding MSTs.
Kruskal (grows tree using disjoint sets; can have many trees during process)
Prim (grows tree by choosing lightest safe edge along cut; only one tree during process)
List the 4 shortest paths methods.
Dijkstra (no neg weight edges, priority queue, tracks distance and parent of discovered nodes; relaxes edges) O(E log V)
