# Jun Zheng Posts

### Word Break II

The main optimization for this is the memo. Because the problem is recursive, we simply remember the result of sub-problems.

Actual problem can be found here.

class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
self.memo = {}
return self.recursiveSolution(0, len(s), s, set(wordDict))

def recursiveSolution(self, start, end, s, wordSet):
# Find all valid prefixes
if start in self.memo:
return self.memo[start]
result = []
for i in range(start, end + 1):
if s[start:i] in wordSet:
# print(str(i) + " " + str(len(s)) + " " + s + " " + s[i:] + " " + s[:i])
if i == end:
result.append(s[start:])
else:
subResult = self.recursiveSolution(i, end, s, wordSet)
for sub in subResult:
result.append(s[start:i] + ' ' + sub)
self.memo[start] = result
return result



### Recover From Preorder Traversal

The actual question can be found here

Coded in less than 30 minutes, don’t expect it to be very good, I might optimize this later.

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode recoverFromPreorder(String S) {
// This is a recursive solution
if(S.length() == 0) return null;
if(!S.contains("-")) {
return new TreeNode(Integer.parseInt(S));
} else {
int numericStartingIndex = 0;
String rootVal = "";
for(int i = 0; i < S.length(); i++) {
if(S.charAt(i) == '-') {
numericStartingIndex = i;
break;
} else {
rootVal += S.charAt(i);
}
}
TreeNode node = new TreeNode(Integer.parseInt(rootVal));

boolean foundDepthOne = false;
int currDepth = 0;
boolean atRight = false;
String left = "";
String right = "";
for(int i = numericStartingIndex; i < S.length(); i++) {
if(S.charAt(i) == '-') {
currDepth++;
} else {
char value = S.charAt(i);
// If this depth is the same or less than max depth
// then we have to switch from left to right
if(currDepth == 1) {
if(!foundDepthOne) {
foundDepthOne = true;
} else {
atRight = true;
}
}
if(atRight) {
right = addNodeToString(right, value, currDepth - 1);
} else {
left = addNodeToString(left, value, currDepth - 1);
}
currDepth = 0;
}
}
node.left = recoverFromPreorder(left);
node.right = recoverFromPreorder(right);
return node;
}
}

public String addNodeToString(String curr, char value, int depth) {
for(int i = 0; i < depth; i++) {
curr += '-';
}
curr += value;
return curr;
}
}


Routers

### CSCD58 Computer Networks - Internet Protocol

Introduction to ethernet and IP

### CSCB63 Data Structure Design and Analysis - Fibonacci Heaps

Basic introduction to fibonacci heaps and some comparson with regular heaps.

## Overview

Threads are basically mini-processes within a process. However they share the same address space.

Creating threads are much faster than creating processes, in some systems, this can be 10x to 100x faster.

Think of threads as JS event loops, basically it.

The classic thread model basically have all threads with their own stack and own PC.

Everything else is shared. The software library will take care of scheduling.

Some useful calls:

If implemented in user space, then the library have to take care of scheduling and switching. However if hardware do support store/load registers, this operation can be done very quickly, which is much faster than trapping to kernel.

And since everything is local, no context switch is needed, no kernel calls, it is very fast. Each process can also have its own scheduling algorithm.

### Drawbacks

Thread cannot make blocking kernel calls, since that will halt all threads. Sometimes library will wrap the actual system call, but it is not really that nice to do.

Another issue is page fault. Which will be discussed in memory management (basically blocking the process because it needs to read instructions from disk).

In user space thread implementations, there is no clock interrupts. So a thread must give up the CPU before another thread can be run.

## Overview

Processes allows computers to do multiple things at once.

In multiprogramming system, CPU switches from process to process very quickly, make it seem that it is running them concurrently. This is usually called pseudoparallelism, in contrast to real-parallelism with multiprocessor.

In any given instant, only one process is running on one CPU.

Context Switch: a context switch is the process of storing the state of a process or of a thread so that it can be restored and resumed later.

## Drawbacks

• Programs cannot have assumption of timing. Say if you know 1 loop takes 0.01 millisec, you loop 1000 times to get 10 millisec. However, while in the loop, OS might already switched to another process.

## Program vs Process

An analogy:

