• Steven Hé (Sīchàng)
  • Link farm
    • 2025 Spring News
    • 2024 Fall News

Steven Hé (Sīchàng)

Hello there, Steven here:

• Systems programmer, Rustacean, Pythonista, Elixirist, Vimmer.
• 1st-year Computer Science Ph.D. student in the Networked Systems Lab (NSL), University of Southern California (USC).
  • Advisor: Harsha Madhyastha.
  • Interests: the Web, Networking, SE, PL, HPC.
• For experiences, publications, etc., please see the CV linked below.

Link farm

Press s to search!

2025 Spring News

• (2025-01-09) 🌐🤖 I sketched the DeGenTWeb project to detect and study LLM-generated text content on the Web.

2024 Fall News

• (2024-12-13) 🤖💀 I posted a survey of generative AI problems and countermeasurements, which showed many business, cryptography, and computer vision problems remain in this field.

• (2024-11-27) ⭕💀 We paused the JSphere project that classifies the use of JavaScript on the Web by browser API calls. Preliminary results are in a report for a course and a colorful poster.

  Feel free to take over this project.

• (2024-11-05) 💬🌐 I recorded a retroactive presentation for my RPSLyzer talk at IMC ’24.

• (2024-11-05) 💬🌐 I presented the RPSLyzer paper at IMC ’24 in Madrid and met nice people at the conference. The conference has no recordings, unfortunately.

• (2024-09-15) 🐍🥲 My Battlesnake “TinyViTMCTS” will go down on the leaderboard because Duke is shutting down the VM it runs on.

• (2024-09-12) 📖🌐 I posted the camera-ready PDF version of the RPSLyzer paper. Download it from the Internet Route Verification repository’s Releases.

• (2024-08-27) 📖💵 The IMC Student Travel Grant committee generously awarded me funds, so that I can go present my paper at the conference.

• (2024-08-23) 🏠🔬 I moved to Los Angeles and joined the USC Networked Systems Lab as a Ph.D. student, working with Professor Harsha V. Madhyastha.

• (2024-07-31) 📖🎉 ACM Internet Measurement Conference (IMC) 2024 accepted our paper, RPSLyzer: Characterization and Verification of Policies in Internet Routing Registries, by Sichang He, Italo Cunha, and Ethan Katz-Bassett. We will post drafts in the Internet Route Verification repository.

• (2024-07-24) 🌐⭕ I sketched the JSphere project to study the overuse of JavaScript in websites.

• (2024-07-03) 🐙🇬🇧 I started developing the Natural Syntax Language Server to highlight part-of-speech for ease of reading.

Older news

To comment on the news, please go to the news page.

• About
  • Contact
  • Name
    • Name pronunciation

About

Contact

• Email: See the address in my CV. I get notifications and reply.
  • I block whoever sends spam immediately.
  • Ping me if I do not reply in three days.
• GitHub: Ping me for code-related discussions. I get emails.

Name

The legal name and name used in publications is “Sichang He” (何思畅, or 何思暢). Steven is the preferred English name.

Name pronunciation

Google Translate pronounces it correctly (Click Listen). Serializing it into English is impossible; the best you can get is H-err? Sii↑ chung↓.

• 2025 Spring News

2025 Spring News

• (2025-01-09) 🌐🤖 I sketched the DeGenTWeb project to detect and study LLM-generated text content on the Web.

News | Steven Hé (Sīchàng)

• 2024 Fall News

2024 Fall News

• (2024-12-13) 🤖💀 I posted a survey of generative AI problems and countermeasurements, which showed many business, cryptography, and computer vision problems remain in this field.

• (2024-11-27) ⭕💀 We paused the JSphere project that classifies the use of JavaScript on the Web by browser API calls. Preliminary results are in a report for a course and a colorful poster.

  Feel free to take over this project.

• (2024-11-05) 💬🌐 I recorded a retroactive presentation for my RPSLyzer talk at IMC ’24.

• (2024-11-05) 💬🌐 I presented the RPSLyzer paper at IMC ’24 in Madrid and met nice people at the conference. The conference has no recordings, unfortunately.

• (2024-09-15) 🐍🥲 My Battlesnake “TinyViTMCTS” will go down on the leaderboard because Duke is shutting down the VM it runs on.

• (2024-09-12) 📖🌐 I posted the camera-ready PDF version of the RPSLyzer paper. Download it from the Internet Route Verification repository’s Releases.

• (2024-08-27) 📖💵 The IMC Student Travel Grant committee generously awarded me funds, so that I can go present my paper at the conference.

• (2024-08-23) 🏠🔬 I moved to Los Angeles and joined the USC Networked Systems Lab as a Ph.D. student, working with Professor Harsha V. Madhyastha.

• (2024-07-31) 📖🎉 ACM Internet Measurement Conference (IMC) 2024 accepted our paper, RPSLyzer: Characterization and Verification of Policies in Internet Routing Registries, by Sichang He, Italo Cunha, and Ethan Katz-Bassett. We will post drafts in the Internet Route Verification repository.

• (2024-07-24) 🌐⭕ I sketched the JSphere project to study the overuse of JavaScript in websites.

• (2024-07-03) 🐙🇬🇧 I started developing the Natural Syntax Language Server to highlight part-of-speech for ease of reading.

News | Steven Hé (Sīchàng)

• 2024 Spring News

2024 Spring News

• (2024-03-15) 💬🌻 I gave $\frac{1}{3}$ of a talk and presented a poster at Flower AI Summit 2024. The talk is FedCampus: A Privacy-preserving Smart Campus by Bing Luo and Sichang He.
• (2024-02-13) 🎬📱 IEEE INFOCOM 2024 accepted our demo paper, FedKit: Enabling Cross-Platform Federated Learning for Android and iOS, by Sichang He, Beilong Tang, Boyan Zhang, Jiaqi Shao, Xiaomin Ouyang, Daniel Nata Nugraha, and Bing Luo. The demo video is on YouTube.

News | Steven Hé (Sīchàng)

• Steven Hé (Sīchàng)’s Notes

Steven Hé (Sīchàng)’s Notes

• Android

Android

run android studio emulator without android studio:

~/Library/Android/sdk/emulator/emulator -avd <DEVICE_NAME>

• Automation Software

Automation Software

• Chatbot Prompt

Chatbot Prompt

general requirements:

I am a computer scientist working on systems. Follow Clear Writing Principles, avoid any repetition, be complete and succinct.

summarize paper w/ focus on FOCUS

What does this paper talk about in terms of FOCUS? Try your best to summarize every single aspect mentioned in the paper. For every single point you elaborate, always quote the exact original related phrase, sentence, or paragraph.

general requirements (old):

Requirements R: be professional and maximally succinct. Prefer verb over noun, adjective over adverb, active tense over passive tense. Avoid fluff or self-judgements. Do not lose any information. Do not praise or repeat any given content. Keep the original language, style, and meaning as much as possible. Make minimal changes for improvement.

To remind the bot the requirements:

Repeat Requirements R verbatim.

point out problem but not revise:

Criticize my draft and list all the problems. For each problem separately, quote my original words, reason about the problem, provide suggestions, and provide suggested change.

compress text:

Revise this part to make it more succinct, without loosing any information. Stay close to the original language and make minimal changes.

refine prompt based on result I do not like:

I do not like how you PROBLEM.
What could I have said instead so that you would never ever say that?

• Command-Line Utilities

Command-Line Utilities

wrap lines to a maximum width of 80 in FILE

fold -w 80 -s FILE

extract all images from PDF

pdfimages -all PDF_FILE "$(pwd)/"

convert PDF to HTML and preserve layout

docker run -t --rm -v $(pwd):/pdf -w /pdf pdf2htmlex/pdf2htmlex:0.18.8.rc2-master-20200820-alpine-3.12.0-x86_64 PDF_FILE

• Hammerspoon

Hammerspoon

add stuff: open config, type in LaTeX, save, reload config

bind function to hotkey

