Kenny Dewhirst

A little while back, I challenged myself to write a Scheme implementation of quicksort. After all, it’s a recursive algorithm, and Scheme is nothing if not recursive, and it seemed like a fun change of pace from writing algorithms in a procedural language.

; Quicksort a proper list
(define (quicksort lst)
  (cond
    ((null? lst)
     '())
    (else (append (quicksort (find-smaller-or-equal
                              (cdr lst) (car lst)))
                  (cons (car lst)
                        (quicksort (find-larger
                                    (cdr lst) (car lst))))))))

(define (find-larger lst lower-bound)
  (cond
    ((null? lst)
     '())
    ((<= (car lst) lower-bound)
     (find-larger (cdr lst) lower-bound))
    (else
     (cons (car lst)
           (find-larger (cdr lst) lower-bound)))))

(define (find-smaller-or-equal lst upper-bound)
  (cond
    ((null? lst)
     '())
    ((> (car lst) upper-bound)
     (find-smaller-or-equal (cdr lst) upper-bound))
    (else (cons (car lst)
                (find-smaller-or-equal (cdr lst) upper-bound)))))

I had a good time writing this, and it’s one of the shortest quicksorts I’ve seen, though I make no claims as to its efficiency.

My Advanced C++ class focused heavily on memory management; we built a string class, a date class, a time class, and a custom vector. The final project in the class was to put them all together to build an appointment book. All strings had to be handled with our own string class, all sequences had to be stored in our own vector class, and the appointments were stored using our own time and date class.

It was fun to be able to build something like this almost from scratch, and the libraries that I wrote to do it came in handy later in school, especially the MyArray class, which I made good use of in my Data Structures class a couple semesters later.

Download the C++ source code here.

This was the culminating project from my Advanced C# class. It uses a DLL built as a previous assignment as the back-end.

The program was designed to be used as a front-end to an inventory database for a media store, which sells books, music, and movies. Each kind of media can be added, removed, modified or looked up for viewing.

Download the C# source code here.

For my Assembly class, the final project was to build Conway’s Game of Life in C++, with the inner loops written in MASM.

The program allows the user to enter live cells by hand, specifying X and Y coordinates, and then it allows the user to iterate the world any number of times. Below is a screenshot of a familiar pattern, the Glider. Over successive time-steps, it will ‘walk’ down and to the right across the game world.

Download the C++ and MASM source code here.

This is a proof of concept flocking model, very similar to the first flocking simulation, Boids. It’s a toroidal world with constantly moving airplanes. In it, each of the airplanes is an agent, and they all make independent decisions based on incomplete knowledge of the world around them.

Each plane has a sight radius around it that represents how far the plane can see and a wedge behind it where it can’t see. This is intended to represent how real-world birds are thought to flock. Planes try to fly towards one another, and to align themselves with the planes in their neighborhood. This leads to a distinct flocking behavior.

Download the C# code here. It was built with XNA 3.1.

My first genetic algorithm solves problems like ‘Make X cents given Y coins from the set Z of allowed coins’. The user can input those problem values, as well as control the population size, mutation rate, and elitism bias of the genetic algorithm solving it.

Genetic algorithms work by ‘breeding’ a solution from previously generated solutions, with the goal being to breed solutions closer to a target. This is wonderful for problems with huge solution spaces, where you know the form of the answer, but not what it is, because GA’s can ‘hill-climb’ across the fitness landscape to quickly approach a right answer.

Sometimes, though, GA’s can get stuck on a local maximum in the fitness landscape, where evolving towards the right answer costs on the fitness function. In these cases, GA’s can take much longer to find the answer.

Download the C# source code here.

In my Artificial Life class, one of our assignments was to build a deterministic cellular automata. These are distinguished from totalistic CA’s like Conway’s Game of Life in that the positions of their neighbors matter. Each of the squares in the grid represents a cell; the black ones are ‘alive’, and the gray ones are ‘dead’.

The CA can be set to run a single step, or to run several, refreshing the drawing between each. The seed button will randomly set each cell on the grid to alive or dead.

The program can save the current state out to a file, and then load these files back into the program.

My CA allows the user to enter a rule by in a separate tab by checking a box for each of the possible states in a von Neumann neighborhood. The number generated at the bottom of the pane is a 32-bit number, derived from the 32 states. It provides a unique identifier for the rule set.

Download the C# source code here.