Data Structures : ICS 340 - Metro State University -- Stachour

Welcome to
Data Structures
ICS 340

Understanding data structures is fundamental to understanding software engineering. According to measurements, between 10% and 40% of the source lines of a typical large application system are composition of one or more of the fundamental data structures. Most of this is redesigned and rewritten, not reused.

Data Structures ICS340 at Metro State

Assignments

Questions

Examples

Documentation

Contacts

What is ICS340?

ICS340 is the number for a data structures class taught at Metro State University in the Twin Cities (of Minneapolis and St.Paul). This class is different than many in that students are allowed to use Pascal, C, or another language allowed by the instructor. The reality is that most data structures work in most applications is recoded time after time because the interfaces are not designed to be necessary and sufficient for the many conditions under which they may be used. In this class, as we study the basic data structures, we shall also sample some topics towards understanding the needs of composition and replacement. In this class, I advocate the use of Ada , here's why.

Assignment Information

Most of the assignments are handed out in hard-copy. That which is online is in the asn subdirectory. Here is some additional material for:

Assignment #1
This is searching of continuous lists. I've provided an Adaish translation of the material in the book. It's this way so that all of them are similar; it does not take advantage of many of the features of Ada. These have not been tested. I have a Contiguous List Specification and Contiguous List Implmentation.
I've also provided a more paramaterized form, more on the style of what an Ada designer would normally do. I've done a Generic Contiguous List Specification, Generic Contiguous List Implementation, Generic Contiguous List Test Procedure, and a compiled and running test program. Here are also the two other program modules I did as a sample. They are: Sorting Package Specification, Sorting Package Implmentation, Sorting Package Test Procedure, and a compiled and running test program. The latter ones will be unlocked for reading only during laboratory sessions, and when requested by class members.
Assignment #2
Here's some clarifications:

Program Units -- Program Modules
For this assignment, you must have multiple program modules. For assignment 1, you might have had 3: contiguous list, seraching, test driver. These should be designed and built upon the premise that you are building something to be reused. Indicate in your writeup how you decided what the modules to implement are. Hint: Fewer than 3 or more than 10 modules is probably not acceptable.
Interface / Implementation
For this assignment, you must separate each unit into its interface and its implementation. If you are using C, this would be the (.h,.c) pair; if Ada, the (.ads,.adb) pair; if Pascal, the (.pas,.tpu) pair. I know that in Pascal the .tpu is generated; this means you need to do a very good job of documentation in your .pas source-file what-is-what. You also need to turn in the .tpu file with your machine-readable media.
Measurement
In assignment 1, you could measure either comparisions or time. In this assignment, you must measure comparisons and moves. We noted a number of problems with measuring elasped time, given the higher speed of today's platforms coupled with the low resolution of the hardware time. Accordingly, you need not measure the time.
Tables and Graphing
Since you are being asked to measure two things (comparisons and moves), you will need two sets of tables and graphs in your writeup, one for each measure.
Risks
Since you are performing an experiement with a small set of random data, rather than the full-size set of real data, there is a risk that your experiment will not scale, or even be wrong. In your discussion/explanation, include a paragraph of 1..3 sentences discussing why your experiement might not be valid.
Program documentation
A sample documentation header for modules/units and subprograms will be available soon. Watch this space for the URL.

Questions

I maintain a FAQ -- Frequently Asked Questions -- from my students. I prefer to receive questions by Email to stachour@winternet.com, thus I can respond not only to the student asking but to all of the students. For those who know Pascal and want to try Ada, there is a short mapping in the file pas2ada.txt

Examples

Here are the examples in subdirectory exp.

Here's the program life and a driver from chapter 1.
Here's a rough translation of sequential search and a driver from chapter 7.

Documentation

The documentation is in the directory doc.

Effort Recording Sheet
Remember that you are to record your effort on the programming assignments. You can find a copy of the effort recording sheet here.
Item #2

Contacts

The best way to contact me is via EMail to stachour@winternet.com. If you are in my class, you also have some alternate ways, which you will find in the class handout.

ICS 340 questions or comments: Contact Paul Stachour at Stachour@winternet.com

Welcome to Data Structures ICS 340

What is ICS340?

Assignment Information

Questions

Examples

Documentation

Contacts

Welcome to
Data Structures
ICS 340