CSC223 2004F, Class 17: Presentations on Bugs

Admin:
* Math/CS Lunch (Cowles, North PDR area)
* Next topic: Swing
* I'll take sarcastic notes while the groups present
* Homework for Wednesday:
  * Think about expressing weights
  * Test that hashing of pairs really works.

Overview:
* The Four Skippers
* The Multi-Majors 
* Jesse's Gang
* Glimmerers + 1

/The Fearsome Foursome: World Implementations/

* Available at http://www.cs.grinnell.edu/~stewartg/cs223/BugWorld/
* Five implementations of worlds.
* perflog.txt gives performance evaluation
* Performance test (40K bugs)
  * Puts a lot of bugs in the world
  * Gets the stuff around them
  * Removes the bugs
* Search list was slow and simple
* Decided to do Vector of Vectors as more space efficient than 2D array
  * Their code sucks, too
* The two-dimensional arrays don't have huge space overhead, even in sparse worlds.
* Ryan screws up massively by claiming that binary search is O(nlogn)

/The Multi-Majors Talk About Bugs/

* Some delay as they set up their computer.
* Implemented the state machine for bugs
* First: Designed a bug, which they're having trouble finding.  Found it.
* Bugs start wandering.  They have input from the world.
* Format: State (string), Detect world, New State, Action
* Bugs forget that things are chasing them
* Sam thinks: 
  * Should we have a "weight" for various rules.
  * What are the format requirements for the various components?
  * What are the legal things that it can detect

/Jesse's Gang talks about Worlds/

* Not as nice as the first group.  Happy that it didn't crash.
* Similar implementations to the other groups, except for trees
  * Their tree is self-balancing (more or less)
* Question: Can you use Java's tree.  No.
* Strategy: Rebalance when 25% of tree changes
* Easiest to implement: 2D array (maybe list)

/Glimmerers + 1: Bug Implementations/

* Hash tables of hash tables