In this and next couple of blogs, we gonna talking about data representations, how numbers are represented in different forms and some of the properties. We need to understand what is the bit level representation of numbers and how does that affect some of the properties when we operate them on. Especially, we need to pay attention to these corner cases.

From today, I will post my study notes of Introduction to Computer Systems (following CMU 15213). In the meantime, I am going to finish the assignments in this book and post my solutions.

Heapsort

In this exercise part, we gonna introduce Heapsort. Heapsort’s running time is ${ O (n\lg n) }$. Just like Quicksort, heapsort sorts array in place.

Heapsort also introduce aother useful algorithm design techinque: a kind of data structure called “heap”. Here the “heap” can be used in Heapsort and Priority queue. Let’s move forward to its content!

Today, we will introduce a very interesting Algorithm, called “Quicksort”, which was invented by Tony Hoare in 1962.

• It’s also a Divide-and-Conquer Algorithm.

• The array will be sorted “in place”. (That means Quicksort doesn’t need extra array like Mergesort.) Therefore, it’s fairly efficient in its use of storage.

• Very pratical (with tuning)

This blog is going to introduce how C++ Compiler works. In fact, the C++ source files are just some text files, and we need some way to transform them into some executable binary files. We have two operations here, one of them called compiling and one of them called linking (we will talk about it in next blog). Actually, what the compiler does is taking our source files and convert them into an object files (which is a kind of intermediate format).

Let’s go ahead and see what compiler does!

Find Max Subarray

The CLRS textbook talks about an algorithm which can find max subarray in ${ \Theta(n \lg n) }$ time. This algorithm uses Divide-and-Conquer idea, that divides the array into two subarray in each time and compares the max subarry of left part, right part or crossing mid element. So the recurrence is ${ T(n) = 2 T(n/2) + \Theta(n) }$. Here, we indroduce another iterative algorithm that can find the max subarray in ${ \Theta(n) }$, which is the exercise 4.1-5.

This lecture will talk about “Divide-and-Conquer”, which is a very powerful algorithm design technique. The main paradigm of it is shown in the following:

• Divede: If we are given some big problem and don’t know how to solve it in an efficient way, we can try to solve it into some small sub-problems.

• Conquer: Then we can conquer each problem recursively.

• Combine: Sometings, we need combine the solutions of these subproblems into the solution of the big problem.

This lecture will introduce the “Elimination” method to solve the linear equation systems. In most cases, the Elimination will work, when matrix ${ A }$ is a good matrix. In this lecture, we also talk about the what kind of situation will let “Elimination” fail.