Kruskal’s Algorithm

It is a greedy algorithm that gives an optimal solution for a minimum spanning tree for a connected weighted graph.

Steps to solve Kruskal’s Algorithm:

  1. Sort graph edges in nondecreasing order (from least to greatest).
  2. Then, starting with an empty subgraph, it scans the sorted list which adds the next edge on the list to the current subgraph IF it does NOT create a cycle. If the edge does create a cycle, simply just skip it.
  3. Continue to add all edges to the subgraph until all vertices have been reached.

Recurrences

Master Theorem: If need to divide something in F(n), then use this theorem.

$F(n) = AF(n/B) + n^C$

Cases to consider: Calculate $B^C$ to compare to A.

If:

  1. $B^C > A$, then $F(n) = \theta(n^C)$
  2. $B^C = A$, then $F(n) = \theta(n^C logn)$
  3. $B^C < A$, then $F(n) = \theta(n^{log_B A})$

Think > = < (squinting face) n^c, n^c logn, n^(log_B A)

Use when you have one recursive call and is in the form F(n) = AF(n/B) + n^C

Generalized Master Theorem: Requires you to change letters into greek letters. Formula is as follows: $F(n) = \alpha F(\beta n) + n ^ \gamma$ where: $\alpha = $ A $\beta = $ 1/B $\gamma = $ C

Cases to consider: Let $T = \sum^{k}_{i=1}\alpha_i\beta_i^\gamma$

If:

  1. $T > 1$, then find a constant $P$ such that $\sum^{k}_{i=1}\alpha_i\beta_i^P = 1$, then $F(n) = \theta(n^P)$
  2. $T = 1$, then $F(n) = \theta(n^{\gamma}logn)$
  3. $T < 1$, then $F(n) = \theta(n^{\gamma})$

Use when you more than one recursive call.

Anti-Derivative: Steps:

  1. Try isolating n on the right side by itself by subtracting F(n - k).
  2. After that, divide both sides by k.
  3. Take the integral of the right side of the equation to obtain the answer.

Use when you have one recursive call and don’t have to divide by anything in parameter.

Substitution: In term sof substitution, if a square root is present in the parameter of F(n), then $G(m/2) = F(\sqrt(n))$

Example: $F(n) = F(\sqrt n) + 1$

Use when parameter of F(n) does not have anything divided

Treap

It is a combination of trees and heaps. It maintains the following properties:

  1. Keys (letters) are organized as in a BST. Left child node is less than parent; right child node is greater than parent.
  2. Priorities (numbers) are organized as in a heap. Parent node is greater than its children.

NOTE: TREAPS NEED TO BE BALANCED, SIMILAR TO AN AVL TREE.

Complex Numbers

Square Root of complex numbers: $\sqrt{z} = \pm(\sqrt{\frac{\sqrt{a^2+b^2}+a}{2}} + \sqrt{\frac{\sqrt{a^2+b^2}-a}{2}})$ if b > 0

$\sqrt{z} = \pm(\sqrt{\frac{\sqrt{a^2+b^2}+a}{2}} - \sqrt{\frac{\sqrt{a^2+b^2}-a}{2}})$ if b < 0

For square root, it’s basically sqrt( (modulus+a) / 2 ) pm sqrt( (modulus-a) / 2 )

Roots of unity formula: $\cos{\frac{2k\pi}{n}} + i\sin{\frac{2k\pi}{n}}$ where k is from 0 to n-1.

Modulus formula: $|z| = \sqrt{a^2+b^2}$

Hash Tables

Hashing distributes keys among a one-dimensional array called a hash table via a hash function. Function assigns an integer between 0 and m-1 called a hash address to a key.

Calculating expected number of cells w/ exactly k items:

$\frac{m(\frac{n}{m})^k}{k!e^{\frac{n}{m}}}$ where m is the table size, n is the number of data items, and k is the items per cell

Memoization

It is used to speed up programs by removing repetitive computation of results. It avoids repeated calls to functions that produces the same output.

Example of memoization: Computing the Fibonacci Sequence. Once each function has reached its base case, go back up and see

Dynamic Programming

Technique where a problem is broken down into smaller sub-problems. Each sub-problem is optimized to find the overall solution.

Once each sub-problem has computed a solution, store the results of those sub-problems so the function does not have to re-compute them when they are needed later (this is why memoization is important).

Can think of it as an optimization technique over recursion.

Loop Invariance

Steps to loop invariance:

Huffman Encoding

In Huffman Encoding, the codons for the different symbols of a message may be written consecutively without spaces.

Steps to Huffman Encoding:

  1. Place the frequencies from least to greatest.
  2. Afterward, add the two least frequencies together. Keep doing this until you are left one a single number.
  3. Assign a weight of 0 to the left branch of each root; assign a wieght of 1 to the right branch of each root.

Calculating Addresses

2-D Array: In Row-major, the formula is $A[i][j] = BaseAddress + n*(i*q+j)$

In Column-major, the formula is $A[i][j] = BaseAddress + n*(i + (j*p))$

3-D Array: In Row-major, the formula is $A[i][j][k] = BaseAddress + n*(iqr + (j*r) + k$

In Column-major, the formula is $A[i][j][k] = BaseAddress + n*((pqk)+(p*j)+i)$

Sparse Array

A sparse array uses a search structure to search through a set of memos ( each memo will be an ordered pair(i,x) where A[i] = x ). If i is not mapped to anything, then A[i] = 0. Fetch will use some find function and store will use an insert function.

Difference between asymptotic time complexity and asymptotic complexity:

Asymptotic complexity wants the overall/general complexity of F(n). For example:

$F(n) = 4F(n/2) + n^2$ would yield $F(n) = \theta(n^2 logn)$

Asymptotic time complexity does not want the overall/general complexity of F(n) but rather only the recurrence (group of functions being called). For example:

$F(n) = 4F(n/2) + 1$ would yield $F(n) = \theta(n^2)$ via the Master Theorem