COMP309 Notes

COMP309.md

Recursive Weighted Activity Selection

RWAS(j){
  if (j == 0) return 0
  else if (M[j] != null) return M[j]
  else {
    M[j] = max(w(A[j]) + RWAS(p(j)), RWAS(j-1))
    return M[j]
  }
}

where:

• A is the set of proposed activities sorted by nondecreasing finish time. e.g. f(A[1]) <= F(A[2]) <= ... <= F(A[n])
• w(A[j]) returns the weight of the activity with index j.
• p(j) returns the largest activity index that is smaller than j and doesn't clash with A[j], or else 0.

Huffman Coding

• Calculate the frequency of each unique character.
• Make each frequency a orphan leaf node of a tree.
• While there are more than 1 orphan nodes:
  • Create a new parent node with the two smallest orphan nodes by summing the frequencies.
• Assign the left node a 0 and the right node a 1.
• For each leaf node, follow the path from the root to the leaf to find the code.

Cost of a Huffman Tree = Sum of (length of code * frequency of character)