• Recepe: Program
• Ingredients: Input Data
• Process: Reading the recepe, getting ingredients and baking the cake.

Now the guy’s son runs into room and says he has been stung by a bee. The guy records where he was in the recipe, gets first aid book and following that. After first aid has been done, he goes back to cooking. This is basically how OS switches processes.

In real OS this is called scheduling. And if a programming is running twice, it is two processes.

## Process Creation

There are 4 principal events that cause processes to be created:

• System initialization
• Execution of a process creation system call by a running process
• A user request to create a new process
• Initiation of a batch job

There are 2 main types: foreground and background (daemons).

Technically, for all these cases, a new process is created by an existing process. In UNIX, only fork can be used to create new processes. After fork, the child may change its memory image using execve. Reason is so we can redirect IO before execve.

Parent and child have different address space. However they may share text.

## Process Termination

There are 4 ways for a process to terminate.

• Normal exit
• Error exit
• Fatal error
• Killed by another process

## Process Hierarchies

In UNIX, a process and all of its children form a process group. When a user sends a signal from the keyboard, all members are notified.

In UNIX, all processes belong to a single tree, which init at the root. Processes cannot change parent (unless parent is killed by some reason).

## Process States

There are 3 main states:

• Running: Actually using the CPU
• Ready: Can run, but temp stopped for another process to run
• Blocked: Cannot run until some external event happens

In UNIX, a process is automatically blocked if trying to read from an empty pipe.

## Process Implementation

People use process table (PCB) to implement processes. Usually a table includes:

• State
• Memory allocation
• Open files
• Scheduling info
• Registers
• etc.

### Interrupt Vector

Usually located at the bottom of the memory, when an interrupt happens, the hardware pushes process info onto stack, and jumps to interrupt vector. Then the interrupt procedure runs.

All interrupts start by saving registers, this is usually done in assembly since C cannot access these information. Then the access is handed over to interrupt handler (stack is also reset).

After the handler is done, the control is back to assembly to load the registers again.

Overview of the basic procedures are listed below:

• Hardware stacks basic program information
• Hardware loads PC from IV.
• Assembly saves registers
• Assembly set up new stack.
• Runs C interrupt service.
• Scheduler decides which to run next.
• C procedure returns to assembly code.
• Assembly runs new process.

## Why balanced trees?

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

### CSCB63 Data Structure Design and Analysis - Complexity

Notes takes for complexity module of CSCB63 course at UTSC.

## Ordered Dictionary

Finite map from keys to values, assume keys are comparable.

Some operations supported:

• insert(k, v)
• lookup(k)
• delete(k)

Ordered set is the same, just with no values, only keys.

If we implement this using a binary tree, lookup can be very slow if we insert all data within sorted order. We will learn how to improve this.

## Hashed Dictionary / Table

Finite map from keys to values, assume keys can be hashed.

Same operations as ordered dictionaries.

Hashed set is the same, just with no values, only keys.

Hash table is an array of size $L$, put key $k$ in $A[h(k) \% L]$

We will learn how to choose the hash function, and what to do if there is a collision.

## Priority Queue

Collection of priority-job pairs, priority is comparable.

Operations supported:

• insert(p, j)
• max()
• extract-max()
• increase-priority(j, k)

Using heap to implement this can be super fast and easy.

## Graph

Includes vertices and edges.

Will learn how to compute reachability, cycles, connected components, and spanning tree/forest.

## Disjoint Sets

Collection of disjoint sets.

Operations supported:

• make-set(x)
• union(S, S’)
• find(x)

If we implement this using trees, amortized time can be almost constant.

## Amortized Time Analysis

Some operations might be slow in the worst case, but rarely happens. We might not be interesting in only the worst case.

$at = \frac{\text{total time of calls}}{\# calls}$

## Operating System Boot Process

This is just a basic description of how a Pentium computer boots.

• First the BIOS is loaded from motherboard RAM.
• BIOS checks how much RAM is installed.
• Other devices like keyboard / mouse are checked.
• Then checks ISA and PCI busses.
• BIOS then determines the boot device listed in CMOS memory.
• Usually floppy -> CD -> HDD
• Examines the partition table at end of the boot sector, to determine which partition to use.

### 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.