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