Category: Computer Science

Last week, I was sitting behind my desk at work, surfing hacker news and and at the top of the website floated an article by the co founder of “Daily Coding Program”, a small tech start up that e-mails daily newsletters with a programming question.  The article shared some of their insights over the past year and how they bootstrapped the company and eventually grew to $2,000 in monthly revenue.

Although I was interested in reading the blog post, I ended skipping over most of it and navigated to their front page, where I scrolled up and down and read more about the company’s product.  When I reached the end of the front page, I was confronted with a sample interview question:

There’s a staircase with N steps, and you can climb 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters.

This question, I had initially thought, could be solved using some techniques that I recently learned from taking my discrete mathematics course. But to confirm whether or not I could apply permutations and combinations, I hollered at my colleague, repeating the question out loud and asking him how this problem could be solved. And as I started reading the question out loud, “There’s a staircase with N steps, and you can climb …” he interrupted me, finishing my sentence with, “1 or 2 steps at a time.”

Apparently, while preparing for interviews with Google and Microsoft, he had stumbled across this same practice problem.

So after letting him interrupt me, I asked him if this particular problem could be solved with permutations or combinations. In other words, do these two mathematical concepts apply to the problem. He confidently answered, “No — dynamic programming.” He then proceeded to step me through his solution, scribbling down his work on a white piece of 8.5 x 11 that sat on my desk.

Fast forward to now.

I’m at home, starting the next lesson for my discrete mathematics course, the lesson title: “Counting using Recurrence Relations” and “Solutions to Recurrence Relations.” I’m skimming the chapter, building a mental model of what the entire chapters entail, an overview.  And when I reached the end of the first chapter, where exercise problems live, I couldn’t help but form a little grin.

To my surprise, the following chapters cover topics relating to the interview question that I had just read. In fact, the exercise in the chapter is phrased almost identically:

Sal climbs stairs by taking either one, two, or three steps at a time. Determine a recursive formula for the number of different ways Sal can climb a flight of n steps.

So, I find it always nice and serendipitous when what you are learning, either in school or on your own, can be applied to real life examples. Albeit, this application was only for an interview question.

But I’ll still consider that as a victory.

About six months ago, I enrolled myself in a computer organization (i.e. CS1410) course offered by University of Northern Iowa and I’m taking it remotely from Seattle, where I work full time as software engineer at Amazon (Web Services).

I’ve completed about two thirds of the course, which consists of sixteen homework assignments and three proctored exams, my most recent homework assignment requiring me to code in MIPS, a low level programming language known as assembly. More specifically, I’m tasked with implementing the quicksort, a recursive algorithm, to sort a sequence of integers.  This homework assignment targets teaching two important computer science concepts: the run-time stack and calling conventions.

Normally, I complete one homework assignment per week. However, this homework assignment was extremely challenging, taking roughly two and a half weeks to complete. The first couple days I dedicated to drilling the quicksort algorithm into my head, ensuring that I could visualize how the program actually sorts elements in the sequence, reading article after article (and sections from the books that have been collecting dust on my bookshelf); the remainder of the time I spent deep diving into writing the assembly code, typing code and executing in a MIPS simulator.  I cannot explain the number of times I grew frustrated, banging my head into the keyboard, because of program crashing.  At one point, I was stuck — for three days straight. None of my troubleshooting skills pinpointed me to the root cause.  After three days of staring at the code, I finally discovered the problem: I was corrupting the run-time stack.  After modifying one single line, updating the instruction to subtract 24 instead of adding 24 to the stack pointer (i.e. $sp register), the quicksort program ran flawlessly.

All in all, I found the homework assignment as challenging but rewarding.

As a programmer, I’ve written a line or two of code that includes the modulus operator (i.e. “return x % 2“).  But, never have I paused to think: “How does the underlying system carry out this operation?” In this post, I limit “underneath the hood” to the lowest level (human readable) programming language: assembly.

So, I’ll take a program (written in C language) and dump it into assembly instructions. Then, I’ll explain each instruction in detail.

My background in assembly programming

Up until a few weeks ago, I had never studied assembly—I did flip threw a page or two of an assembly book, when a colleague mentioned, about five years ago, that his uncle programmed in assembly—and I certainly underestimated the role that assembly plays in my career.

Sure—the days of writing pure assembly language evaporated decades ago, but the treasure lies in understanding how programs, written in higher level languages (e.g “C, Perl, PHP, Python”), ultimately boil down to assembly instructions.

Modulus program

