Date: Tue, 10 Dec 1996 16:49:00 GMT Server: NCSA/1.4.2 Content-type: text/html CSE 373 Projects

CSE 373: Information about Projects

Purpose

The project is your opportunity to practice design and implementation of a solution to a problem, using data structures and algorithms, in a more realistic context than the preceding assignments have afforded. Not only can you experience the problem-solving process through a more complete sequence, but you also can choose your topic from a variety of choice options. Unlike the assignments so far, you are asked to work in groups of two people (with the possible exception that those working on the OPSIS topic below might be asked to work separately). By working together with a partner, you will be able to communicate with another person as you solve your problem together. If every student worked alone on a totally different project, there could be a tendency for you to become isolated and easily get stuck with technical problems that nobody else could help you with. The project will involve not only analysis and implementation, but reporting in both written and oral forms. This is much like what a software development team has to do in a corporate environment when they are part of an R&D effort, a custom software project, or a new product plan. So, the data structures and algorithms will be a key part of your project, but not the only part.

Topics

  • Applying graph algorithms to WWW URL data. This could include taking a bunch of WWW documents, computing some basic features of them like number of words, links, images, headings, etc., to obtain a "feature vector" for each document, and then considering the complete graph on n of these documents with a weight on an edge representing the "distance" between its two documents. Then a minimum spanning tree could be constructed in order to identify clusters of similar documents.
  • Using tree and graph data structures to represent and manipulate images or maps. Possibilities include implementing pyramids as multiresolution representations of images or implementing sets of chain codes to represent roads, political boundaries, rivers, and other linear features in maps. Here is some additional information on pyramids and quadtrees.
  • Implementing and comparing various types of binary search trees (such as splay trees, AVL trees, etc.) using the OPSIS visual programming system for data structures. Students selecting this option will not need to write a large program in C, C++ or any other traditional language but will do most of their work with a powerful, new visual editor for data structure algorithms. Here is more information on OPSIS.
  • Processing of symbolic expressions. Linked lists are particularly useful in representing symbolic expressions such as mathematical formulas, parts of computer programs, and representations of knowledge for artificial intelligence systems. At their core, interpreters for language such as Lisp and Mathematica are list processing systems. Students selecting this option will either design their own list-oriented language and implement it in C++ or choose a small subset of Lisp, Mathematica or similar language and implement that in C++.

    Project Milestones

  • Wednesday, November 20. Topic descriptions due. You should have chosen a partner (unless you are doing the OPSIS option) and a topic by this time. Your description should include both partners' names, a title for the project, a paragraph explaining your topic and what you hope to accomplish. It should also explain how you and your partner plan to divide up the work. Who will do what? Explain which computing platform you plan to use. List one or two references you have found that will help you in your project. How will the user interact with your program?
  • Between Monday, November 25 and Wednesday, November 27. Small group meetings with me to discuss your projects and any difficulties you may be having. Here is the current schedule.
  • December 6, 9. Project presentations.
  • December 11. Written reports due.

    Late policy for project milestones

  • Topic descriptions received after the due date will have 10% taken off.
  • Teams that do not meet with me by December 2 will have 10% taken off the whole project grade.
  • Project reports turned in after 12:35 on Dec. 11 but by 12:00 on Dec 12 will be docked 10% of the project grade, and there will be another 10% off for each business day the report is late. Turning it in on Monday, Dec 16 means 30% off the project grade. Tuesday, Dec 17 it's 40% off, and at the final exam it is 50% off. If turned in after the final exam, no credit will be given for projects.
    Last update: 13 November 1996.
    
    S. Tanimoto