Monday, October 11, 2010

Smoke some trees, yo

A tree is an acyclic graph where each node has one or zero parents and zero or more children.

Binary trees

Number of children is always two.

Ordered binary trees

All nodes left of a given node, n, are <= n; all nodes right of n are > n.



  1. visit root
  2. go left
  3. go right
  1. go left
  2. visit root
  3. go right
  1. go left
  2. go right
  3. visit root

Level-order (breadth first search) (needs a queue)

  1. enqueue root in q
  2. while q is not empty
    1. n = q.dequeue()
    2. visit n
    3. if n.left, enqueue(n.left)
    4. if n.right, enqueue(n.right)
Note: changing the queue above to a stack will result in pre-order search (also have to swap the order of 2.3 and 2.4)

Of course, rather than using recursion, you can replace the call stack with an actual stack, and then mark the nodes as visited or not.

Saturday, October 9, 2010

Sorting? Awesome fun for whole family

Bubble sort is dumb. Let's look at quick sort and merge sort.

Quick sort:

  • O(nlogn) best and average.
  • Worst case is O(n^2)
  • divide and conquer mother fucker
  • probably not stable (same keys may change order)
  • pick a pivot, p, in the array (usually in the middle)
  • partition into two arrays, one with all values <= p, the other with all values >= p
  • the partition step can be done in place
  • call quicksort on the two arrays
  • if the array size is zero, you're done