So, I contrived a trivial modulus program written in C—let’s dissect it:

// modulus.c

int modulus(int x, int y){
    return x % y;
}

Converting C code into assembly

Before a program can be executed by an operating system, we must first convert the program into machine code—we call this compiling.  Before we run our program (modulus.c) through the compiler, we need to discuss two arguments that we’ll pass to the compiler, in order to alter the default behavior.  The first argument, -0g, disables the compiler from optimizing the assembly instructions.  By default, the compiler (we’re using gcc) intelligently optimizes code—one way is by reducing the number of instructions.  The second argument, -S, instructs the compiler to stop at  just before it creates the machine code (unreadable by humans), and, instead, directs the compiler to create a file (modulus.s) containing the assembly instructions.

# gcc -Og -S modulus.c

The command above outputs a file, modulus.s, with the contents (unrelated lines removed):

modulus:
movl	%edi, %eax
cltd
idivl	%esi
movl	%edx, %eax
ret

Let’s step through and explain each of the assembly instructions, one-by-one.

mov

When we want our CPU to perform any action, such as adding, substracting, multiplying, or dividing numbers, we need to first move bytes of data (an intermediate value, or from memory) to a register.  We move data to registers with the mov command, which is capable of moving data from:

• register to memory
• memory to register
• register to register
• immediate value to memory
• immediate value to register

The assembly above first moves data from one register (%edi) to another register (%eax).  This is necessary since subsequent instructions, such as cltd, rely on data being present in the %eax register.

cltd

cltd stands for “convert long to double long.”  But before we dig into why we need this instruction, we must detour and briefly explain the next instruction in line, idivl.

When we send an idivl (divide long) instruction, the processor calcutes the numbers and store the quotient in one register, and stores the remainder in another.  These two values stored in the register are half the size; if the dividend is 32 bits, the cpu stores (1) 16-bit value in one register, and the other 16-bit value in another.

Therefore, if we expect a 32-bit quotient and 32-bit remainder, then the dividend (which is, presumably, 32-bits) must be doubled—to 64-bits.  In our modulus program, we set a return value of type int.

idivl

idivil divides the numerator (stored in %eax) by the argument (or denominator) — the argument that we passed to the instruction.  In our assembly example above, idivl divides the value stored in %rax, by the value in %esi—x and y, respectively.

movl

At the end of a sequence, assembly (by default) returns whatever value is stored in the register %rax.  Therefore, the final instruction moves the remainder, not the quotient, from %edx to %rax.

Wrapping up

I hope I was able to share a thing or two on how a higher level program ultimately breaks down into simple assembly instructions.

[1] I was banging my head against the wall until I found a easy to understand reason why we must convert long to double long: http://www.programmingforums.org/post12771.html

How many page table entries are required given a virtual address size and page size?

I was confronted with this question when reading Computer Systems from a programmer’s perspective on virtual memory management (VMM) which forced me to reread the chapter, over and over. It wasn’t until I forced myself to close the book, step away from the problem for a day, was I able to fully grasp what was being asked:

Let’s narrow the scope and focus on a single instance, where n is 16 and P is 4K;  the question can be easily rephrased into something that makes more sense (to me): “How many 4k pages can fit into 16 bit memory address”?

First, how any bits are required, for a 4K block size, to represent a single page? Well, 2¹² is 4096 so … that’s sufficient. Therefore, we can rephrase the abstract question that we can solve mathematically: “How many 12 bit pages can fit into a 16 bit virtual address size?”

So, the problem now boils down simple division— 2¹⁶ / 2¹²,which can be expressed as 2^16-12: 2⁴, which is sixteen (16). That’s 16 page table entries that required for a virtual address of size of 16 combined with a page size of 4k.

The same approach can be taken for all the remaining practice problems. Convert the page (e.g. 4k, 8k) size into bits and divide that into the virtual address size (e.g. 16, 32)

I’m slowly working through “Computer Systems from a programmer’s perspective” [1] , struggling every bit of the way. I stopped beating myself up about it, though.

The code snippets below are in C. The first function, inplace_swap, swaps two integers. The code itself looks lacks intent but I promise you, it swaps two integers.

The second function, reverses an array. Coming from the Python world, I wondered why in the world we need to pass incount as an additional argument. I discovered the additional argument is absolutely necessary. C functions will always collapse array arguments into a pointer. The length of pointer, which is nothing more than a memory address, cannot be calculated [2].

#include <stdio.h>

void inplace_swap(int *x, int *y){
    *y = *x ^ *y;
    *x = *x ^ *y;
    *y = *x ^ *y;
}

