Jun Zheng Posts

CSCB63 Data Structure Design and Analysis - Balanced Trees

Why balanced trees?

Binary tree: $O(n)$ for insert, delete and search.

Some better trees:

  • AVL Trees
  • B-trees
  • Splay trees
  • Weight …

AVL Trees

Similar to binary search tree. But also different in a few ways:

  • The height of an AVL tree is $O(log n)$.
  • Each internal node has a balance property equal to -1, 0, 1.
  • Balance value = height of the left subtree - height of the right sub tree.

Balance Property

Have to store the height of sub-trees.

-1 - Right heavy, +1 - Left heavy, 0 - Balanced.

Searching

  • Same as BST

Insertion

After insert, if a node’s balance factor is not -1, 0 or +1, we have to do one single rotation to fix it.

If there is a “bent”, then we have to do double rotation

for (X = parent(Z); X != null; X = parent(Z)) { // Loop (possibly up to the root)
    // BalanceFactor(X) has to be updated:
    if (Z == right_child(X)) { // The right subtree increases
        if (BalanceFactor(X) > 0) { // X is right-heavy
            // ===> the temporary BalanceFactor(X) == +2
            // ===> rebalancing is required.
            G = parent(X); // Save parent of X around rotations
            if (BalanceFactor(Z) < 0)      // Right Left Case     (see figure 5)
                N = rotate_RightLeft(X, Z); // Double rotation: Right(Z) then Left(X)
            else                           // Right Right Case    (see figure 4)
                N = rotate_Left(X, Z);     // Single rotation Left(X)
            // After rotation adapt parent link
        } else {
            if (BalanceFactor(X) < 0) {
                BalanceFactor(X) = 0; // Z’s height increase is absorbed at X.
                break; // Leave the loop
            }
            BalanceFactor(X) = +1;
            Z = X; // Height(Z) increases by 1
            continue;
        }
    } else { // Z == left_child(X): the left subtree increases
        if (BalanceFactor(X) < 0) { // X is left-heavy
            // ===> the temporary BalanceFactor(X) == –2
            // ===> rebalancing is required.
            G = parent(X); // Save parent of X around rotations
            if (BalanceFactor(Z) > 0)      // Left Right Case
                N = rotate_LeftRight(X, Z); // Double rotation: Left(Z) then Right(X)
            else                           // Left Left Case
                N = rotate_Right(X, Z);    // Single rotation Right(X)
            // After rotation adapt parent link
        } else {
            if (BalanceFactor(X) > 0) {
                BalanceFactor(X) = 0; // Z’s height increase is absorbed at X.
                break; // Leave the loop
            }
            BalanceFactor(X) = –1;
            Z = X; // Height(Z) increases by 1
            continue;
        }
    }
    // After a rotation adapt parent link:
    // N is the new root of the rotated subtree
    // Height does not change: Height(N) == old Height(X)
    parent(N) = G;
    if (G != null) {
        if (X == left_child(G))
            left_child(G) = N;
        else
            right_child(G) = N;
        break;
    } else {
        tree->root = N; // N is the new root of the total tree
        break;
    }
    // There is no fall thru, only break; or continue;
}
// Unless loop is left via break, the height of the total tree increases by 1.

Deletion

  • If the key is a leaf, delete and rebalance.

Tree Height

Maximum possible height is $log(n)$, if we have $n$ nodes.

If the height is $h$, let minsize(h) be the minimum number of nodes for an AVL tree of height $h$.

Then

minsize(0) = 0,
minsize(1) = 1,
minsize(h + 2) = 1 + minsize(h + 1) + minsize(h)

minsize(h) = fib(h+2) - 1 (why?)

CSCB63 Data Structure Design and Analysis - Complexity

Useful Manipulations

$log_b(x) = log_b(a) * log_a(x)$

$lim_{n \to \infty} \frac{2^{3n}}{2^n} = lim_{n \to \infty} {2^{2n}} = \infty$

Complexity Table

in Big O of $ln(n)$ lg_2(n) lg_2(n^2) (lg_2(n))^2 n n lg_2 n 2^n 2^{3n}
ln(n) Y Y Y Y Y Y Y Y
log(n) Y Y Y Y Y Y Y Y
log(n^2) Y Y Y Y Y Y Y Y
(lg_2(n))^2 N N N Y Y Y Y Y
n N N N N Y Y Y Y
n log n N N N N N Y Y Y
2^n N N N N N N Y Y
2^{3n} N N N N N N N Y

Complexity Proofs

Prove $n \in O(n lg n)$

$\exists n_0, \exists c, \forall n, n \geq n_0 \implies f(n) \leq c \cdot g(n)$

$n \leq 1n$

$n \leq n \cdot log(n), n \geq 2$

$n \leq c \cdot n \cdot log(n)$

Therefore we have c = 1, and n_0 = 2.

Prove $n log(n) \notin O(n)$

Assume for a contradiction that $nlog(n) \in O(n)$, so

$\exists c, \exists n_0, \forall n, n \geq n_0 \implies nlog(n) \leq c \cdot n$.