hs.hotkey.bind({"functionKey", …}, "key",…, function()
  …
end)

functionKey: cmd alt ctrl
key: X \\ Left
the {} must stay even if it`s empty

show alert message

hs.alert.show("message")

generate system notification with title and content

hs.notify.new({title="title", informativeText="content"}):send()

define the current window as win

local win = hs.window.focusedWindow()

define win’s window frame as f

local f = win:frame()

position of f is (f.x, f.y) its width and height f.w, f.h

define the screen win at as screen

local screen = win:screen()

define screen’s screen frame as max

local max = screen:frame()

update the frame of win as f

win:setFrame(f)

hs.pathwatcher.new(.....):start()

reload config

hs.reload()

automatically reload config

function reloadConfig(files)
    doReload = false
    for _,file in pairs(files) do
        if file:sub(-4) == ".lua" then
            doReload = true
        end
    end
    if doReload then
        hs.reload()
    end
end
myWatcher = hs.pathwatcher.new(os.getenv("HOME") .. "/.hammerspoon/", reloadConfig):start()
hs.alert.show("Config loaded")

get the home direction of the system

os.getenv("HOME")

connect string to path

..

call function whenever changes in direction

hs.pathwatcher.new("direction", function):start()

• Browsers
  • clear browser cache
    • browser DNS cache

Browsers

clear browser cache

browser DNS cache

Chrome:

chrome://net-internals/#dns

Firefox:

about:networking#dns

• Computer Science

Computer Science

• Discrete Mathematics for Computer Science
  • proof by induction

Discrete Mathematics for Computer Science

proof by induction

steps with example

• variable $n$
• property $P(n)$
• base case $P(0)$
• induction hypothesis
  • weak induction
    assume $P(n-1)$ is true
  • strong induction
    assume $P(k)$ is true $\forall k<n$
• induction step
  induction hypothesis $\Rightarrow P(n)$ is true

• Machine Learning
  • general problem format
  • machine learning is about building a function
    • simplification using feature vector
  • loss
    • zero-one loss
    • quadratic loss
  • empirical risk
  • three types of machine learning problems
    • classification problem
      • all possible training set
      • signature of machine learning function $\lambda$
      • classifier $h$ define a partition of $X$
    • regression problem
    • clustering problem
  • supervised/ unsupervised machine learning
• polynomial data fitting
  • interpolation in polynomial data fitting
• k-nearest neighbors predictor
  • Voronoi diagram
• gradient descent
  • stochastic gradient descent (SGD)
  • step size
  • subgradient
• logistic-regression classifier
  • score function for linear boundary
  • signed distance to hyperplane
  • logistic function
    • softmax function
  • cross entropy loss for binary classification
    • cross entropy loss for $K$-class case
• support vector machine (SVM)
  • binary support vector machine
    • separating hyperplane for binary support vector machine
    • hinge loss
      • empirical risk of binary support vector machine
  • soft linear support vector machine
    • subgradient of hinge function
  • support vector machine with kernel
    • representer theorem
    • support vector
    • kernel for support vector machine

Machine Learning

general problem format

given input $A$, want output $y\in Y$

$$f:A\to Y,y=f(a)\in Y\text{for }a\in A$$

• traditional approach
  hand-craft the function $f$
• machine learning
  build another function $\lambda$ and use it to generate an approximation $f$

machine learning is about building a function

• training data $L=\{(a_1,y_1),\cdots ,(a_n,y_n)\}$
• class of allowed function $\mathcal{F}$

use a predefined algorithm to compute $f\in \mathcal{F}$ with the goal:

$$y\approx f(x)$$

simplification using feature vector

convert input into a 1d vector, making machine learning generally applicable

• feature vector $\vec{x}\in X\subseteq {\mathbb{R}}^d$
• $\varphi :A\to X$
• training set $T_a=\{({\vec{x}}_1,y_1),\cdots ,({\vec{x}}_n,y_n)\}\subset {\mathbb{R}}^d\times {\mathbb{R}}^e$
• hypothesis space $\mathcal{H}$
• $Y\subseteq {\mathbb{R}}^e$

predefined algorithm produce $h\in \mathcal{H}$ so that

$$f(a)=h(\varphi (a))$$

loss

estimation of the error of $h$

$$\begin{gathered} \ell :Y\times Y\to {\mathbb{R}}^{+} \\ \ell (y_n,h({\vec{x}}_n)) \end{gathered}$$

zero-one loss

$$\ell (y,\hat{y}):=\{\begin{array}{ll}0& y=\hat{y}\\ 1& \text{otherwise}\end{array}$$

quadratic loss

$$\ell (y,\hat{y}):=(y-\hat{y}{)}^2$$

empirical risk

average lost based on the training set

$$L_T(h):=\frac{1}{N}\sum _{n=1}^N\ell (y_n,h({\vec{x}}_n))$$

three types of machine learning problems

classification problem

label given data

• classifier (predictor) $h$: the produced function

all possible training set

$$\mathcal{T}:=2^{X\times Y}$$

signature of machine learning function $\lambda$

$$\lambda :\mathcal{T}\to \mathcal{H}\text{such that}\lambda (T)=h$$

• $\lambda$ learn (or train) classifier $h$ from training set $T$
• inference: apply classifier $h$ on any data
  • testing: apply classifier $h$ on unseen data

classifier $h$ define a partition of $X$

regression problem

given data, return a vector

clustering problem

group given data

supervised/ unsupervised machine learning

supervised learning: classification, regression

unsupervised learning: clustering

polynomial data fitting

not machine learning but similar

$$\begin{gathered} A\vec{c}=\vec{b} \\ A=\left[\begin{array}{cccc}1& x_1& \cdots & x_1^k\\ ⋮& ⋮& & ⋮\\ 1& x_N& \cdots & x_N^k\end{array}\right] \\ \vec{b}=\left[\begin{array}{c}{y}_1\\ ⋮\\ y_N\end{array}\right] \\ \hat{\vec{c}}\in \underset{\vec{c}}{\mathrm{argmin}}\Vert A\vec{c}=\vec{b}{\Vert }^2 \end{gathered}$$

• number of monomial $m(d,k)=\left(\genfrac{}{}{0ex}{}{d+k}{k}\right)$

interpolation in polynomial data fitting

achieve $0$ loss

• $k=N-1\Rightarrow$ always interpolate
• overfitting

k-nearest neighbors predictor

remember the whole training set

$$T=\{({\vec{x}}_i,y_i)|i=1,\cdots ,N\}$$

return average of $y_n$s corresponding to the $k$ closest ${\vec{x}}_n$s to $\vec{x}$

• useful for both classification and regression
• smaller $k$ results in worse overfitting
• good interpolation and poor extrapolation

Voronoi diagram

gradient descent

stochastic gradient descent (SGD)

group training set randomly into mini-batch, use gradient from each mini-batch to descent

• mini-step are in the right direction on average
• epoch: using all data once

step size

• fixed

• decreasing

• momentum

  $${\vec{v}}_{k+1}={\mu }_k{\vec{v}}_k-{\alpha }_k\nabla f({\vec{z}}_k)$$

• line search

subgradient

logistic-regression classifier

• score-based

score function for linear boundary

$$s(\vec{x})=\sigma (a(\vec{x}))=\sigma (c+{\vec{u}}^T\vec{x})$$

signed distance to hyperplane

hyperplane $\chi \in {\mathbb{R}}^d$

$$b+{\vec{w}}^T\vec{x}=0\vec{w}\ne \vec{0}$$

• $\vec{w}$ is perpendicular to $\chi$

• distance of $\chi$ from origin

  $$\beta :=\frac{|b|}{\Vert \vec{w}\Vert }$$

• signed distance of $\vec{x}$ from $\chi$

  $$\Delta (\vec{x}):=\frac{b+{\vec{w}}^T\vec{x}}{\Vert \vec{w}\Vert }$$

logistic function

$$f(\Delta ):=\frac{1}{1+e^{-\Delta }}$$

then the score function is

$$s(\vec{x}):=f(a(\vec{x}))=f(b+{\vec{w}}^T\vec{x})=\frac{1}{1+e^{-b-{\vec{w}}^T\vec{x}}}$$

• activation $a(\vec{x})$ is signed distance scaled

softmax function

softmax function in activation $\vec{a}$

$$\begin{gathered} \vec{s}(\vec{x})=\left[\begin{array}{c}{s}_1(\vec{a})\\ ⋮\\ s_K(\vec{a})\end{array}\right] \\ \vec{a}(\vec{x})=\left[\begin{array}{c}{a}_1(\vec{x})\\ ⋮\\ a_K(\vec{x})\end{array}\right] \\ {s}_k(\vec{x})=f(a_k(\vec{x}))=\frac{e^{a_k}(\vec{x})}{{\sum }_{j=1}^K{e}^{a_j}(\vec{x})} \end{gathered}$$

cross entropy loss for binary classification

cross entropy loss of assigning score $p$ to point whose true label is $y$

$$\begin{gathered} \ell (y,p):=\{\begin{array}{ll}-\log p& y=1\\ -\log (1-p)& y=0\end{array} \\ =-y\log p-(1-y)\log (1-p) \end{gathered}$$

• differentiable so we can do gradient descent
• base of $\log$ does not matter
• resulting risk function is weakly convex

cross entropy loss for $K$-class case

$$\ell (y,\vec{p})=-\log p_y=-\sum _{k=1}^K{q}_k\log p_k$$

• true label $y$
• prediction $\vec{p}$
• one hot encoding $\vec{q}$ of $y$

support vector machine (SVM)

binary support vector machine

separating hyperplane for binary support vector machine

$$\begin{gathered} {\vec{n}}^T\vec{x}+c=0 \\ \vec{n}\in {\mathbb{R}}^d,\Vert \vec{n}\Vert =1,c\in \mathbb{R} \end{gathered}$$

• decision rule

  $$\begin{gathered} h(\vec{x})=\text{sign}({\vec{n}}^T\vec{x}+c) \\ \Rightarrow y({\vec{n}}^T\vec{x}+c)\ge 0 \end{gathered}$$

• margin for $(\vec{x},y)$ with parameter $\vec{v}=(\vec{n},c)$

  $${\mu }_{\vec{v}}(\vec{x},y):=y({\vec{n}}^T\vec{x}+c)$$

  • margin ${\mu }_{\vec{v}}(T)$ of training set

    $${\mu }_{\vec{v}}(T):=\underset{(\vec{x},y)\in T}{\min }{\mu }_{\vec{v}}(\vec{x},y)$$

  • linearly separable if ${\mu }_{\vec{v}}(T)>0$

hinge loss

reference margin ${\mu }^{\ast }>0$

$$\begin{gathered} {\ell }_{\vec{v}}(\vec{x},y):=\frac{1}{\mu \ast }\max \{0,{\mu }^{\ast }-{\mu }_{\vec{v}}(\vec{x},y)\} \\ =\max \{0,1-y({\vec{w}}^T\vec{x}+b)\} \end{gathered}$$

where

$$\vec{w}:=\frac{\vec{n}}{{\mu }^{\ast }},b=\frac{c}{{\mu }^{\ast }}$$

• separating hyperplane ${\vec{w}}^T\vec{x}+b=0$

empirical risk of binary support vector machine

$$L_T(\vec{w},b):=\frac{1}{2}\Vert \vec{w}{\Vert }^2+\frac{C_0}{N}\sum _{n=1}^N{\ell }_{(\vec{w},b)}({\vec{x}}_n,y_n)$$

• bigger $C_0\Rightarrow$ smaller ${\mu }^{\ast }$

soft linear support vector machine

$$({\vec{w}}^{\ast },b^{\ast })={\text{ERM}}_T(\vec{w},b)$$

subgradient of hinge function

$$\begin{gathered} \rho (z)=\max \{0,z\} \\ {\rho }^{\prime }(z)=\{\begin{array}{ll}1& z>0\\ 0& \text{otherwise}\end{array} \end{gathered}$$

support vector machine with kernel

representer theorem

$\forall$ loss function in the form

$$L^T(\vec{w},b)=R(\Vert \vec{w}\Vert )+S({\vec{w}}^T{\vec{x}}_1+b,\cdots ,{\vec{w}}^T{\vec{x}}_N+b)$$

where $R:{\mathbb{R}}_{+}\to \mathbb{R}$ increasing, $S:{\mathbb{R}}^N\to \mathbb{R}$,

$\exists {\beta }_1,\cdots {\beta }_N$ s.t.

$${\vec{w}}^{\ast }=\sum _{n=1}^N{\beta }_n{\vec{x}}_n$$

• proof: by writing

  $${\vec{w}}^{\ast }=\sum _{n=1}^N{\beta }_n{\vec{x}}_n+\vec{u}\text{for some}\vec{u}\in \text{span}\{{\vec{x}}_i\}$$

  and proving $\vec{u}=\vec{0}$ by contradiction

support vector

sample that are misclassified or classified correctly with a margin not larger than ${\mu }^{\ast }$

only support vector contribute to ${\vec{w}}^{\ast },b^{\ast }$

$$\begin{gathered} h(\vec{x})=\text{sign}\left(\sum _{n=1}^N{\beta }_n{\vec{x}}_n^T\vec{x}+b^{\ast }\right) \\ {L}^T(\vec{w},b)=\frac{1}{2}\sum _{n=1}^N{\beta }_m{\beta }_n{\vec{x}}_n^T{\vec{x}}_n+\frac{C_0}{N}\sum _{n=1}^N\rho \left(1-y_n\left(\sum _{n=1}^N{\beta }_m{\vec{x}}_n^T{\vec{x}}_n+b\right)\right) \end{gathered}$$

kernel for support vector machine

$$\begin{gathered} h(\vec{x})=\text{sign}\left(\sum _{n=1}^N{\beta }_{n}K({\vec{x}}_n,\vec{x})+b^{\ast }\right) \\ {L}^T(\vec{w},b)=\frac{1}{2}\sum _{n=1}^N{\beta }_m{\beta }_{n}K({\vec{x}}_n,{\vec{x}}_n)+\frac{C_0}{N}\sum _{n=1}^N\rho \left(1-y_n\left(\sum _{n=1}^N{\beta }_{m}K({\vec{x}}_n,{\vec{x}}_n)+b\right)\right) \end{gathered}$$

where kernel $K$

$$K(\vec{x},\vec{\xi }):=\vec{\phi }(\vec{x})\vec{\phi }(\vec{\xi })$$

for some $\vec{\phi }$

• $K(\vec{x},\vec{\xi })=K(\vec{\xi },\vec{x})$
• $K^2(\vec{x},\vec{\xi })\le K(\vec{x},\vec{x})K(\vec{\xi },\vec{\xi })$

$K$ is a kernel of $\{{\vec{x}}_i\}$

• $\iff C\ge 0$ where $C_{ij}=K({\vec{x}}_i,{\vec{x}}_j)$

• $\iff$ Mercer’s condition: $\forall f:{\mathbb{R}}^d\to \mathbb{R}$ s.t.

  $${\int }_{{\mathbb{R}}^d}f(\vec{x})d\vec{x}$$

  is finite,

  $${\int }_{{\mathbb{R}}^d\times {\mathbb{R}}^d}K(\vec{x},\vec{\xi })f(\vec{x})f(\vec{\xi })d\vec{x}d\vec{\xi }\ge 0$$

• Gaussian kernel

  $$K(\vec{x},\vec{\xi })=e^{-\frac{\Vert \vec{x}-\vec{\xi }{\Vert }^2}{{\sigma }^2}}$$

  • radial basis function (RBF) SVM

• Networking
• encoding/decoding
• framing
  • error handling for framing
• reliable transmission
  • stop-and-wait transmission
  • continuous transmission: sliding window algorithm
    • go-back-$n$
    • duplicate ACK
    • selective ACK
    • sliding window performance
    • sliding window frame identifier count
• Ethernet
  • Ethernet switch
  • Ethernet address
• Wi-Fi
  • Wi-Fi distribution system
• network switch
• forwarding
  • packet forwarding (frame-based forwarding)
  • circuit-based forwarding
  • source-based routing
• Ethernet switch device
  • spanning tree algorithm
  • repeater
  • virtual local area network (VLAN)
• interconnect network
  • internet protocol (IP)
    • IP fragmentation
  • IP address
    • network information center (NIC)
    • IPv4
    • IPv6
    • subnet/CIDR
    • network address translation (NAT)
  • IP forwarding by router
    • address translation
    • default route
  • routing table
    • distance vector protocol
    • link-state protocol
  • node configuration
    • dynamic host configuration protocol (DHCP)
  • internet control message protocol (ICMP)
• interdomain routing
  • autonomous system (AS)
  • border gateway protocol (BGP)
  • routing relationship and policy
• user datagram protocol (UDP)
  • network port
• transport control protocol (TCP)
  • end-to-end principle
  • TCP header
  • TCP connection establishment
  • TCP flow control
• hypertext transfer protocol (HTTP)
  • HTTP message
• remote procedure call (RPC)
• real-time protocol (RTP)
  • stream control transmission protocol (SCTP)
• simple mail transfer protocol (SMTP)
• congestion control
  • traffic flow
  • resource allocation fairness
  • TCP queue discipline
  • classic TCP congestion control
    • congestion window cwnd
    • TCP slow start
    • TCP fast retransmit
    • TCP cubic
• domain name system (DNS)
  • DNS entry
• attack
  • authenticity attack
  • anonymity attack
  • availability attack
• firewall
  • firewall access policy
  • demilitarized zone
  • intrusion detection system (IDS)
• virtual private network (VPN)
  • secure tunnel
  • the onion router (Tor)
• overlay network
  • peer-to-peer network
    • BitTorrent

Networking

encoding/decoding

• non-return to zero (NRZ)
  • baseline wander
  • synchronization problem
• non-return to zero inverted (NRZI): invert signal on 1
• Manchester encoding: xor clock and bit
  • only 50% efficiency
• 4b/5b encoding
  • 64b/66b
  • 128b/130b
• modulation

framing

• sentinel-based framing
  • BISYNC, PPP
  • framing byte may appear in payload
    • escape byte
• count-based framing: body length before body
  • DDCMP
• bitwise sentinel framing
  • HDLC
  • bit stuffing: add extra 0 after 5 consecutive 1
• close-based framing
  • fixed size frame
  • need precise clock & synchronization phase
  • high efficiency

error handling for framing

• parity bit: whether number of 1 is odd

  e.g. server RAM

  • fast, easy in hardware
  • miss many error
  • high overhead

• checksum: add up all sequence of certain length

  e.g. internet checksum

  • easy in software
  • miss many error

• cyclic redundancy check (CRC): divide message as a polynomial by generator polynomial

  e.g. BISYNC, DDCMP, HDLC, ethernet, Wi-Fi

  • easy in hardware with shift register
  • good implementation ensure catching
    • all single-bit error
    • double bit error
    • odd number of error
    • burst of error shorter than $k$ bit

reliable transmission

• acknowledgement (ACK)
• timeout

stop-and-wait transmission

if ACK arrive before timeout, send next frame, else, send same frame again

• timeout hard to choose
• need 1 bit for frame identifier and in ACK
• waste bandwidth

continuous transmission: sliding window algorithm

sender

• send window size (SWS)
• last ACK received (LAR)
• last frame sent (LFS)

receiver

• receive window size (RWS)
• largest frame acceptable (LFA)
• last frame received (LFR)

go-back-$n$

resend all frame since first lost frame

duplicate ACK

• sender: resend on duplicate ACK
• receiver: resend ACK for the last in-order frame when frame out of order

selective ACK

• sender: resend missing frame between last ACK and SACK
• receiver: send SACK for out-of-order frame

sliding window performance

utilize bandwidth

frame size $f$,
bandwidth $b$,
transmission time $t$,
round trip time $r$,
time to first ACK $t_0$,
number of packet $n$

$$\begin{gathered} t=\frac{f}{b} \\ {t}_0=t+r \\ n=\lceil \frac{t_0}{t}\rceil \end{gathered}$$

sliding window frame identifier count

• smaller is better since overhead
• ≥ SWS + RWS: prevent overlap of sequence

Ethernet

• carrier sense: idle/busy
• multiple access: share medium and broadcast
• collision detection
  • collision avoidance: exponential back-off

Ethernet switch

• usually point-to-point
• high collision

Ethernet address

48 bit printed in hex separated per byte by colon

• unique
• manufacturer are allocated 3-byte OUI
• broadcast address FF:FF:FF:FF:FF:FF

Wi-Fi

• carrier sense
• multiple access
• collision avoidance
  • request to send (RTS): inform future send
  • clear to send (CTS): reserve medium

Wi-Fi distribution system

• access point connected to Ethernet
• automatic handover
  • support client mobility
  • new access point inform old one

network switch

interconnect link of the same type

• many port
• can connect to each other

forwarding

• require unique address

packet forwarding (frame-based forwarding)

• each frame contain enough information of destination (overhead)
• no reachability information
• independent forwarding
• congestion
• network switch keep forwarding table
  • map destination to outgoing port

circuit-based forwarding

• need establish circuit (stateful)
  • virtual circuit established on demand
  • circuit establishment request use frame forwarding
• network switch keep virtual circuit table
  • input port, input id, output port, output id

source-based routing

• origin provide forwarding information
  • specify each output port in switch
    • intermediate switch shift array
  • address of each switch
• origin need global view
• frame header size undefined

usage

• establish virtual circuit
• go around failure
• hide origin of packet for attack
  • mostly disabled

Ethernet switch device

multiple Ethernet interface

• build forwarding table
• broadcast if destination not on forwarding table
• remove old entry

spanning tree algorithm

• disable some link to eliminate loop
• switch with lowest ID is the root
• each switch start with self as root and broadcast root and distance
• alternative: TRILL, shortest path bridging

reason

• broadcast storm: broadcast cycle

drawback

• waste bandwidth
• $O(d)$ where $d$ is diameter of network, slow to converge if $d$ large

repeater

• increase collision

virtual local area network (VLAN)

• additional field in frame header
• block invalid address
• scoped broadcast

interconnect network

• failed attempt to convert packet

internet protocol (IP)

• service model
  • no guarantee
  • most basic requirement on link layer, work everywhere
• packet header

IP fragmentation

what to do when packet size exceed frame size

• reassemble packet at destination
• in frame header
  • use same identifier
  • indicate following fragment with flags
  • help reassemble with offset
• alternative: drop packet
  • default in IPv6
  • tell sender maximum valid size

IP address

• hierarchical
• network identifier
• node identifier

network information center (NIC)

IPv4

• class A: big network, first byte < 128, 1 byte reserved
• class B: smaller, first byte 129 ~ 191, 2 byte reserved
• class C: small, first byte ≥ 192, 3 byte reserved
• private address: 10.0.0.0/8, 172.16.0.0/12, 192.168.0.0/16

IPv6

• 16 byte
• written in hex, 2 byte between each colon, $0$s omitted

subnet/CIDR

split address

• length x.y.z.w/l
  • bit not masked determine subnet size
  • network smaller than /24 usually not allowed in routing table
• netmask: same as length, $1$s followed by $0$s
• can split large subnet/ aggregate small subnet and advertise big network
• routing table can have overlapping entry, specific one used

network address translation (NAT)

enable computer in network share same globally routed public address

• engineering solution (hack)
• connection mapping: NAT table, use local port and remote IP and port to multiplex packet
• IP no longer unique across device
• port forwarding (UPNP) so incoming connection arrive

IP forwarding by router

• if interface is connected to destination network, translate to link-layer address (e.g. MAC) and deliver over local network
• else, find a router nearer to destination and do the above to it

address translation

• build link-layer address from IP
  • does not work, e.g. IPv4 address (4 byte) to MAC (6 byte)
  • privacy leak, e.g. IPv6 EUI-64 deprecated
• address resolution protocol (ARP)
  • source broadcast ARP request
  • matching node send ARP response with link-layer address to requester
• neighbor discovery protocol (NDP) for IPv6

default route

just deliver to this route if not in my routing table

routing table

• can configure manually but usually automatically by routing protocol
• distilled into forwarding table
• map destination to potentially many next port
• additional information than forwarding table

distance vector protocol

• used by routing information protocol (RIPv2)
• each router periodically broadcast all its best route to each neighbor
• count to infinity problem
  • solution: limit maximum distance to 15
  • split horizon optimization: do not send route back to where it is from

link-state protocol

• used by open shortest path first (OSPF)
• each router globally broadcast all its link at change
• reliable flooding
  • costly
  • send link-state packet (LSP)
    • list of neighbor and metric (cost) of link
    • sequence number: increasing
    • guaranteed delivery via ACK
    • time-to-live
    • resend if no ACK
  • receiver discard LSP with lower sequence number than seen
  • receiver forward LSP
  • receiver optimization: wait for other LSP for a while
  • only needed when topology change
• metric
  • usually fixed
  • dynamic metric cause route oscillation and unpredictable performance

node configuration

• manual configuration: maintain IP allocation table
• autoconfiguration: DHCP

dynamic host configuration protocol (DHCP)

• client without IP address broadcast DHCP discover message
• DHCP server respond with configuration
  • IP address
  • DNS server
  • default gateway
  • lease duration
• DHCP server reserve IP prefix and give new device unallocated IP address
• DHCP relay allow multiple network to use 1 DHCP server

internet control message protocol (ICMP)

• report error, transmit metadata
• for troubleshoot

message type

• 0: echo reply

• 3: destination unreachable

  • 0/1/2/3: network/host/protocol/port unreachable
  • 4 fragmentation needed, for maximum transmission unit (MTU) discovery

• 8: echo request

interdomain routing

autonomous system (AS)

set of router following same policy, a.k.a domain

• distinct operator
• transit traffic: traffic across two AS
• stub AS: on the border, no transit trafic
  • transit AS: opposite; promise to route you anywhere
• multihoming: network with multiple provider
• peering point: host network equipment

border gateway protocol (BGP)

• de facto standard
• policy-based routing
  • oblivious to performance
  • goal: find loop-free policy-compliant path
  • no obligation to accept or propagate route
  • can withdraw route
• focus on scalability
  • only propagate most preferred route
• only need to run on router that connect two AS
• configure BGP session manually
  • sometimes require contract and service agreement
  • small/regional network pay larger network for transit

routing relationship and policy

• whatever make them money
• provider-client/client-provider: client pay for transit
  • provider export all route to client
  • client export only its route to provider
• peer-to-peer: exchange route for free
  • peer export client route to peer

user datagram protocol (UDP)

multiplex packet for different application

• demultiplexing key (network port) in packet
• add packet to queue for socket. packet stay until application call recv()
• datagram: packet

network port

• 2 byte, local to each node
• which port
  • in the spec
  • portmap
  • well-know port: SSH: 22, DNS: 53, HTTP: 80, HTTPS: 443

transport control protocol (TCP)

• demultiplexing
• guaranteed delivery
  • dynamic retransmission timer
• in-order delivery
  • dynamic sliding window
• bidirection transmission
• flow control
  • accommodate for slowest endpoint
• congestion control
  • coordinate across nodes

end-to-end principle

functionality should be provided at a layer only if it can be complete there

• guarantee on each link does not guarantee end-to-end
• TCP/IP push reliable delivery to transport layer

TCP header

• number each byte: SequenceNum
• ACK for each byte: Acknowledgment
• control sliding window: AdvertisedWindow

TCP connection establishment

• three-way handshake
• 4 messages to tear down

TCP flow control

• receiver set AdvertisedWindow to remaining buffer space
• sender set sliding window size according to AdvertisedWindow
  • block send() on buffer full
• sender send 1 byte periodically to check AdvertisedWindow
  • prevent chicken-egg problem: hang on 0 AdvertisedWindow
• 32 bit sequence number, sliding window can have up to $2^{16}$ byte
  • prevent sequence number wrap around
  • increase sequence number to 64 bit with option flag
• use all bandwidth
  • AdvertisedWindow has 16 bit, maximum sliding window size is 64KiB
  • option flag to multiply value in AdvertisedWindow
• Nagle’s algorithm: sender wait for ACK if cannot send full frame
  • silly window syndrome: sender send tiny frame due to tiny AdvertisedWindow
• adaptive transmission: EstimatedRTT $t_e$, MeasuredRTT $t_m$, Timeout $t_o$

  • Karn/Partridge algorithm with parameter $a$:

    $$\begin{gathered} t_e=a\cdot t_e+(1-a)\cdot t_m \\ {t}_o=2\cdot t_e \end{gathered}$$

  • Jacobson/Karels algorithm with DeviationRTT $\sigma$, parameter $\delta$:

    $$\begin{gathered} t_e=t_e+(\delta \cdot (t_m-t_e)) \\ \sigma =\sigma +\delta \cdot (|t_m-t_e|-\sigma ) \\ {t}_o=t_e+4\cdot \sigma \end{gathered}$$

  • ignore retransmitted packet

hypertext transfer protocol (HTTP)

• universal resource locator (URL)
  • protocol:path
  • for HTTP http[s]://[user[:pass]@]host/path[?query][#fragment]

HTTP message

• command/status line
  • request: command GET / HTTP/1.1
  • response: status line HTTP/1.1 200 OK
• headers
  • mandatory Content-Length: 69
• empty line \r\n
• content

remote procedure call (RPC)

client request & server respond (minimum 2 transmission)

• message oriented
• lower overhead than TCP
• stub
  • allow function call
• protocol
  • encode high-level data
• acknowledgement model
  • send ACK
  • response as ACK
  • ping/working
• sync/async

popular example: REST/gRPC

real-time protocol (RTP)

• latency is vital
• monitor path property
• let application handle packet drop

stream control transmission protocol (SCTP)

• media delivery
• built-in media stream sync
• not depend on low-layer functionality
  • common: IP + UDP
• example: WebRTC

simple mail transfer protocol (SMTP)

1. user send mail to domain server
2. domain server send to other domain server
3. other domain server push to other user
4. other user retrieve message using IMAP or POP3

• plain text: encode binary to string
• optional authentication: usually only between user/server

congestion control

• router-based vs endhost-based
• priori resource reservation vs transmission-time feedback
• window-based vs rate-based
• throughput vs latency: power = throughput / latency

traffic flow

• defined as (Source IP, Destination IP) or (Source IP, Source Port, Destination IP, Destination Port)
• aid router track soft state

resource allocation fairness

Jain’s fairness for $n$ flow with throughput $x_i$

$$f(x_1,\cdots ,x_n)=\frac{{\left({\sum }_{i=1}^n{x}_i\right)}^2}{n{\sum }_{i=1}^n{x}_i^2}:{\mathbb{R}}^n\to [0,1]$$

• 1 is most fair

TCP queue discipline

• FIFO queue with tail-drop
  • prevalent
• priority queing
  • absolute priority: higher priority always first
  • reserve a fraction of bandwidth
  • diffserv: buy priority
• fair queuing
  • number of flow variable and large
  • flow send packet of different size
• random early drop (RED): drop packet before queue fill
  • no drop below minTreshold
  • increasing drop probability between minTreshold and maxThreshold

classic TCP congestion control

• utilizing bandwidth & fairness
• introduced during “congestion collapse”
• implicit signal: drop packet

congestion window cwnd

limit number of unacknowledged byte

additive increase/ multiplicative decrease (AI/MD)

• packet dropped: cwnd = max(cwnd / 2, packet_size)
• not dropped: cwnd += packet_size
• mathematically proved to converge to same throughput

TCP slow start

• exponentially increase cwnd at start: each ACK: cwnd += 1
• when dropped
  • slow start threshold SSthresh = cwnd / 2
  • each RTT: cwnd = packet_size
    • actual: each ACK: cwnd += packet_size / cwnd
• slow start while cwnd < SSthresh, do AI/MD afterwards

TCP fast retransmit

• receiver send duplicated ACK for each packet out of order
• sender retransmit on multiple duplicated ACK

TCP cubic

• default in Linux since 2006
• hybrid slow start
  • identify ACK slowdown and do AI/MD
• stay at expected maximum cwnd, do AI after no drop for a while

domain name system (DNS)

• first try: “hosts” file /etc/hosts
• top-level domain by ICANN
• domain level hierarchy
• name resolution: ask name server from root up
• 13 root server each use different implementation
• distributed database

DNS entry

• canonical name
• nick name
• subdomain entry

attack

authenticity attack

• phishing: impersonation
• spoofing: hide source of attack

countermeasure: HTTPS

anonymity attack

• censorship
• persecution
• blackmail

countermeasure: VPN, TOR

availability attack

• DDoS
• ransom

firewall

• block incoming, usually allow outgoing
• software/hardware
  • cheap, flexible vs expensive, opaque
  • low vs high performance
• stateful/stateless
  • have vs no memory
  • cheap, easy vs expressive

firewall access policy

• accept, drop, reject
• default allow vs default deny
• IP, transport protocol, port, application data

demilitarized zone

• allow closely watched device to access more

intrusion detection system (IDS)

monitor software/hardware to detect malicious activity

• network intrusion detection system (NIDS)
• host intrusion detection system (HIDS)

virtual private network (VPN)

• tunneling protocol
• end-to-end encryption

usage

• remote access
• site-to-site
• bypass firewall/proxy

secure tunnel

• TLS, SSL
• IPsec
  • authentication header (AH): after IP header
  • encryption header (EH): after AH, before encrypted TCP header
  • wrap all above as payload into another IP-AH-EH-encrypted payload

the onion router (Tor)

overlay network

• internet is overlay IP network over physical link
• VPN is overlay IP network over internet

example

• overlay multicast

peer-to-peer network

• unstructured peer-to-peer network: messy
• super node: big machines, store what file neighbor have
  • coordination: maintain after super node leave
• tracker: broadcast what peer interested in same file
  • peer exchange (PEX): list of known peer

BitTorrent

• dedicated tracker track peer and torrent
• direct connection between peer for data transfer
  • select peer by speed (tic-for-tat)
  • seeder: peer with file
  • leecher: peer looking for file
• distributed hash table (DHT)
  • no need for tracker

• Data Science

Data Science

• Visualization
• data type
  • item
  • attribute
    • attribute type
  • link
  • position
  • grid
  • structured data
  • unstructured data
• symbolic display
  • graph
  • mark
  • channel
    • characteristic of channel
• analysis framework
  • user task
• graph theory
  • centrality
    • degree of vertex
    • betweeness of vertex
    • closeness of vertex
      • geodesic distance between vertex
    • eigenvector of vertex
    • clustering coefficient
• time

Visualization

data type

item

discrete entry

attribute

measured property

attribute type

• nominal (categorical)

  with equality relationship

• ordinal

  with order

• quantitative (numerical)

  with algebra

  • ratio: with meaningful $0$
  • interval

link

relationship between item

position

spatial location

grid

sampling strategy for continuous data

structured data

• table: item & attribute
  • flat
  • multi-dimensional
• network: item & attribute & link
• field: grid & attribute
• geometry: position

unstructured data

text, audio, graphics…

symbolic display

• parallel coordinate
• treemap
• field
• choropleth map
• star plot

graph

• framework
  • scale
• content
  • mark
• label
  • title
  • axis

mark

represent item, link

• point
• line
• area

channel

represent attribute

• position
• color
  • hue
  • saturation
  • luminance
• shape
  • glyph
• tilt
• size
• area
• texture

characteristic of channel

• selective
• associative
• quantitative
• order
• length

analysis framework

four level

• domain situation
• data/task abstraction
• visual encoding/interaction idiom
• algorithm

three question

• what
• why
• how

user task

• query
  • retrieve value
  • find extremum
  • determine range
• search
  • sort
  • filter
• consume
  • compute derived value
  • characterize distribution
  • find anomaly
  • cluster
  • correlate

graph theory

$G(V,E)$

• independent set: no edge
• clique: all possible edge
• path: all edge can be consecutively traversed
• tree: no cycle
• network
• unconnected graph
• biconnected graph: no articulation point
  • articulation point: break the graph if deleted
• bipartite graph: edge between only vertex for two set

centrality

quantity to measure vertex importance

degree of vertex

number of connected node

• in-degree/ out degree for directed graph

betweeness of vertex

sum of number of shortest path through the vertex divided by number of shortest path between each pair of vertex

$$B(i)=\sum _{a,b}\frac{g_{aib}}{g_{ab}}$$

closeness of vertex

sum of geodesic distance between the vertex and every other

$$C(i)=\sum _{j}d(i,j)$$

geodesic distance between vertex

number of edge between them on the shortest path

eigenvector of vertex

adjacency matrix dot vector of degree

clustering coefficient

time

• Documentation

Documentation

• Pandoc

Pandoc

How to use Pandoc to produce a research paper

create paper.pdf from paper.md and paper.bib

pandoc --pdf-engine latexmk -C --bibliography=paper.bib \
-M reference-section-title=Bibliography \
-V classoption=twocolumn -V papersize=a4paper -V fontsize=12pt \
-V geometry:margin=0.1in -V mainfont=Times \
-s paper.md -o paper.pdf

deal with CJK

pandoc --pdf-engine xelatex -C --bibliography=paper.bib \
-M reference-section-title=Bibliography \
-V classoption=twocolumn -V papersize=a4paper -V fontsize=12pt \
-V geometry:margin=0.1in -V mainfont=Times -V CJKmainfont='Songti SC' \
-s paper.md -o paper.pdf

using HTML as intermedia and wkhtmltopdf to create PDF

pandoc -s paper.md -o paper.pdf -t html5 \
-V margin-top=0 -V margin-bottom=0 -V margin-left=0 -V margin-right=0

word count

pandoc --lua-filter ~/.config/helper.lua/wc.lua input

convert docx to md:

cat INPUT_FILENAME.docx | pandoc --from docx --to markdown_strict \
    --extract-media=. -o OUTPUT_FILENAME.md &&
    sed -i -e 's/\\\_/_/g' \
        -e 's/\\\\\[/[/g' \
        -e 's/\\\\\]/]/g' \
        -e 's/\\\\\*/*/g' \
        -e 's/\\\\left\\\\\\\\ /\\\\left\\\\{/g' \
        -e 's/>/>/g' \
        -e 's/&lt;/</g' \
        OUTPUT_FILENAME.md

• Exams
  • Cheatsheet CSS

Exams

Cheatsheet CSS

html body {
    font-size: 12.5px;
}

* {
    line-height: 1 !important;
    margin-top: 0 !important;
    margin-bottom: 0 !important;
    padding-top: 0 !important;
    padding-bottom: 0 !important;
}

h1,
h2,
h3,
h4,
h5,
h6 {
    font-size: 1em !important;
}

main,
div,
section {
    margin: 0 !important;
    padding: 0 !important;
}

:not(span, code, pre) {
    font-family: Arial Narrow !important;
}

main {
    display: block !important;
}

a.anchor {
    display: none;
}

section.markdown-body {
    column-count: 3;
    column-gap: 0;
}

html body ul,
html body ol {
    padding-left: 1em;
}

• TOEFL
  • reading
    • inference
    • summary
  • speaking
    • defend personal choice
    • campus-related passage + dialog
    • academic course passage + lecture
    • academic course passage

TOEFL

reading

inference

• do not jump away from choice contradicting to article

summary

• do not choose choice that are not main point

speaking

do not add stuff not on notes

defend personal choice

• give example

campus-related passage + dialog

• summarize passage first

academic course passage + lecture

• directly go into lecture, mention passage in the way

academic course passage

• get example
• omit details, keep summary

• Financial

Financial

• Monero

Monero

• p2pool mining setup using Monero GUI: add below to Daemon startup flags in node setting (from https://www.reddit.com/r/MoneroMining/comments/19dvhpg/unable_to_set_up_p2pool_node/)

  --zmq-pub tcp://127.0.0.1:18083
  

• Government

Government

• United States
  • Enter US checklist

United States

• apply for visa outside US

Enter US checklist

• passport w/ > 6 months validity
• visa & all related document

• macOS

macOS

get ID of app:

osascript -e 'id of app "SomeApp"'

stop mds_store going crazy: disable Spotlight indexing

sudo mdutil -a -i off
# enable later
sudo mdutil -a -i on

add big folders to Spotlight privacy ignore list

flush DNS cache:

sudo dscacheutil -flushcache
sudo killall -HUP mDNSResponder

restart audio control, useful when audio is not working:

sudo killall coreaudiod

install xcode-select w/o using the garbage CLI that hangs: find the version for the corresponding Xcode version here https://developer.apple.com/download/all/?q=command%20line%20tools%20for%20Xcode, download the .dmg file, and install

MagSafe not working: reboot

• Sucklessfy
  • DS.Store
  • key repeat
  • disable bloat daemon

Sucklessfy

allow apps from anywhere

sudo spctl --master-disable

DS.Store

remove all .DS_Store in subfolder

find . -name '.DS_Store' -type f -delete

key repeat

disable alternate character and enable key repeat for APP_NAME

defaults write APP_NAME ApplePressAndHoldEnabled -bool false

disable bloat daemon

cd /System/Library/LaunchDaemons
sudo launchctl unload com.apple.mobile.softwareupdated.plist

• Mathematics

Mathematics

• Abstract Algebra
• integer
  • natural number
  • well-ordering axiom
  • division algorithm
    • divisibility
    • greatest common divisor
      • Euclidean algorithm
      • Bézout’s identity
      • relatively prime
    • prime number
      • Euclid’s lemma
      • fundamental theorem of arithmetic
• relation
  • partition of set
  • equivalence relation
    • equivalence class
  • modular arithmetic
    • congruence module $n$
    • congruence class
    • addition and multiplication in modular arithmetic
      • unit
      • zero divisor
• group
  • abelian group (commutative group)
  • nonabelian group
    • general linear group of degree $n$ over $R$
      • special linear group of degree $n$ over $R$
  • binary operation
    • associative binary operation
    • commutative binary operation
  • order of group
    • order of element in group
  • Torsion group
  • dihedral group $D_{2n}$
    • permutation of set
  • symmetric group on set
    • array notation of permutation
    • cycle notation of permutation
      • transposition
      • disjoint cycle
  • subgroup
    • subgroup test
    • centralizer of group
      • center of group
    • normalizer of group
  • cyclic group
    • fundamental theorem of cyclic group
  • homomorphism
    • well-defined map
    • automorphism
    • isomorphism
      • equivalence relation from isomorphism
      • cyclic isomorphism
      • Cayley’s theorem
    • kernel and image of homomorphism
  • coset
    • set of coset
      • index of subgroup in group
      • Lagrange’s theorem
  • normal subgroup
    • normal subgroup test
  • quotient subgroup
    • natural projection
  • isomorphism theorem
    • first isomorphism theorem
    • second isomorphism theorem (diamond theorem)
    • third isomorphism theorem
    • forth isomorphism theorem
• ring
  • commutative ring
  • ring with identity
  • division ring
  • field
  • zero divisor of ring
    • integral domain
  • unit of ring
  • subring
    • subring test
    • center of ring
    • characteristic of ring
    • nilpotent of commutative ring with identity
  • polynomial ring
    • polynomial in $x$ with coefficient in $R$
  • matrix ring
    • scalar matrix
  • ring homomorphism
  • ideal of ring
    • ideal test
    • maximal ideal
    • prime ideal
  • quotient ring
  • isomorphism theorem for ring
    • first isomorphism theorem for ring
    • second isomorphism theorem for ring
    • third isomorphism theorem for ring
    • forth isomorphism theorem for ring

Abstract Algebra

integer

$$\mathbb{Z}:=\{\cdots ,-2,-1,0,-1,-2,\cdots \}$$

natural number

$$\mathbb{N}:=\{0,1,2,\cdots \}$$

well-ordering axiom

$\forall R\subseteq \mathbb{N},R\ne \varnothing ,\exists a\in R$ s.t. $\min (R)=a$

division algorithm

$\forall a,b\in \mathbb{Z},b>0,\exists !q,r\in \mathbb{Z}$, s.t.

$$a=bq+r,0\le r<b$$

divisibility

$b|a$, or $b$ divide $a\iff \exists c\in \mathbb{Z}$, s.t. $a=bc$

• $b\nmid a$, or $b$ do not divide $a$
• $b|a\iff b|(-a)$
• $a\ne 0,b|a\Rightarrow b\le |a|$

greatest common divisor

$a,b\in \mathbb{Z}\setminus \{0\},\exists !d:=\gcd (a,b)$, s.t.

1. $d|a,d|b$
2. $c|a,c|b\Rightarrow c\le d$

or

1. $d|a,d|b$
2. $c|a,c|b\Rightarrow c|d$

Euclidean algorithm

$a,b\in \mathbb{Z}\setminus \{0\}$

1. let $r_{-2}=a,r_{-1}=b$

2. apply division algorithm on $r_{i-1},r_i$ until $r_{n+1}=0$

   $$r_{i-1}=q_{i+1}{r}_i+r_{i+1}$$

3. $r_n=\gcd (a,b)$

• $a,b,q,r\in \mathbb{Z},b>0,a=bq+r\Rightarrow \gcd (a,b)=\gcd (b,r)$

Bézout’s identity

$a,b\in \mathbb{Z}\setminus \{0\},\exists u,v$ s.t.

$$\gcd (a,b)=au+bv$$

• $\gcd (a,b)=\min (\{ax+by|x,y\in \mathbb{Z}\})$
• $x,y\in \mathbb{Z},c=ax+by\Rightarrow \gcd (a,b)|c$
• find $u,v$: substitute $\gcd (a,b)$ from the last equation in Euclidean algorithm up

relatively prime

$a,b$ are relatively prime $\iff \gcd (a,b)=1$

• $\gcd (a,b)=1\iff \exists x,y\in \mathbb{Z},ax+by=1$
• $a|bc,\gcd (a,b)=1\Rightarrow a|c$

prime number

$p\in \mathbb{Z}$, then $p$ is prime $\iff p\ne 0,p\ne \pm 1$, the only divisor of $p$ are $\pm 1,\pm p$

• composite number: not prime

Euclid’s lemma

$p$ prime, $p|ab\Rightarrow p|a$ or $p|b$

• $p\in \mathbb{Z}\setminus \{0,\pm 1\}$, then $p$ prime $\iff$ if $p|ab$, then $p|a$ or $p|b$
• $p$ prime, $p|a_1{a}_2\cdots a_n\Rightarrow \exists i,p|a_i$

fundamental theorem of arithmetic

$\forall n\in \mathbb{Z}\setminus \{0,\pm 1\},n$ can be factored uniquely into product of primes

relation

relation $R$ on $A$ is a subset $R\subseteq A\times A$

$aRb$ or $a$ is related to $b\iff (a,b)\in R$

• $a/Rb$ or $a$ is not related to $b$

partition of set

$A$ is a non-empty set, partition of $A$

$$\mathcal{P}:\{A_i|i=1,2,\cdots \}$$

s.t.

1. $\forall i\ne j,A_i\cap A_j=\varnothing$
2. $A=\bigcup _i{A}_i$

• $R_{\mathcal{P}}:=\{(a,b)|\exists A_i,a\in A_i,b\in A_i\}$ is equivalence relation

equivalence relation

1. reflexive: $aRa$
2. symmetric: $aRb\Rightarrow bRa$
3. transitive: $aRb,bRc\Rightarrow aRc$

equivalence class

equivalence class of representative $a$

$$[a]:=\{x\in A|xRa\}$$

• $aRb\iff [a]=[b]$

• $[a],[b]$ are either disjoint or identical

• quotient set of $A$ by $R$

  $$A/R:=\{[a]|a\in A\}$$

  is partition of $R$

modular arithmetic

$a,b,n\in \mathbb{Z},n>0$, then

$a{\equiv }_{n}b$ or $a\equiv b$ (mod $n$) or $a$ is congruent to $b$ modulo $n\iff n|(a-b)$

congruence module $n$

$\mathbb{Z}/n$ ($\mathbb{Z}$ mod $n$) or quotient set of $\mathbb{Z}$ by ${\equiv }_n$

• $\mathbb{Z}/n$ is equivalence relation on $\mathbb{Z}$

congruence class

equivalence class of $a$ modulo $n$

$$\begin{gathered} [a{]}_n:=\{x\in \mathbb{Z}|x{\equiv }_{n}a\} \\ =\{a+nk|k\in \mathbb{Z}\} \end{gathered}$$

• there are $n$ distinct congruence classes

addition and multiplication in modular arithmetic

$$\begin{gathered} [a]+[b]=[a+b] \\ [a][b]=[ab] \end{gathered}$$

• addition and multiplication are well-defined
• $\forall [a]\in \mathbb{Z}/n,\exists !$ additive inverse
• $[a]\ne [0]$ either has unique multiplicative inverse or it has not

unit

$\exists x\in \mathbb{Z}/n,[a]x=[1]$

• $[a]$ is unit $\iff \gcd (a,n)=1$

zero divisor

$\exists x\ne [0],[a]x=[0]$

• $p\in \mathbb{N}\setminus \{0,1\}$, then

  $p$ is prime

  $\iff \forall [a]\ne [0]$, $[a]$ is unit

  $\iff [b][c]=[0]\Rightarrow [b]=[0]$ or $[c]=[0]$, or no zero divisor

group

ordered pair $(G,\ast )$

• set $G$
• binary operation $\ast$

axiom group satisfy:

1. $\ast$ is associative
2. identity: $\exists e\in G,\forall a\in G,a\ast e=e\ast a=a$
3. inverse: $\forall a\in G,\exists a^{-1}\in G,a\ast a^{-1}=a^{-1}\ast a=e$

property

1. $e$ is unique
2. $\forall a\in G$, $a$ has unique inverse
3. $a\ast x=b$ and $y\ast a=b$ has unique solution, cancellation law work

• $(a^{-1}{)}^{-1}=a$
• $(a\ast b{)}^{-1}=b^{-1}\ast a^{-1}$
• value of $a_1\ast a_2\ast \cdots \ast a_n$ is independent of the bracketing

abelian group (commutative group)

$\ast$ is commutative

• $\mathbb{Z},\mathbb{Q},\mathbb{R},\mathbb{C},\mathbb{Z}/n,{\mathbb{R}}^{m\times n}$ under $+$
• $\mathbb{Q}\setminus \{0\},\mathbb{R}\setminus \{0\},\mathbb{C}\setminus \{0\},(\mathbb{Z}/n{)}^{\times }$ under $\cdot$

nonabelian group

• dihedral group of order $2n$, $D_{2n}$
• $(GL(n,\mathbb{R}),\cdot )$

general linear group of degree $n$ over $R$

$$GL(n,R):=\{A\in R^{n\times n}|A\text{ is invertible}\}$$

special linear group of degree $n$ over $R$

$$SL(n,R):=\{A\in GL(n,R)|\det A=1\}$$

binary operation

$$\ast :G\times G\to G$$

associative binary operation

$$(a\ast b)\ast c=a\ast (b\ast c)$$

commutative binary operation

$$a\ast b=b\ast a$$

order of group

$|G|$, or order of $G$, is the number of distinct elements in $G$

order of element in group

$|a|$, or order of $a$, is the smallest $n\in {\mathbb{Z}}_{+}$ s.t.

$$a^n=e$$

or $\infty$ if $n$ DNE

• $e,a,a^2,\cdots ,a^{n-1}$ are distinct
• $a^m=1\iff n|m$
• $\forall m\in {\mathbb{Z}}_{+},|a^m|=\frac{n}{\gcd (m,n)}$

Torsion group

$G$ is a Torsion group, then $\forall a\in G,|a|$ is finite

• Torsion-free group: $\forall a\in G,a\ne e,|a|=\infty$

• Torsion subgroup of $G$: for abelian group $G$,

  $$\text{Tor}(G):=\{a\in G||a|\text{ is finite}\}$$

• $ab=ba,\gcd (|a|,|b|)=1\Rightarrow |ab|=|a||b|$

• $G$ is abelian Torsion group, then $c$ has largest order $\Rightarrow \forall a\in G,|a|||c|$

dihedral group $D_{2n}$

rotation ($r$) and reflection ($s$) of n-gon

$$\begin{gathered} \{1,s,r,sr,r^2,s{r}^2,\cdots ,r^{n-1},s{r}^{n-1}\}n\ge 3 \\ (r^i)(k)=i+k\mathrm{mod}n \end{gathered}$$

• order $2n$
• degree $n$
• $|s|=2$
• $|r|=n$
• $\forall 0\le i\ne j\le n-1,s{r}^i\ne s{r}^j$
• $\forall 0\le i\le n,r^{i}s=s{r}^{-i}$

permutation of set

permutation of $X$: bijection

$$\sigma :X\to X$$

symmetric group on set

set $\Omega \ne \varnothing$

$S_{\Omega }$, the set of permutation of $\Omega$

$(S_{\Omega },\circ )$, symmetric group on $\Omega$

• $n\ge 1,\Omega =X_n\Rightarrow (S_n,\circ )$, symmetric group of degree $n$
• $|S_{\Omega }|=n!$
• $n\ge 3\Rightarrow (S_n,\circ )$ nonabelian

array notation of permutation

$\alpha$ is permutation on $X_n$

$$\alpha =\left(\begin{array}{cccc}1& 2& \cdots & n\\ \alpha (1)& \alpha (2)& \cdots & \alpha (n)\end{array}\right)$$

cycle notation of permutation

cyclically permute and fix the rest

$$(a_1{a}_2\cdots a_m)=\left(\begin{array}{cccc}{a}_1& a_2& \cdots & a_m\\ a_2& a_3& \cdots & a_1\end{array}\right)$$

• $m$-cycle (or cycle of length $m$)

transposition

$2$-cycle

• $\forall \sigma \in S_n,\sigma$ can be expressed as product of transposition
  • not unique
  • even permutation: length of such transposition is even
  • odd permutation

disjoint cycle

no common number

• $\alpha ,\beta \in S_n$ disjoint $\Rightarrow \alpha \beta =\beta \alpha$
• $\forall \pi \in S_n,\pi \ne 1,\pi$ can be uniquely expressed as product of disjoint cycle of length at least 2

subgroup

$H\le G$, or $H\subseteq G$ is a subgroup of $G$

1. $H\ne \varnothing$
2. $\forall x,y\in H,xy\in H$
3. $\forall x\in H,x^{-1}\in H$

• $H<G$, or $H$ is a proper subgroup of $G$

subgroup test

1. $H\le G\iff$
   1. $H\ne \varnothing$
   2. $\forall x,y\in H,x{y}^{-1}\in H$
2. $|G|<\infty ,H\le G\iff$
   1. $H\ne \varnothing$
   2. $\forall x,y\in H,xy\in H$