Here is a collection of links and idea for projects stolen from mail from last semester. The first has a link to some nice student project documentation.
/////////////////////////// > > Here's a nice animation of Heap Sort: > http://www2.hawaii.edu/~copley/665/HSApplet.html > Not only is this a very nice tutorial for learning heap sort, it is an example of a very well documented application. The associated web pages describe the goals of the project and the design of the software. I think the TFs would be very happy to see projects documented like this. /////////////////////////// If you don't yet know what you'd like to do -- please, have a look at the list of possibilities mentioned at the end of the "Final Project" page on the course web site. On my own page (sections/hans) I also give a few links that might give you ideas: there's a link to Stephan Wolfram's articles about cellular automata (Stephan Wolfram is the creator of the Mathematica); there's a link to Marvin Minsky's home page (Marvin Minsky is an MIT professor, founder of the Artificial Intelligence Laboratory -- together with Seymour Papert -- he's a sort of idea machine who is constantly bubbling with new ideas and tossing them out into the world). There may be nothing on those web pages that you can directly use, but they could set you thinking and dreaming. If you've never visited the wonderful web sites of the MIT Media Lab, you should also definitely do so right now: http://www.media.mit.edu/ Hans /////////////////////////// Also, for those doing game-playing projects, there is an interesting and IMO quite helpful multipart discussion of issues involved with programming a computer to play chess. There is even a heavily commented java app to play the game. It's at: http://www.gamedev.net/reference/programming/features/chess1/ Here's another link to a list of (mostly _extremely_ good) articles and PhD theses that I recently found: http://hoggy.virtualave.net/y.bishop/page1.htm They're all about search in Chess or other 2-person games. Some of the more recent onces involve learning algorithms. (There is also one about the 8-puzzle.) /////////////////////////// Here are a couple of resources folks have found userful in the past The Java in a nutshell book has a simple "paint" program. If you want an application that allows the user to draw, start here. This has been used to build an application that did "optical" character recognition. The sun java page includes some sample programs, from a slide show to a web crawler. Even if you don't use any of the code samples, this is a good place to look at examples. http://developer.java.sun.com/developer/codesamples/ /////////////////////////// > i) Spreadsheet calculator (which is strongly encouraged) > Questions: How would you do the interface? > Should this be something similar to Excel, with all items in a > column the result on a mathematical calculation involving members > of two other columns? Would it have to have a GUI? Any other > suggestions? How would a project like this employ AVL trees, > or regular trees, and how could a performance comparison be done? Reading over old mail, I'm not sure I replied to your spreadsheet question. I find this a very interesting problem, and I don't know that any student has done it for the class. I'm spaming this list in case I can interest others. While a gui is nice, you don't need one to have a useful tool. Briefly, you can extend the parser with covered in the stacks lecture to include references. Each cell holds a number or a formulae, such as =F17 + F16. Each cell has an expression and result: for numbers they are the same. When asked to print the values of the spreadsheet, you print the results. You could have another option that prints the formulaes. You could set cell values through commands, such as f22 = "=f16 + f17" f16 = 123 f18 = "Totals" You pass thorough the spreadsheet, and evaluate cells whose strings begin with "=". This already is an interesting application. You can add many more features: what happens if the order of dependancies doesn't match the order you encounter the formulaes? What happens if you have a loop? Can you have absolute and relative references, so you can cut and paste formulaes from one cell to another? This could use trees, but you will quickly encounter graph problems in sorting out dependancies. (f16 depends on g22, which depends on b13. We haven't evaluatd g22, so we can't evaluate f16) There is ample room for a challenging and interesting project sorting out these issues. Adding a GUI is nice, but there is lots of work before then. /////////////////////////// Here are some links to information about Discrete Event Simulation http://www.nmsr.labmed.umn.edu/~michael/des.html 10 easy lessons. Sample Java code http://ubmail.ubalt.edu/~harsham/ref/RefSim.htm Many sophisticated references /////////////////////////// Printed Resources Graph Algorithms and problems See Sedgewick's new book Baase and Van Gelder (see bibleography) Corman, Leiserson and Rivest (bibleo) Top-down Recursive-decent Parser Welsh, Elder and Bustard - Sequential Program Structures Wirth - Pascal Report (?) Sorting Networks See lecture 9 Knuth, vol 2 Links off our website Corman, Leiserson and Rivest (bibleo) - jeff parker