$log(n) \leq c$ $n \leq 2^c$

Suppose $n > 2^c$, then $n \geq n_0 \implies n \leq 2^c$. Which is a contradiction.

Prove $6n^5 + n^2 - n^3 \in \Theta(n^5)$

First prove $6n^5 + n^2 - n^3 \in O(n^5)$

$\exists n_0, \exists c, \forall n, n \geq n_0 \implies f(n) \leq c \cdot g(n)$

$6n^5 + n^2 - n^3 \leq 6n^5 + n^2 \leq 6n^5 + n^5 \leq 7n^5$

Let c = 7, and n = 1.

Then prove $6n^5 + n^2 - n^3 \in \Omega(n^5)$

$\exists n_0, \exists c, \forall n, n \geq n_0 \implies f(n) \geq c \cdot g(n)$

$6n^5 + n^2 - n^3 \geq 6n^5 - n^3 \geq 5n^5$

Let c = 5, and n != 1.

Prove $3n^2 - 4n \in \Omega(n^2)$

$3n^2 - 4n \geq bn^2$

$3n - 4 \geq bn$

$3n - bn \geq 4$

$n(3-b) \geq 4$

$n \geq \frac{4}{3-b}$

CSCC69 Operating Systems - Lecture 1

What is an OS

-----------------
Applications
-----------------
Operating System
-----------------
Hardware
  • Provides services
  • Resource manager
  • Control program (protection)

Processes

A process contains

  • An address space
  • Set of OS resources
  • Set of general-purpose registers with current values

What is a Context Switch

CSCB07 Software Design - Intro to Refactoring

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Introduction to refactoring.

CSCB07 Software Design - Decorator Pattern

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Decorator pattern.

CSCB07 Software Design - Pub/Sub Pattern

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Publish and Subscribe Pattern.

CSCB07 Software Design - Iterator and Builder Pattern

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Iterator and Builder design pattern.

CSCB07 Software Design - Unit Testing

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Introduction to JUnit.

CSCB07 Software Design - Polymorphism, Abstract Classes, Interfaces, Liskov, Singleton

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Polymorphism, Abstract Classes, Interfaces, Liskov, Singleton.

CSCB07 Software Design - More Java Memory Model

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

More topics on Java memory model.

CSCB07 Software Design - Software Development Process

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

CRC cards and how to properly develop software with a team.

How I Redesigned IFCAT

A good piece of code should look clean, concise and does what it is supposed to do.

I am not an expert in software engineering, but during my time contributing to IFCAT project, I did find some design flaws, and this is how I fixed them.

This post mainly serves as my personal reference in the future when I try to code Node.js systems. But also is a good read for anyone who is new to programming.

CSCB07 Software Design - Java Memory Model & CRC

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Java memory model and some CRC.

CSCB07 Software Design - Intro to Java

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Introduction to Java programming. This note assumes you are somewhat knows how to program, many obvious details are ignored.

CSCB07 Software Design - SVN

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Basic introduction to version control and how to use SVN.

CSCB36 Theory of Computation - Chapter 6 Predicate Logic

Notes taken for CSCB36 course at UofT, this post is for Chapter 6, Predicate Logic.

CSCB36 Theory of Computation - Chapter 5 Propositional Logic

Notes taken for CSCB36 course at UofT, this post is for Chapter 5, Propositional Logic.

CSCB36 Theory of Computation - Chapter 0

Notes taken for CSCB36 course at UofT, this post is for Chapter 0, mainly talks about sets and fundamental mathematical units.

MATA22 Linear Algebra - Diagonalization

This article is mainly notes I have taken from reading Linear Algebra (Addison-Wesley, 1995) section 5.2. For course MATA22 at UTSC.

CSCB09 Software Tools and Systems Programming - Advanced Topics

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

CSCB09 Software Tools and Systems Programming - Sockets

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

CSCB09 Software Tools and Systems Programming - Signals and Sockets

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

CSCB09 Software Tools and Systems Programming - Pipes / IPC

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

CSCB09 Software Tools and Systems Programming - Processes

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

CSCB09 Software Tools and Systems Programming - Misc IO

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

CSCB09 Software Tools and Systems Programming - Structs, Memory, Strings

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

CSCB09 Software Tools and Systems Programming - Intro to C

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

CSCB09 Software Tools and Systems Programming - Shell Programming

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

CSCB09 Software Tools and Systems Programming - Intro to UNIX

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

MATA22 Linear Algebra - Eigenvalues and Eigenvectors

This article is mainly notes I have taken from reading Linear Algebra (Addison-Wesley, 1995) section 5.1. For course MATA22 at UTSC.

MATA22 Linear Algebra - Determinants of a Square Matrix

This article is mainly notes I have taken from reading Linear Algebra (Addison-Wesley, 1995) section 4.2. For course MATA22 at UTSC.

MATA22 Linear Algebra - Determinants

This article is mainly notes I have taken from reading Linear Algebra (Addison-Wesley, 1995) section 4.1. For course MATA22 at UTSC.