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).
Singly Linked List
The goal is to end up with the following linked list:
Reversed Linked List
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.
The harmonic minor scale is a more complicated (sophisticated?) scale than the major scale. This post will show all the relative chords to the harmonic minor scale (in the key of A).
Lately, I’ve been thinking a lot about the relationship between chords and scales and why certain chords sound good when played in a particular key.
Turns out, every note in a scale has a relative chord. A relative chord is a chord that sounds good with that note as the root note of a scale. But how do we know which chord this is?
Now that the servos are working at the touch of a mouse, all I have to do is make the gimbal, put it in a box, hook up the servos, and away I go. But mechanical engineering has never been my strong point. In fact, my first stab at it is not looking good.
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:
This is Part 3 of my “Eye-to-Eye” adventure: figuring out how the Arduino network shield works, and how to interface with it from the OpenGazer program I discussed previously.
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.
Some people were having problems installing opengazer, and I decided to put together a more comprehensive set of instructions
Wouldn’t it be cool to use eye tracking software to control animatronic eyes?? If you answered “yes”, this post is for you – the beginning of my project, Eye-To-Eye that aims to do just that – build animatronic eyes and control them using my own eyes via eye-tracking software.