CS Homework from the Turn of the Millennium
I pulled a backup of my old home directory off a server recently. /home/ugrad5/mmichie/class/, New Mexico State University, mostly 2001-2002. Twenty-five directories spanning a full CS degree: data structures, algorithms, compilers, operating systems, networking, parallel computing, assembly, graphics, and a couple of contest entries. About 770 files, mostly C, some Java, a handful of 68HC11 assembly.
This is the sequel to learning Pascal in the Canal Zone. Same person, six years later, different country.
Hello, My Name Is
CS 171. The first assignment. Name_Tag.java, the whole thing:
// Matt Michie
// CS 171
// Lab 5 - Name Tag Program
// Prints a command line argument.
class Name_Tag {
public static void main (String[] args) {
System.out.println ("Hello. My name is " + args[0]);
} // method main
} // class Name_Tag
// -=-=-=-=-
// Output
// -=-=-=-=-
// bear[2] java Name_Tag Matt
// Hello. My name is Matt
The output is pasted right into the source file as a comment. The hostname was bear. The program is twelve lines including blanks.
Registers and RAM
CS 273 was embedded systems, programming a Motorola 68HC11 microcontroller in assembly. hw1.asm implements a comparison and swap routine:
* system constant
RAM equ 0
STACK equ $ff
EEPROM equ $f800
RESET equ $fffe
* data area
org RAM
a rmb 1 * int a ;
b rmb 1 * int b ;
c rmb 1 * int c ;
tmp rmb 1 * int tmp;
* code area
org EEPROM
n1 fcb 3 * a = 3;
n2 fcb 2 * b = 2;
n3 fcb 1 * c = 1;
start
* program code
ldaa n1
ldab n2
staa a
stab b
Every line has a C equivalent in the comments. ldaa becomes a = 3. stab becomes b = 2. The mapping between high-level intent and raw register manipulation is spelled out instruction by instruction, the way you have to think when there are no abstractions left.
Red-Black Trees
CS 372, Data Structures and Algorithms. The extra credit assignment was a red-black tree implementation. redblack.c, dated November 15, 2001:
RedBlackTree *Insert(int key)
{
RedBlackTree *current, *parent, *x;
current = root;
parent = 0;
while (current != NIL) {
if (key == current->key)
return (current);
parent = current;
if (key < current->key)
current = current->left;
else
current = current->right;
}
x = (RedBlackTree *) malloc(sizeof(*x));
x->key = key;
x->parent = parent;
x->left = NIL;
x->right = NIL;
x->color = red;
Full insert with rebalancing, left and right rotation, delete with fixup. The sentinel node’s key is 666. The tree prints itself with parenthesized inorder notation. This was the assignment where you first internalize that a data structure isn’t just a concept from a textbook; it’s memory you allocate, pointers you maintain, invariants you restore after every mutation.
Building a Compiler
CS 370 was compilers. The work started with token1.c, a tokenizer that recognizes words, numbers, periods, comments, strings, and reserved words. Each character maps to a code via a 256-entry lookup table:
for (ch = 0; ch < 256; ++ch) char_table[ch] = SPECIAL;
for (ch = '0'; ch <= '9'; ++ch) char_table[ch] = DIGIT;
for (ch = 'A'; ch <= 'Z'; ++ch) char_table[ch] = LETTER;
for (ch = 'a'; ch <= 'z'; ++ch) char_table[ch] = LETTER;
By lab 8, there’s a full compiler that parses function definitions and goal expressions, then emits C code. compiler.c generates #include headers, a read_number() function, and a main() that prints the result of evaluating the goal expression. The compiler tracks function names, parameter indices, and recursion state. It’s a tiny language, but it’s a real compiler: source in, executable out.
FireSHell
CS 474 was operating systems. The big project was FireSHell (FSH), a Unix shell built with Eric Zeitler and Daniel Foesch. The README opens with a warning:
A new shell being designed with the goal of producing a shell that bridges the gap between GUI and CLI. This is a primitive ALPHA and should not be used unless you are secure about your system. Note this is a big warning! If your system goes down because you used FSH, and can’t do anything from a console anymore, we’re really sorry, but that’s tough nuggets!
The architecture is clean for a student project. parse.c tokenizes the command line, handling quoted strings. interp.c is the main loop: read a line, parse it, dispatch. Built-in commands (cd, pwd, set, unset, exit) are handled internally. Everything else goes to execute.c:
int execute(char *filename, char* argv[], int deamonize)
{
pid_t child;
int status;
child = fork();
if(!child)
{
DEBUG("I am a child executing in a new environment\n");
execvp(filename, argv);
perror("fsh");
exit(-1);
}
if(!deamonize)
{
DEBUG("I am a parent waiting away");
waitpid(child, &status, 0);
/* flush std buffers in case the child is dumb */
fflush(stdout);
fflush(stderr);
fflush(stdin);
}
else
DEBUG("program deamonized, so I continue...");
return 0;
}
Fork, exec, wait. The comment “flush std buffers in case the child is dumb” is the kind of defensive programming you learn from experience. The TODO file lists what they never got to: pipes, redirection, aliasing, configurable prompts. The CREDITS file names Eric’s “Q&D Shell” (Quick and Dirty) as the foundation. The shell script test.fsh starts with #!/bin/fsh -f and runs two commands: ls and echo hello. They shipped what they had.
Network Othello
CS 484 was networking. The assignments built up from raw sockets to a protocol with checksums, NAK/ACK framing, and error codes. program2/server.c implements a server that accepts TCP connections, parses framed packets, and validates checksums:
void setupSocket(int server_port);
int parsePacket(char *buff, char *tokens[]);
int computeChecksum(char *data);
void readFrame(char *buffer);
int sendNAK(char *frame_id, char *error_code);
int sendACK(char *frame_id, char *message);
The final project was an Othello game server. Two clients connect, choose colors, and play a full game of Reversi over TCP, with the server managing the board state, validating moves (checking all eight directions for outflanking), and announcing the winner. Socket programming, process forking per client, game state machine, protocol design. It’s a lot of moving parts for a class project.
Parallel Mandelbrot
CS 491 was parallel computing with MPI. mandelbrot.c distributes the computation of the Mandelbrot set across multiple processors. The master opens an 800x800 X11 window, sends row numbers to workers, and draws points as results come back:
MPI_Init(&argc,&argv);
MPI_Comm_rank(MPI_COMM_WORLD,&myrank);
MPI_Comm_size(MPI_COMM_WORLD,&mysize);
if(myrank == 0)
{
/* ... open X11 display, create window ... */
for (num=1; num < mysize; num++)
{
MPI_Send(&row,1,MPI_INT,num,data_tag,MPI_COMM_WORLD);
count++;
row++;
}
do
{
MPI_Recv(&rowstruct,X_RESN+2,MPI_INT,MPI_ANY_SOURCE,
MPI_ANY_TAG,MPI_COMM_WORLD,&status);
count--;
if (row < Y_RESN)
{
MPI_Send(&row,1,MPI_INT,rowstruct.procnum,
data_tag,MPI_COMM_WORLD);
row++;
count++;
}
/* ... draw points ... */
} while (count > 0);
}
Each worker receives a row number, iterates z = z^2 + c up to 100 times per pixel, and sends back which points are in the set. The master uses a work pool pattern, sending new rows to whichever processor finishes first. The iteration itself is the standard escape-time algorithm:
do
{
temp = z.real*z.real - z.imag*z.imag + c.real;
z.imag = 2.0*z.real*z.imag + c.imag;
z.real = temp;
lengthsq = z.real*z.real+z.imag*z.imag;
k++;
} while (lengthsq < 4.0 && k < 100);
The same class had montecarlopi.c, which estimates pi by throwing random points at a circle and counting how many land inside. Also parallelized with MPI, also using a master-worker pattern. The formula is right there in the comments: pi = 4 * amount in circle / amount total.
Dots-n-Boxes
The ACM programming contest entry. prototype.c, a Dots-n-Boxes AI. The header sets the tone:
// Matt Michie
// mmichie@linux.com
// ACM entry
// Thanks / greets go out to:
// PI the soundtrack
// Astral Projection
// ezeitler
// dcook
// the milkman
// truefluke
// This program sucks. I ran out of time so I'll submit what
// I have.
// Although if i wake up early maybe i'll work on it (yeah right).
The AI tracks a 2D board of lines (vertical, horizontal, or both), looks for three-sided boxes it can close, and falls back to random moves when it can’t find one. The MakeMove function is self-described as “Full of UGLY HACKS!!!!!!!!!!!” and includes a goto labeled Fucked:. The three-sided box finder returns 666 when it finds one. He submitted what he had.
The greets section is a snapshot of the NMSU CS social circle circa 2001: ezeitler (Eric Zeitler, the FireSHell co-author and later a Signalnine collaborator), dcook, the milkman, truefluke (Darren Morrin, Signalnine’s most prolific poster). The email is mmichie@linux.com, because that’s where I was volunteering at the time.
The Arc
CS 171 to CS 491 is roughly the shape of an undergraduate CS education. You start by printing your name. You end by distributing fractal computation across a cluster and rendering it in real time. In between, you learn that a shell is just parse-fork-exec in a loop, that a compiler is just recursive descent with code generation, that a red-black tree is just a binary tree that refuses to become a linked list, and that every network protocol is just framing, checksums, and state machines.
The code quality is uneven in the way that student code always is. There are elegant implementations sitting next to hacks held together with gotos. There are meticulous comments in one file and none in the next. The FireSHell team divided the work cleanly but never finished the TODO list. The ACM entry was submitted half-done at midnight with Astral Projection playing in the background. That’s what learning looks like.
The featured files are here: the programs referenced in this post, from Name_Tag.java through the Mandelbrot renderer. The full archive is in the repo.