template  void qs2 (vector&; arr, int left, int right)
 if (left >= right)

 int i = left, j = right;

    int pivot = arr[(left + right) / 2];
    while (i <= j) {
        while (arr[i] < pivot)
        while (arr[j] > pivot)
        if (i <= j) {
  swap(arr[i], arr[j]);

 qs2(arr, left, i - 1);
 qs2(arr, i + 1, right);

Now let's try some mergesort:

  • worst case is O(nlogn)
  • better for using slower data access things like files, tape drives
  • don't have to store everything in memory
template  void mergeSort (vector& v)
 if (v.size() < 2) return;
 // first divide in two, until only size 1 left
 int n = v.size(); 
 int middle = n / 2;
 vector left;
 left.insert(left.begin(), v.begin(), v.begin() + middle);

 vector right;
 right.insert(right.begin(), v.begin() + middle, v.end());



 // then reconstitute such that the new result is in order
 while (left.size() > 0 || right.size() > 0)
  if (left.size() > 0 && right.size() > 0)
   if (left[0] <= right[0])
  else if (left.size() > 0)
   v.insert(v.end(), left.begin(), left.end());
  else if (right.size() > 0)
   v.insert(v.end(), right.begin(), right.end());

Studying: Day Two

When we last left off I was working on stacks. I'm gonna implement it with a linked list by deriving off my linked list class. On the way I am also going to change the class to use generics. It turns out it's super easy to create generic classes in Java:

class LinkedListNode 
    public LinkedListNode(T newData)
        data = newData;

    LinkedListNode next = null;
    T data; 

public class LinkedList  {
// etc

I'm told that generics in Java are sorta bad because they use type erasure. This is when the compiler "erases" the types of generic classes, so it's compatible with any old non-generic classes. This means if a class has type T, you cannot reference T anywhere in your code, like you could with C++ templates. In fact, the other day one of my coworkers was complaining that they have to duplicate code that creates a new class of a generic type just for this reason.

public class Stack  extends LinkedList 
    public Stack()

    public void push(LinkedListNode node)
    { = _root;
        _root = node;        

    public LinkedListNode pop()
        LinkedListNode ret = _root;
        _root =;

        return ret;
and then a queue is trivial:
public class Queue  extends LinkedList
    public void enqueue (LinkedListNode node)

    public LinkedListNode dequeue ()
        LinkedListNode ret = _root;
        _root =;
        return ret;

Friday, October 8, 2010

Study time

In preparation for an interview I have with a certain Mountain View, California software company, I am reviewing and practicing all the basic data structures and algorithms that I learned in second year. I will be live-blogging this. Excited yet? Fuck ya.

Linked list: 

Probably the simplest data structure. Used for lists of shit.

The basic structure is a node (in Java) with a pointer reference to its next node.

class LinkedListNode
    public LinkedListNode(String text)
        data = text;

    LinkedListNode next = null;
    String data; // or whatever interesting thing the list holds

Some design considerations:

  • Should there be a LinkedList class to perform insert/delete/retrieve operations, or should the LinkedListNode do these itself? 
  • Probably makes more sense from an OOP perspective to have a separate class absract these ops, so I will write that.
  • I should be recording how long I am spending on this. So far it's been at least 15 minutes.
  • Apparently I don't know Java that well because I've already fucked up how Java copies references, and had a typo and shit...
  • Forgot to update the previous node's next node after deleting
  • I forgot to update the root after deleting the root node
  • Forgot case where deleting the tail...wait no that's handled automatically
  • A lot (all) of these functions could have been written recursively, whatever.
public class LinkedList {
    LinkedListNode _root = null;

    public void insert(LinkedListNode node)
        LinkedListNode current = _root;
        if (_root == null)
            _root = node;

        while (current != null && != null)
            current =;
        } = node;        

    public LinkedListNode find(String data)
        LinkedListNode found = _root;
        while (found != null && !
            found =;
        return found;
// Version 1. delete using 1 extra pointer
public void delete1(String data) { LinkedListNode found = _root; LinkedListNode prev = null; while (found != null && ! { prev = found; found =; } if (found != null) { if (prev != null) { =; } else { _root =; } } }
// Version 2. delete without using 1 extra pointer
public void delete2(String data) { LinkedListNode found = _root; // special case where the head is what we're looking for if ( { _root =; //delete( found); (if we were using c/++) return; } while (found != null) { if ( != null && { =; //delete( found); (if we were using c/++) break; } found =; } } }

Insert: O(n). Access: O(n). Delete: O(n). Some variants are double-linked list (where nodes point back to their next and previous nodes, and circular, where the head points to the tail.

A popular interview question is to reverse a linked list. Here goes:

public void reverse()
        reverseEx(_root, null);

    private void reverseEx(LinkedListNode node, LinkedListNode prev)
        if ( != null)
            reverseEx(, node);
            _root = node;
        } = prev;

The above took me a long time, and you can do it without recursion. For some reason I wasn't thinking about doing it moving forward in the list:

public void reverse2()
        LinkedListNode current = _root;
        LinkedListNode prev = null;
        LinkedListNode next = null; // this is necessary, at first I thought it wasn't, i'm retarded

        while (current != null)
            next =;
   = prev;
            prev = current;
            current = next;

        _root = prev; // i fucked this up, previously I had _root = current, but at this point, current == null. but then again, I just wrote it then debuged it...hopefully i would read it over a couple times in an interview!


Stacks are the basic LIFO structure. You can create them with any data structure you like, but typically arrays or linked lists are used. The array implementation was obvious to me:

#define MAXSIZE 2

class Stack
 int _size;
 int _allocated;
 t* _data;

 Stack::Stack() : _size(0), _data(new t[MAXSIZE]), _allocated(MAXSIZE)

 t pop()
  if (_size < 1)
   throw new exception("stack underflow");
  return _data[--_size];

 void push(t d)
  if (_allocated <= _size)
   _allocated += MAXSIZE;
   t* newData = new t[_allocated];
   memcpy(newData, _data, sizeof(t) * _size);
   delete _data;
   _data = newData;

  _data[_size++] = d;

  delete [] _data;
  • I wanted to try having dynamic memory for some reason, that could grow past whatever, to test I set the maxsize to 2 which is obviously way low
  • also wanted to  use templates
  • when using a template function, it's just template  <class t> void MyFunction(){..}
  • but when using a template class, it's template <class t> class MyClass {...}
  • also I played around with std::stuff, I can't believe Fekete doesn't use it! MFC sucks compared to it.
So of course you can also create a stack with linked list:

For tomorrow:

Linked lists stacks, queues, priority queues, trees, sorting! Basic shit motherfucker.

Monday, June 7, 2010

Update to Assignment 1

I kept thinking about the assignment and found the negative weight search problem so interesting that I went back and spent another hour or so on it. I now have a full solution to the standard and both bonus assignments that includes solutions for graphs with negative weights.

Main fixes

  1. Fixed an error in my implementation of the Bellman-Ford algorithm. I misread the bounds of the inner loop: I thought it looped through all the edges in the current node, but rather, it loops through all the edges of the entire graph. I was able to simplify the code considerably once I realized my error.
  2. I also realized that for the bonus questions, any negative weight node can be used in a cycle, and this will break the Bellman-Ford algorithm. For example:
    1. Input is: 
    2. "B1"
    3. "3 3 1,1 2,3"
    4. "1 -10 2"
    5. "5 2 -1"
    6. "2 1 3"
    7. There is a cycle between nodes (1,2), and (2, 3). The Bellman-Ford algorithm cannot handle this case.
  3. To solve this challenge, I implemented a brute force exhaustive search that tries searching all nodes to all nodes recursively. This is not elegant but solves the problem quickly enough for small data sets. My solution is more of a proof of concept than anything and could use some heavy optimization. The best way to do this would be to profile the code, and see where the hotspots are.
  4. Fixed a potential array index out of bounds error when inputting start and end nodes.
The code is available here.

Tuesday, June 1, 2010

Shortest Path Assignment

The first part of the assignment works as specified, including negative weights.

For the bonus, I ran into a bug where in some cases the shortest path is not found when using negative weights. A valid path is found, but it is not always the shortest. Given more time, I could definitely figure this out, but I have reached the deadline. Please see my Bonus1GraphTest.TestNegativeSearch() for a failing test.

To use:

2. Extract the zip file
3. The app and unit test source code is in the CylindricalMatrix and CMTests folders, respectively.
4. The code is in C#.


I originally intended to write this assignment using Dijkstra's algorithm to compute the shortest path in the matrix, until I realized negative weights were valid; I therefore switched to the Bellman-Ford algorithm because it can work with negative weights. To model the graph search problem, I created a graph, node and edge classes.

The general workflow is: 

The InputParser parses the input, and returns a matrix, and start and end nodes. A graph is then created from the matrix, and the shortest path is computed. The results are output to the user.
  • The InputParser class reads input from any TextReader stream. The TextReader stream can be stdin, for user input, or a mocked stdin to aid in testing and debuggin.
  • The Matrix class I modeled after the Data Transfer Object (DTO) pattern. Future programmers may want to search for the shortest path using a non-graph algorithm, therefore I thought it best to keep the Matrix class "dumb" and only use it to be passed to other modules.
  • The graph classes do the meat of the assignment including the transform of matrix to graph, and searching.
  • There is a BaseGraph class that has default graph building and searching functionality.
  • The StandardGraph class is derived off  BaseGraph and implements features specific to the Standard portion of the assignment, such as there being no start or end row defined.
  • Bonus1Graph is derived off BaseGraph and extends the graph building functionality to search in all cardinal directions.
  • Bonus2Graph is derived off Bonus1Graph to implement "torus" wrapping.

Wednesday, April 28, 2010


I started working on this project Sunday afternoon and finished Monday evening. It's the old arcade classic Pong, with a few extra twists!

Use the mouse to control your paddle.

Players can either be computer-controller (CPU) or controlled by you (Human).

Source code is here:

It was a fun little project, and most importantly it was a project I finished.

I used the Model-View-Controller pattern when creating it:

  1. Paddles and Balls each have a model class, with basic data properties. Like radius, or width. These classes are derived off event dispatcher so that a "data changed" event can be sent when ever a property changes.
  2. I created a PaddleView and BallView class, derived off of Sprite, to visually represent the model class. These Views can only be created by passing a model into their constructor. The View listens to the Models "data changed" event and updates their view correspondingly when something changes.
  3. Finally we have a PaddleController and ModelController. These must be instantiated by passing a view into the contructor, or through a factory function which creates a model and view for the controller automatically. The Controller listens to events sent from the View, like UI events, and interprets what to do with them. In the case of the ball, the controller is responsible for adjusting the ball's path as it hits corners and paddles. The PaddleController controls the paddle's direction and AI.
The AI is very basic. It finds the ball with the closest current position and moves along the y-axis to match the ball's position. There is a slight heuristic so that the paddle favors balls that are closer to it along the horizontal axis, as the paddle can move quicker up and down rather than waiting for the ball to come to it. In the future I would like to have the paddle move toward the future position of the ball (based on its current angle and speed) rather than the present position of the ball.

Enjoy! I appreciate any feedback.

Tuesday, April 27, 2010

To actually finish a project

If you're anything like me you start many projects but rarely if ever finish them. That's why the latest project I've started is ridiculously simple, and I can actually complete it in a reasonable time. The project is the 30+ year-old video game Pong.

I created it in flash. It took about eight hours to complete.

I will upload it as soon as I figure out how.

Editting blog posts on the iphone is brutal BTW. I wonder if there's an app for that?