void reverse_array(int a[], int cnt){
    int first, last;
    for (first = 0, last = cnt - 1; first <= last; first++, last--){
        inplace_swap(&a[first], &a[last]);
    }

}

This function appears to work just fine, at first. It reverses even numbered array flawlessly, however, fails to reverse an odd numbered array.

void print_array(int a[], int cnt){
    int i;
    for (i=0; i < cnt; i++){
        printf(" %d", a[i]);
    }
    printf("\n");
}

int main(){
    int a[] = {1,2,3,4};
    int a_length = sizeof(a)/sizeof(int);
    printf ("Reversing 1 2 3 4 : ");
    reverse_array(a, a_length);
    print_array(a, a_length);
}

$ ./reverse_array
Reversing 1 2 3 4 :  4 3 2 1

int b[] = {1,2,3,4,5};
int b_length = sizeof(b)/sizeof(int);
printf ("Reversing 1 2 3 4 5:");
reverse_array(b, b_length);
print_array(b, b_length);

$ ./reverse_array
Reversing 1 2 3 4 5: 5 4 0 2 1

0001 ^ 0001 = 0000
0111 ^ 0111 = 0000

1 2 3 4 5
5 2 3 4 1
5 4 3 2 1

1 2 3 4 5 6 7
7 2 3 4 5 6 1
7 6 3 4 5 2 1
7 6 5 4 3 2 1

But I love teaching: the hard work of the first class, the fun of the second class. Then the misery of the third.

—Ken Thompson

In the post, I’m covering what a binary search tree is, its structure, and the basic operations: find, insert, and delete. We also cover the three methods for traversing the tree. At the end of this post are practice problems to help drive the concepts home.

Next is an example problem that glues the concepts together.

    15
   /  \
  7    21
 / \
5  10

 public class BinaryTree<E> {
     Node root;

     private class Node<E> {
         int key;
         E data;
         private Node leftChild;
         private Node rightChild;

         @Override
         public String toString(){
             String myString = "<Node [" + this.key + "]>";
             return myString;
         }
     }
}

public Node<E> find(int key){
    Node<E> currentNode = this.root;
    while(currentNode !=null){
        if (currentNode.key == key){
            return currentNode;
        }

        if (key < currentNode.key){
            currentNode = currentNode.leftChild;
        } else {
            currentNode = currentNode.rightChild;
        }
    }

    return currentNode;
}

public void insert(int key, E data){
    Node<E> newNode = new Node<E>();
    newNode.key = key;
    newNode.data = data;
    if(root == null){
        root = newNode;
        return;
    }else{
        Node<E> currentNode = root;
        Node<E> parent;
        while(true){
            parent = currentNode;
            if(key < currentNode.key){
                currentNode = currentNode.leftChild;
                if (currentNode == null){
                    parent.leftChild = newNode;
                    return;
                }
            }else{
                currentNode = currentNode.rightChild;
                if (currentNode == null){
                    parent.rightChild = newNode;
                    return;
                }
            }

        }
    }
}

public void inorder(Node<E> localRoot){

    if(localRoot !=null){
        Node<E> currentNode = localRoot;
        inorder(currentNode.leftChild);
        System.out.println(currentNode);
        inorder(currentNode.rightChild);
    }


}

public void preorder(Node<E> localRoot){
    if (localRoot != null){
        Node<E> currentNode = localRoot;
        System.out.println(currentNode);
        preorder(currentNode.leftChild);
        preorder(currentNode.rigthChild);
    }
}

public void postOrder(Node<E> localRoot){
    if (localRoot != null){
        Node<E> currentNode = localRoot;
        postOrder(currentNode.leftChild);
        postOrder(currentNode.rightChild);
        System.out.println(currentNode);
    }
}

 Before               After

    15                  15
   /  \                /  \
  7    21             7    21
 / \                   \
5  10                   10

public boolean delete(int key){
    Node<E> currentNode = root;
    Node<E> parent = currentNode;
    boolean isLeftChild = false;

    while (currentNode.key != key){
        parent = currentNode;
        if (key < currentNode.key){
            isLeftChild = true;
            currentNode = currentNode.leftChild;
        } else {
            currentNode = currentNode.rightChild;
        }
        // node not found
        if (currentNode == null){
            return false;
        }
    }
    // Case 1: No children
    if (currentNode.leftChild == null && currentNode.rightChild == null){
        if (currentNode == root){
            root = null;
            return true;
        }
        else if (isLeftChild){
            parent.leftChild = null;
            return true;
        } else {
            parent.rightChild = null;
            return true;
        }
    }
    return false;
}

     Left child with single left child

    15                15
   /  \              /  \
  7   21            5   21
 /
