CSE465 - Data Structures and Algorithms

Bill Pringle
[email protected]
BillPringle.com

Semester Project

Students form teams and develop a software program to apply the principles learned in class.

Each week, the team leader shall e-mail a status report to the instructor with copies to the entire team. This status report shall outline the progress of the team, including any difficulties they may be having. Please don't send this information as attachments; include the information in the body of the e-mail. The status reports provide an opportunity for the team to request assistance from the instructor. Failure to disclose problems during the semester may result in a penalty applied to the score of the group submission.

At the conclusion of the course, teams will submit the final program and documentation containing two sections: one submitted by the entire team, and a second containing submissions by each individual on the team. The objective of these submissions is to convince the instructor that the team members understand the course subject material.

The documentation submitted by the Team will describe the entire process as well as the final product. This will include such things as assignments of team members, Program Design, explanation of design decisions, Interface Control Documents (ICDs), and user instructions.

The documentation submitted by individual team members will include an evaluation of the final product. This section may discuss such things as: Personal contributions to the project, how the project could have been done differently, What further development could be done (and how), insights gained from the class, etc.

Here is a more detailed description of Group Projects.

Project Requirements

Write a program that demonstrates a knowledge of data structures and algorithms. The program should include both data structures and algorithms, but may emphasize one or the other. (Emphasizing both is best, but more difficult, and not recommended for groups consisting of mostly non-programmers.)

To demonstrate a knowledge of data structures

write a program:

that processes data containing at least two different types of related data.
The program should ingest data and organize it to reflect both the types of data and their relationships.
Each type of data should have at least one unique key and at least two data fields.
The program should be able to retrieve either type of data by the key field and at least one data field.
Given one type of data, the program should be able to find at least one type of related data.
The data structures should optimize the relationships between the various objects within the program, and simplify the algorithms.
The program should be interactive, not batch, and preferably a console application.
You are encouraged to use ADTs available from my web site (linklist, stack, queue, etc.) or elsewhere rather than building your own. You can also take one of the programs from my web site and enhance it.

The program should take advantage of first-class abstract data types (ADTs). The program should be modular and, when possible, follow the model - view - controller design pattern. In order to do this, you will want to spend time at the beginning designing your major objects, and segmenting the program into loosely coupled modules. Ideally, you should be able to replace one module with another one using a completely different algorithm.

Use of Databases

Since the purpose of the program is to demonstrate an understanding of data structures and algorithms, the use of a Relational Database (RDBMS) is strongly discouraged.

The reason for this is that most people who use databases store most (if not all) of their data in a single table, create a few indecies to optimize searches, and then use SQL Select statements to extract the desired data. The resulting recordset is then examined by the application. This essentially boils down to a sequential search of an array, which doesn't demonstrate data structures very well.

While it is possible to implement data structures using databases (I do it all the time), it is beyond what most students have experience with. It requires normalized data and the use of foreign keys to link individual tables together, as well as procedures that performs joins across the tables to create a view that the application then uses. (Essentially, the stored procedures perform the same function as a first class ADT.)

If you are familiar with databases, the preceeding paragraph made sense, and you feel you know enough to create complex data structures using a database, feel free to discuss this issue with me. If I am convinced you know how to do it, I will let you use a database. However, most of the students I have had in the past didn't really know how to do this.

To demonstrate a knowledge of algorithms

write a program:

Provide multiple methods of searching and/or processing data
compares various algorithms to search and/or process the data
experiment with different heuristics as appropriate
that determines optimum approaches for the problems
although much can be taken from the text book and/or my web site, include some of your own ideas as well.

You might want to download and study the Farmer research paper for an example of how to compare different algorithms. Similar approaches can be used to compare different ways of storing the data. Comparing the times for the different approaches is a good criteria to comparisons, both other criteria can be used.

You might want to write a program to generate large test input files. Comparisons are hard to make (and often misleading) if there are only a few records in the collection. Start out with a small number of records to debug your code, then switch to a large number of records to compare approaches. You can use for loops and random number generators to quickly create a large file.

Depending on the particular program you decide to write, some of the above requirements may not quite apply. In these cases, the team should explain in their group submission why a requirement(s) don't apply to their project. In other cases, you may not have the time (or ability) to actually implement one of the requirements. In these cases, the group submission should describe how the requirement would have been implemented had more time been available.

Make sure that whatever you do, it contains several types of data items that are organized such that the user may search for particular items. It should also be able to find related items. Remember, the goal of this assignment is to demonstrate your mastery of Data Structures and Algorithms, not to simply write a program.

Example Projects

Project	Description
Music Collection	Record types: Albums, Artists, Songs. Search by Artist, Title, etc.
Relational Database	Ability to create tables, fields, & relationships, & minimal retrieval capabilities.
Write a Game	Let user play against (or with) the program.
Table of Contents for HTML page.	Determine structure of an html page (using <Hx> and <A NAME=> tags). Then create a new page containing a table of contents, inserting name tags where needed.
Program to Read E-mail	Display messages by subject, date, sender, etc.