• final project
• Choose any one of the topics we've looked at this term to sink your teeth into in more depth. Do some extra reading, write up some code, and prepare a short paper describing what you did, how you tested it, and how it works.

• Read about crypto: DES, RSA, and all that. See my links in the resources.
• (Here's my notes and code on DES
• Pick a crypto (or related) algorithm to explore - either code up something on your own based on a description of the algorithm, or download someone else's and test it out. How different are the encrypted texts when the input varies by only one bit?

• Read about information entropy.
  • Look at Shannon's paper.
  • Browse the wikipedia entry.
  • Explore my perl code to calculate it.
• Start reading about lossless compression algorithms.
  • wikipedia data compression
  • wikipedia LZW compression
  • wikipedia Huffman coding
  • Dr Ross's Compression Crypt
  • google "huffman coding", "LZW compression", "Burrows-Wheeler transform"
• Start coding - or playing with someone else's - a compression algorithm.

• Browse the chapter on Matrices, chapter 7.
• Look up (wiki or otherwise) to get at least a clue about the following terms :
  • Gaussian elimination wikipedia
  • fourier transform and FFT
  • convolution
  • matrix multiplication
  • rotation matrix
  • eigenvalues and vectors
• Check out Jim's PDL (perl data language) code in /code/perl/pdl/
• Octave and Inline::Octave are also cool tools for doing this stuff.
• Coding: Download and explore a matrix math system, or implement and test one of the matrix algorithms discussed in class.

• Read the chapter on searching
• Pick one of the algorithms to investigate. Again, write or get some code, generate or obtain some data search, and benchmark what you get for different amounts of data.
• (Yes, this is somewhat repetitive - but it gives you a chance to explore and share what you find, eh?
• When you submit this one, give me a synopsis of your work so far this term for these 6 assignments.

• Read the chapter on sorting
• Pick one of the algorithms to investigate. Write or get some code, generate something to sort, and see if it obeys the O(?) you expect.

As discussed in class on the 10th, each of you is taking a different version of a binary-tree-like algorithm to examine, implement (with help from any sources you can muster), test, and explain. If I'm remembering right, the breakdown looks like this:

• John: red-black trees
• Daniel: skip list
• Gabe: threaded trees
• Josh: AVL and/or 2-3 trees

We agreed that we'd use data like that in /usr/share/dict/words as the string objects for populating the trees, and that we'd all have an API something like the following. We left as unspecified whether the FIRST and NEXT needed to traverse the data in order.

 ADD("string");
 DELETE("string");
 boolean = SEARCH("string");   # return the node, perhaps?
 "string" = FIRST();
 "string" = NEXT();

• Read and come to class Tues ready to discuss chapters 2 and 3 in Mastering Algorithms with Perl. That's a lot of material, but I expect a lot of it (but not all) is review for many of you.
• Code, test, and evaluate (in terms of O(n) speed and memory for various types of data) either a binary tree or a hash. You can do this in perl or c++, and can base your stuff on other people's code - but be sure to quote your sources, document the API, and be clear about what you did. If you can't get all the details done by Thursday, at least have something that runs to show in class, even if that means just typing in and testing some of the code from the text. If need be we'll look at more polished routines next Tuesday.

• From the resources page, read about Turing machines, finite state machines, and what the P, NP, and NP-Complete complexity classes are. Write a short blurb defining each and giving and example, and come to class on Tues ready to discuss.
• Download (or write code to implement) a Turing machine or finite state machine simulator. Follow one of its examples to have it do something like multiply two numbers or some other simple task of your choice. Discuss the execution time and required space for this algorithm.
• (optional) For a really good time, implement any one of permutation algorithms we discussed last week, at least for a fixed value of N, with a finite state or Turing machine.

• Read chapter 1 in "Mastering Algorithms with Perl"
• Write a program to generate all permutations of a list of N elements, in either C, C++, or Perl. Include documentation on how to use it, tests that it does what it should, and sample input/output. Generate a table of N vs runtim(N), plot the results, find a function f(N) that describes the runtime, and discuss what this says about O(?) for this algorithm. For Perl you can use Benchmark.pm (part of the standard pel distribution) for timing info.
• You can look at what Jim did (/usr/bin/time for timing, gnuplot for the plot) here.
• Brownie points: Do the same for the problem of determining whether a given permutation of 0..(N-1) is odd or even, including O(?) for (a) a random permutation (i.e. average time) and (b) the worst-case permutation for that your algorithm.

last modified Monday May 23 2005 2:14pm EDT