Introduction

Quick Sort is a classical divide-and-conquer algorithm. The basic idea is: in each phase, we choose one from an array and divide this array into two subarray. All elements in first one are smaller than this number and the other’s are all bigger than this number then do the same for both parts again. Finally, we merge all and get a sorted array. Quick sort’s average time-complexity is O(nlogn) and space complexity is only O(1). Although its worst-case is up to O(n^2), it’s often the best practical choice for its remarkable average efficiency.

Core Concepts

1. Quick Sort Algorithm Description;
2. Complexity Analysis

Introduction

We all know that computers execute machine code which is a sequence of bytes encoding the low-level operations that manipulate data, manage memory, read and write data on storage device and communicate over networks. Machine-level code, also called assembly code, is generated by compiler depend on different operating system. But as abstraction is an important notation in Computer Science, many high-level programming languages enable developers to neglect the assembly code layer for distinct standards in different platforms to improve developing efficiency and put more emphasis on practical tech schema.

However, in some specific conditions like compiler optimization should take assembly layer into consideration because more effective organization of assembly code will achieve better performance which will influence the higher level architecture a lot. Plus, in reverse engineering decompile from machine code need to understand assembly code.

So what consists of assembly code? Since assembly code is a kind of programming language, employing different forms of abstraction and hiding details of implementation thorough the use of simpler, abstract model is two important properties for assembly code. The basic component of assembly code is instruction, instruction defines operation and processor state so that assembly code is equivalent to the composition of instruction set architecture which defines the processor state, the format of instructions and their effect on processor state.

A program can be viewed as a sequence of instruction and processor executes them one by one. But programs executed concurrently is one of the most critical characteristics in modern operating system. Multi-core architecture can ensure that in the same time there are several processors are running simultaneously. But for one core, how to improve the performance of concurrency? In most modern CPU architecture, sequential pipeline becomes a necessary component. The basic idea of pipeline is that instruction sequence execution can be split into several stages and processor can simultaneously execute different stages for different program to increase throughout of the system, that is, the number of *”customer”* served per unit time.

Generally, processing instruction involves a number of operations. We can organize them in a particular sequence of stages. Although instructions differ greatly in their actions, they are all executed in a uniform sequence. Let’s see the processing stages briefly:

Fetch -> Decode -> Execute -> Memory ->Write Back -> PC update

In general, Compiler -> Linker -> Instruction Set Architecture -> Assembly code -> Sequential stages -> Pipeline is the progress of source code executed in operating system. Compile is not our main point and linking will be introduced in another note.

In this note, we will introduce these concepts:

1. IA32 Instruction Set Architecture (ISA);
2. Y86 Processor: Sequential and Pipeline implementation on the foundation of IA32;

Introduction

Logistic Regression (LR) is a classical model for classification and regression which is widely used in Compute Vision, NLP and Recommending System. Its simple, effective and adaptive to both linear and nonlinear conditions. It is a logarithmic linear model as well as Maximum Entropy Model (MEM). MEM is a rule for statistic learning and generalized from Logistic Regression.

In this article, I will introduce LR first, then generalize it to MEM. At last, I will introduce how to train LR and MEM by IIS and Quasi-Newton Method.

In recent years, gradient decent and another optimizer like Adam becomes the main choices for training a ML and DL model. So I will also introduce Gradient Decent briefly but more details will be noted in another article.

Core Concepts

1. Logistic Regression and Maximum Entropy;
2. IIS and Quasi-Newton Method;
3. Gradient Decent;

Introduction

k-NN (k-nearest neighbour) is a classification and regression model. The goal of k-NN is to find k nearest neighbours of an instance and label them a given class. The input is feature vector and output is its class. Majority voting is used to predict a new instance’s class. k-NN is a supervised machine learning algorithm so that it needs labeled dataset.

Three basic components of k-NN is:

1. The k value;
2. Distance measure;
3. The rule of classification;

Most people can figure out that we can implement k-NN by linear search for the main job in training phase is to find all nearest neighbour. Unfortunately, it’s unacceptable for large dataset because of high complexity both in time and space. A more universal method is applying kd tree which is a binary tree with special form. Therefore, k-NN is an effective classification and regression model.

Main Contents

1. Majority vote;
2. Distance function;
3. kd Tree;
4. C++ implementation step by step;

Introduction

PCA and SVD are two widely used dimensional reduction techniques. Dimension Reduction, namely, is to save the information from origin data as much as possible and reduce the attributes that the data has as less as possible. PCA and SVD are closely related and the difference between them is that SVD still have the means of data opposite to PCA;

Core Concept

1. Principle Component Analysis (PCA);
2. Singular Value Decomposition (SVD);

Introduction

In Computer System, unit of information storage and the arithmetic operated on the data stored in such unit are composed of two basic components of a Computer System’s function. We will see what is Byte and how to implement mathematical computing in computer (more commonly, in all micro-systems)

Core Concepts

1. Byte, word size and Byte ordering;
2. Representation of positive and negative number in computer;
3. Arithmetic like plus, minus, multiply and divide;

Introduction

What is Hash Table?

Hash table is a special form of an ordinary array. It can complete SEARCH, INSERT and DELETE in O(1) average time;

Core concepts

1. Hash Function and Collision;
2. Chaining and Open-Addressing;
3. Linear Probing and Double Probing;