CMPSC 130A Midterm Prep

Prof Vigoda UCSB F25

Adjacency List space

O(n + m)

Adjacency List traversal

O(n + m)

Adjacency List lookup

O(n)

Adjacency list insertion

O(n)

Adjacency Matrix Space

O(n^2)

Adjacency Matrix Traversal

O(n^2)

Adjacency Matrix insertion

O(1)

Adjacency Matrix Lookup

O(1)

DFS Runtime

O(n + m)

Explore runtime (all of the calls to it combines)

O(m)

f grows no faster than g

f = O(g)

f grows at the same rate as g

f = Theta(g)

f grows at least as fast as g

f = Omega(g)

number of edges in undirected graph

m <= n choose 2

number of edges in directed graph

m <= n(n-1)

Algo for marking all the connected components

DFS-cc

DFC-cc runtime

O(n + m)

edges from a non-child descendant to an ancestor

back edges

edges from a non-parent node to a descendant

forward edges

edges to a non-ancestor and non-descendant

cousin edges

what two arrays do we add to DFS to make it work for directed graphs?

pre and post

Kosaraju’s Algo (SCC) runtime

O(n + m)

What algorithm do we use to split the graph into SCCs?

Kosaraju’s Algo

BFS runtime

O(n + m)

Dijkstra’s Runtime

O(log n(n+m))

Dijkstra’s insert runtime

O(log n)

Dijkstra’s insert inputs

heap H, node v, dist dist[v]

Dijkstra’s deletemin runtime

O(log n)

Dijkstra’s deletemin inputs

heap H

Dijkstra’s decreasekey runtime

O(log n)

Dijkstra’s decreasekey inputs

heap H, node v, dist[v]

Dijkstra’s inputs:

Graph G, weights w, start node s

Subgraph that is connected and acyclic

Tree

Subgraph that is acyclic

Forest

Number of edges in a tree

n - 1

Inputs to Kruskal’s Algorithm

G, w

Greedy algo for getting an MST

Kruskal’s Algorithm

Kruskal’s runtime

O(m log n)

Prim’s algorithm inputs

G, w

Prim’s algorithm runtime

O(m log n)

an edge that is guaranteed to be in the MST of a graph

cut

top sort runtime

O(n + m)

SP-DAG Inputs

Graph G, weights w, start node s

SP-DAG runtime

O(n + m)

Union-Find makeset() runtime

O(1)

Union-Find find() runtime

O(log n)

Union-Find union() runtime

O(log n)

Hashing with a linked list at each array index

Chain Hashing

Hashing method using two hash functions, and placing the item into the bucket with lesser load

2-choice hashing

Max load of a bucket in a one-function hash

log n

Max load of a bucket in a two-function hash

log log n

Hashing method using one bit array and multiple hash functions

Bloom Filter

Chain Hashing LL Insert() runtime

O(1)

Chain Hashing LL Find() runtime

O(log n)

Chain Hashing LL Delete() runtime

O(log n)

Bloom filter: fraction bits still 0 after n insertions

e^(-kn/m)

Bloom filter: false positive rate

(1 - e^(-kn/m))^k

Max load of a bucket in a d-function hash

log log n / log d