Algorithms Final

f = o(g) (little o)

f(n)/g(n), analogous to <, limit = 0

f = ω(g) (little omega)

f(n)/g(n), analogous to >, limit = inf

f = O(g) (big O)

f(n)/g(n), analogous to < or equal to, limit = finite

f = Ω(g) (big omega)

f(n)/g(n), analogous to > or equal to, limit = positive

f = θ(g)

f(n)/g(n), analogous to =, limit = finite and positive

Asymptotic notation trick for polynomials

• deg(f) < deg(g) → f = o(g)

• deg(f) > deg(g) → f = ω(g)

• deg(f) = deg(g) → f = θ(g)

Asymptotic notation trick for logs, exponentials, and polynomials

logs are little o of polynomials which are little o of exponentials

Binary search

finds a specific value in a sorted array by repeatedly dividing the search interval in half

O(log n)

merge sort

• sorts a given list of numbers by first dividing them into two equal

  halves, sorting each half separately by recursion, and then combining the results of these recursive calls—in the form of the two sorted halves

• T(n) = 2T(n/2) + O(n)

• O(n log n)

quicksort

• picks an element in the array as a pivot. Partition the array so values < pivot are to its left and values > pivot are to its right. Recursively sort the two halves

• Best case: T(n) = 2T(n/2) = O(n) Worst case: T(n) = T(1) + T(n-1) = O(n)

• Expected time: O(n log n) Worst time: O(n²)

Dselect

to find the kth smallest element in a list or array. It works by dividing the input array into smaller groups, finding the median of each group, and then recursively finding the median of those medians.

BFS

explores all neighbors of a node before moving to the next level, used to find shortest path

DFS

• traversing or searching tree or graph data structures, exploring as far as possible along each branch before backtracking

• mark node as visited

• O(V+E)

Kosaraju’s

• Finds all SCCs in graph

• Compute transpose graph G^T. Do DFS on G^T. Do DFS on G (processing vertices in reverse order of finish time of previous step).

• O(n+m)

topological sorting

Do DFS, keep track of when each visit call terminates, return vertices in reverse order of finish time

O(V+E)

DAG Shortest Paths

• Create a topological order of vertices. For every vertex being processed, we update distances of its adjacent using distance of current vertex.

• O(n+m)

sink

a vertex with no outgoing edges

source

a vertex with no ingoing edges

Dynamic programming

Identify a useful collection of subproblems

Find a recursive relationship between subproblem solutions

Apply it bottom-up, storing subproblem solutions as you go

path-MWIS

maximize total weight of an independent set
DP?

longest increasing subsequence

Takes an array of integers and produces the maximum length of an increasing subsequence

DP?

sequence alignment (edit distance)

• replace, insert, delete

• find DAG shortest path from (0,0) to (m,n)

• DP?

knapsack

There are i items, each with a positive integer value and positive integer weight and there is a capacity W. Find a set to maximize value within the capacity.

DP?

Bellman-Ford

Negative cycle detection algorithm

repeatedly checks and updates distance estimates from the source node to all other nodes (spam updates)

O(VE)

Floyd-Warshall

find the shortest paths between all pairs of vertices in a weighted graph, whether directed or undirected, with or without negative edge weights (but without negative cycles)

It works by iteratively updating a matrix of shortest path distances, considering each vertex as a potential intermediate point in the path

O(n³) n = vertices

Dijkstra’s

find the shortest paths from a single source vertex to all other vertices in a graph.

It operates by iteratively exploring the graph, marking vertices as visited, and updating shortest path distances until all vertices are considered

Worst case: O(V²), normally O((V+E) log V)

DP

Prim’s

find the most efficient way to connect all vertices in a graph with the least total edge weight

find the minimum spanning tree (MST) of a connected, weighted, undirected graph.

It works by iteratively adding the minimum-weight edge that connects a vertex in the MST to a vertex not yet in the MST.

O(E + V log V)

Ford-Fulkerson

find the maximum flow in a network.

It works by repeatedly finding augmenting paths and increasing the flow along them until no more such paths exist

Its purpose is to determine the maximum amount of flow that can be sent from a source to a sink within a network, given the capacity constraints of the edges

O(|f*||E|)

Edmonds-Karp

a maximum flow algorithm that uses BFS to find augmenting paths in a flow network.

a variant of Ford-Fulkerson

determine the maximum amount of flow that can be sent from a source to a sink in a network

O(V * E^2)

capacity

the maximum amount of flow that can be transported across an edge in a given period of time

residual network

a representation of the remaining capacity for sending flow through a flow network.

augmenting path

path from the source s to the sink t in the residual network where every edge on the path has positive residual capacity. It represents a route along which additional flow can be pushed.

(s, t)-cut

a partition of the graph’s vertices into two disjoint sets S and T such that:

• The source s is in set S

• The sink t is in set

The cut refers to the set of edges going from S to T.

max-flow min-cut theorem

the maximum flow through a network from a source to a sink is equal to the capacity of the minimum cut in that network

P

A yes or no problem is in ___ if the answer can be computed in polynomial time

verifier

an algorithm that can quickly confirm whether a given solution to a problem is correct

certificate

it's a proof or solution that can be easily checked, but might be hard to find

NP

a class of problems where a solution, if given, can be verified in polynomial time

Karp reducibility (≤_p)

the concept of reducing one problem in NP to another problem in NP within polynomial time.

This means that if a problem A is ___ to a problem B, then if an efficient algorithm exists for problem B, it also implies an efficient algorithm for problem A. 

NP-hard

used to classify problems that are, in a sense, as hard as the hardest problems in NP

NP-complete

if a problem is in NP and is NP-hard

problem within the complexity class NP that has the property that every other problem in NP can be reduced to it in polynomial time

3SAT

asks whether a given 3CNF formula is satisfiable (is it possible to assign true or false to the variables in a way that makes the formula true)

NP-complete

HAM-CYCLE

to determine if graph G contains a Hamiltonian cycle consisting of all the vertices belonging to V
NP-complete

IND-SET

asks whether graph G has an independent set of size k

NP-complete

VERTEX-COVER

does graph G have a vertex cover (a subset of vertices touches each edge at least once) of size k?

NP-complete

TSP

given a weighted complete digraph and a number b, is there a Ham. cycle of total weight <= b?

NP-complete

HIT

Given a set X and subsets C₁, …, C_m in X and a number k, is there a subset S in X such that S = k

find the smallest subset of X, such that the smallest subset, H hits every set comprised in C.