Crash Consistency


Superblock: Sanity Check:

  1. Check the system size > the number of blocks that have been allocated.
  2. We want to find a suspected superblock.

Free Blocks:

Ensure inodes in use ar emorked in inode bitmaps. Update the inode bitmap if needed.

Inode state: check inode fields for possible corruption

Like check a vaild mode field.

Duplicates: check if two different inodes refer to same block.

Clear One if obviously bad, or give each inode its own copy of block

Bad blocks: bad pointers (like outside of valid range)


Directory checks: Integrity of directory structure

Such as, . and .. must be the first two entries


Transaction structure


Huffman Coding

Total Encoding Length means the total number of bits needed for the “prefix codes”

ABL(Averyage Number of bits per letter) is simply TEL / n (n is the total number of letters).

An optimal prefix codes is that with the smallest ABL.

Definition: A binary tree is full if each internal node has 2 children.

Clamin: The binary tree corresponding to the optimal prefix code is full.


Let K be an optimal prefix code. Assume there is a T such that T is a binary tree corresponding to an optimal prefix code K and T is not full – T has a node u that has exactly one child v.

  1. If u is the root, we can just make a new tree T’ by deleting u and making v the root.
  2. If u is not root, we can make a new tree T
    1. by deleting u and mking v the child of w.

And it is true that, by either case, the number of bits needed decreases, and we can stilll make them intact for each other.

Let K’ be such prefix code. We have ABL(K’) < ABL(K). It is against the fact that K is an optimal prefix code. So, the assumption that there is a T such that T is a binary tree corresponding to an optimal prefix code K and T is not full – T has a node u that has exactly one child v, is false.

But how to find such a tree?

Corollary: There is an optimal binary tree T*, in which the two lowest frequency letters are assigned to leaves that are siblinsg.

Here comes the Huffman Algorithm

function HuffmanEncoding(S, freq)
  if S == {a, b}
    y(a) = 0
    y(b) = 1
    Let y* and z* be the two lowest frequency letters
    Form a new alphabet S' = S - (y*, z*) + w, with freq(w) = freq(y*) + freq(z*)
    y' = HuffmanEncoding(S', freq)
    Extend y' to a prefix code y for S as follows:
      y(y*) = y'(w).append(0)
      y(z*) = y'(w).append(1)
  return y
Algorithm Design, Analysis & Complexity Uncategorized

CSC373 Goals

My goal is to master the following standard algorithm design patterns

Greedy Strategies

Dynamic Programming

Summary to some concepts after reading CLRS chapter 15

Graph Algorithms

Network Flow

Linear Programming

Approximation Algorithms


You Can Now Use Your Face to Play the Classical Snake Game

Have you ever been addicted to Snake?

Now, with the help of a TensorFlow model called PoseNet, you can get a totally different experience with this classical game. That’s because:

You can now use your face to control the snake!

Have a try here:


  1. To the PoseNet team who makes the core feature of my face control snake game possible.
  2. To the unknown person who shares his / her snake game so that I could just modify the codes to make my game.