Grad School (2017-18)

A number of neat projects came out of attending school at the University of Washington.

Sudoku

Recursion & Backtracking

This was a remarkably quick assignment. I've always found that I handle tricky high-level concepts a lot better than low-level ones. Balance a cash drawer using basic arithmetic? Hopeless. Remember how to spell "amount?" I keep using two Ms, no matter what I do. But give me recursion, binary search trees, or Machiavelli, and they're as natural as walking.

Here, we put together a command-line program that takes in a string of numbers and zeros, generates a sudoku puzzle, then solves it by brute force, testing one square, seeing if that test is a valid move, then the next, then backtracking when all possible moves on that square have been tried, and trying the next possibility on the previous square (see video for an extremely slowed down version that shows each move. Puzzles take anywhere from 10,000-10,000,000,000 moves, so the video only displays a small subset)


Concordance Generator

KWIC & Templated Binary Search Trees

 

My very first exposure to Binary Search Trees: Autumn Quarter 2017. So far, second only to recursion, they're one of my favorite concepts in computing. 

Essentially, the program stores each word and it's surrounding context in an Entry object, which makes up the principle data within the Binary Tree structure. Outputing the tree then runs recursively through each entry in order, generating the KWIC concordance seen above.


Network Relays

UDP > TCP > TCP > UDP

The beast of a final project for Systems Programming (Operating Systems, especially Linux). The spec goes something like this:

  1. Create a relay that listens for a UDP multicast on one segment of a network
  2. Catch & interpret it's contents.
  3. Relay that message to any/all connected relays in other network segments via TCP, filtering for duplicate messages in the event of a cyclic connection.
  4. On receiving a message, Multicast the message to the local UDP network segment.

The original messages came from premade java programs that fire off short UDP multicasts, and another premade java program had to receive and interpret the messages correctly after they were passed through the relays. 

Each relay had to decompose the message, decide if it was valid, convert it into a helper object to operate on, add it's own ID to help check for duplicates, and forward the message along.

On the receiving end, a relay picked up a message from a remote relay, decomposed, edited, and recomposed it, then multicasted it to the awaiting local machines.

In practice, this looked like a lot of terminal windows, each connected to a machine in the Linux lab on campus.


Other Concepts

Over the first two quarters we covered Essential C++, Binary Trees, B-Trees, Hash Tables, Factories, Linux, Dijkstra's, Breadth & Depth First Searching, Binary Math, Predicate Calc, & Formal Logic.

For Spring 2018 we went through Operating Systems, covering everything in Linux from Memory & Storage management to multi-process to multi-threaded applications & debugging to networking.