Show Menu

cheatsheet for cs570 analysis of algorithms

Runtime Complexity

Formally: there exist constants c and n0 such that for all
suffic­iently large n: f(n) ≤ c . g(n)
c,n0 n : n ≥ n0, f(n) ≤ c . g(n)

Master theorem

T(n) = a·T(n/b) + f(n), a≥1 and b>1
let c = log_b a

Case 1: (only leaves) if f(n) = O(nc-e), then T(n) = Theta(nc) for some e>0
Case 2: (all nodes) if f(n) = theta(nc logk n) , k≥0 , T(n) = theta(nc logk+1n)
Case 3: (only internal nodes) if f(n) = omega(nc+e), then T(n) = theta(­f(n)) for some e>0

Kruskals Algorithm

Sort all edges by their weights
- Choose the minimum weight edge and join corres­pondent vertices (subject to cycles).
- Go to the next edge.
- Continue to grow the forest until all vertices are connected
Runtime Comple­xity:
Sorting edges – O(E log E)
Cycle detection – O(V) for each edge
Total: O(V * E + E * log E)

Depth-­Fir­st-­Search (DFS)

It starts at a selected node and explores as far as possible along each branch before backtr­acking. DFS uses a stack for backtr­acking

Breadt­h-F­irs­t-S­earch (BFS)

It starts at a selected node and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. BFS uses a FIFO queue for bookke­eping

Amortized Analysis

Aggregate method: The amortized cost of an operation is given by 𝑇(𝑛) / 𝑛
Accounting Method: We assign different charges to each operation; some operations may charge more or less than they actually cost.

Topolo­gical Sort

1. Select a vertex that has zero in-degree.
2. Add the vertex to the output.
3. Delete this vertex and all its outgoing edges.
4. Repeat

Coin Change

opt[k,x] = min(op­t[k­-1,x] , opt[k,x - dk] + 1)
Base : opt[1,x] = x, opt[k,0] = 0

01 knapsack

opt[k,x] = max(vk + opt[k-1, x - wk], opt[k-1,x]
base: opt[0,x] = 0, opt[k,0] = 0
opt[k,x] = opt[k-1,x] if wk > x

Djikstra's Algorithm

When algorithm proceeds, all vertices are divided into two groups
- vertices whose shortest path from the source is known
- vertices whose shortest path from the source is NOT discovered yet.
Move vertices one at a time from the undisc­overed set of vertices to the known set of the shortest distances, based on the shortest distance from the source.

Runtime: O(V.log V + E.log V)



a × b = (x1·10n/2 + x0) · (y1·10n/2 + y0)

Strassen Algorithm

Prim's Algorithm

1) Start with an arbitrary vertex as a sub-tree C.
2) Expand C by adding a vertex having the minimum weight edge of the graph having exactly one end point in C.
3) Update distances from C to adjacent vertices.
4) Continue to grow the tree until C gets all vertices.

binary heap : O(V.log V + E. log V)
Fibonacci heap: O(V. log V + 1) (ac)

Greedy Algorithm

It is used to solve optimi­zation problems
It makes a local optimal choice at each step
Earlier decisions are never undone
Does not always yield the optimal solution

Longest Common Subseq­uence

LCS[i,j] = (1 + LCS[i-­1,j-1]) if s[i] = s[j]
LCS[i,j] = (max(l­cs[­i-1,j] , max[i,­j-1]) if s[i] != s[j]

base case: lcs[i,0] = lcs[0,j] = 0


No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.

          Related Cheat Sheets