Author Archives: Mirkules

Reversing a Linked List

Exploring and refreshing data structures and algorithms, you will inevitably find the question “how do you reverse a linked list?”. For this exercise, we assume a singly-linked list, with a head, and the last item pointing to null (as shown).

Linked List

Singly Linked List

The goal is to end up with the following linked list:

Reversed Linked List

Reversed Linked List

Continue reading

Breadth-First Search and Depth-First Search in Java

I decided to implement Breadth First Search and Depth First Search in Java. The implementation uses a Directed as the underlying abstract data type, keeps track of visited graph nodes by keeping a separate data structure, and implements BFS by using a Queue.

Some implementations only implement DFS and BFS on trees, but this implementation uses a graph because a tree is really a directed graph with no cycles (i.e. a node cannot reach itself in traversal). However, in the case of a graph, when a node can reach itself, you have to pay special attention to those loops by marking nodes as “visited” so that you don’t “visit” them again and end up in a stack overflow or an infinite loop. There is more than one way to do this: by keeping a separate data structure of the visited nodes (the way I did it) or by adding an extra field to each node, mark it as visited each time it is visited, and reset it once you are done with the search. Since both methods would take linear time but resetting the nodes’ visited flags would make coding more complicated, I chose to keep a separate data structure for that.


UPDATE 2012/10/16: Graph in PHP. Interestingly, PHP arrays use hash maps as the underlying structure, so using key/value pairs might actually speed up the algorithm.

Eye-To-Eye Part 4: Moving the Servos

The four pieces required for the Eye-To-Eye project are in place now: A laptop running Ubuntu with Opengazer fully functional, router, Arduino with Ethernet Shield and two servos (for one eye). The glue for all the pieces — especially the opengazer-to-network part — have also all been figured out. However, putting the pieces together still required some work I didn’t anticipate, and provided some interesting challenges I have yet to solve.

But the good news is, it works! Here’s the video:

Continue reading

Installing Opengazer

For Eye-To-Eye, I decided to use Opengazer on Ubuntu. I had two laptops running Ubuntu 11.04: Acer Aspire One (slightly older netbook) and Toshiba Tecra. I eventually got both of them working, although there were a lot of tweaks. These are my notes to get it working on both of these machines, YMMV.

First, download opengazer and follow instructions in the README.

You’ll notice right away you need CMake. Thankfully, Ubuntu makes this easy:
sudo apt-get install cmake

Next, download and install VXL. Unfortunately, this has to be done from source. Because VXL is made for previous versions of linux, there are some headers which are outdated. I’ve compiled a list of problems and solutions.[see below for update]

These are all the problem areas, the rest is described well in the opengazer README.

Update: 2012-04-17

Some people were having problems installing opengazer, and I decided to put together a more comprehensive set of instructions