5

     Left Child with a single right child

    15                15
   /  \              /  \
  7   21            9   21
   \
    9

     Right child with single left child

    15                15
   /  \              /  \
  7    21           7    18
      /
     18

     Right child with single right child

    15                15
   /  \              /  \
  7    21           7    25
         \
          25

if (currentNode.leftChild != null && currentNode.rightChild == null){
    if(currentNode == root){
        root = currentNode.leftChild;
    }
    else if(isLeftChild){
        parent.leftChild = currentNode.leftChild;
    } else {
        parent.rightChild = currentNode.leftChild;
    }
}
else if(currentNode.rightChild != null && currentNode.leftChild == null){
    if (currentNode == root){
        root = currentNode.rightChild;
    }
    else if(isLeftChild){
        parent.leftChild = currentNode.rightChild;
    }
    else {
        parent.rightChild = currentNode.rightChild;
    }
}

    15                15
   /  \              /  \
  7   21            8   21
 / \               / \
5   9             5   9
   /
  8

    15
   /  \
  7   21
 / \
5   9
     \
     12
    /  \
   10   14

public Node<E> getSuccesor(Node<E> toBeDeleted){
Node<E> parentSuccessor = toBeDeleted;
Node<E> successor = toBeDeleted;
Node<E> currentNode = toBeDeleted.rightChild;
while(currentNode.leftChild != null){
    parentSuccessor = successor;
    successor = currentNode;
    currentNode = currentNode.leftChild;
}
if(toBeDeleted.rightChild != successor){
    parentSuccessor.leftChild = successor.rightChild;
    successor.rightChild = toBeDeleted.rightChild;
}
return successor;

public class Employee {
    private int id;
    private String firstname;
    private String lastname;

    public Employee (int employeeid, String firstname, String lastname){
        this.id = employeeid;
        this.firstname = firstname;
        this.lastname = lastname;
    }

    @Override
    public String toString(){
        // < 05: Joe Schmoe >
        String myString = "< " + this.id + " " + this.firstname + " >";
        return myString;
    }

    public static void main(String[] args){
        Employee jboyd = new Employee(15, "jess", "boyd");
        Employee mstreiter = new Employee(7, "myles", "streiter");
        Employee mdavis = new Employee(21, "matt", "davis");
        Employee mmadsen= new Employee(5, "martin", "madsen");
        Employee mchung = new Employee(19, "matt", "chung");

        BinaryTree<Employee> employees = new BinaryTree<Employee>();
        employees.insert(jboyd.id, jboyd);
        employees.insert(mstreiter.id, mstreiter);
        employees.insert(mdavis.id, mdavis);
        employees.insert(mmadsen.id, mmadsen);

        // Is myles in the building?
        // returns true
        System.out.println(employees.find(mstreiter.id));

        // Jess clocks out
        employes.delete(jboyd.id);

        // Is Matt in the building?
        // returns false
        System.out.println(employees.find(mchung.id));

    }
}

    15
   /  \
  7   21
 / \
5   17

Python progression path – From apprentice to guru is a popular StackOverflow post. To categorize whether a person should take his beginner/intermediate course, one of the commentors posted this question:

I can better answer this question after reading Fluent Python. Example 1 and Example 2 deal with immutable and mutable data types – respectively. Let’s address each example individually.

>>> x = 42
>>> y = x
>>> id(x)
4298172632
>>> id(y)
4298172632

>>> x = x + 1
>>> id(x)
4298172608
>>> id(y)
4298172632
>>>

>>> x = [1,2,3]
>>> y = x
>>> id(x)
4299948256
>>> id(y)
4299948256

>>> id(x)
4299948256
>>> id(y)
4299948256

>>> def update(x, y=[]):
...     y.append(x)
...     return y
...
>>> list1 = ['a', 'b', 'c']
>>> list2 = [1, 2, 3]
>>> update('d', list1)
['a', 'b', 'c', 'd']
>>> update(4, list2)
[1, 2, 3, 4]
>>> list1
['a', 'b', 'c', 'd']
>>> list2
[1, 2, 3, 4]
>>> update('a')
['a']
>>> list3 = update('b')
>>> list3
['a', 'b']
>>> list4 = update('hello')
>>> list4
['a', 'b', 'hello']