Date: Tue, 05 Nov 1996 20:57:57 GMT Server: NCSA/1.5 Content-type: text/html Last-modified: Wed, 18 Sep 1996 18:25:48 GMT Content-length: 7243 Assignment 1: Handout

CS 367 Assignment 1: Introduction to C++

(Due Date/Time: Thursday, October 3, 1996, 5:00pm)

Introduction

The purpose of this first programming assignment is to provide experience with Unix, using a editor (vi or emacs), doing simple C++ programming, and using the gnu C++ compiler (g++) and its debugger (gdb). We have provided a partially written (but fully specified!) C++ program. Your job is to complete and thoroughly test the program. More specifically, the program implements an abstract data type (ADT) for handling a bounded integer sequence (IntSequence).


Your Job

The IntSequence ADT will represent a sequence of integers by stroring the numbers in an array of integers. The internal representation consists of the current length of the sequence plus a statically-sized array of integers that hold the sequence's current contents. The IntSequence type supports five operations, each of which takes the integer sequence as its first argument:

The clear operation initializes (or reinitializes) a sequence to be empty (contain zero elements). The append operation puts a new value at the end of a sequence. The length operation returns the number of elements currently in a sequence. The printN operation prints the first N values in a sequence, where N, the number of values, is an argument to the operation. . The sort operation sorts the integers in a sequence into ascending order.

To make your job as simple and clear as possible, we have provided three files: intseq.h, intseq.c, and prog1.c. The file intseq.h contains a complete C++ specification of the ADT-- you should not edit this file. The file prog1.c contains a complete main routine that serves as a test driver for your ADT implementation--you should not edit it either. Your job is to make a copy of the file intseq.c, which contains stubbed-out functions for the ADT operations, and add the actual implementation code. You can then debug and test your code using gdb and the driver routine in prog1.c. We have provided a small set of test data files, but you should add more test cases to find the important cases that our files fail to exercise.


How To Sort

To write the sorting function, you should use a very simple sorting scheme known as insertion sort. This algorithm sorts an array of data by stepping through the array, an element at a time, and keeping everything to the left of the current element sorted. To understand how this approach works, think of the array as being laid out from left (element 0) to right (element N-1, assuming that the array contains N elements), so the algorithm steps through the array from left to right. At each step, the current element is copied out of the array and inserted into its appropriate place in the sorted subarray to the left of the position that it was copied from. Inserting the element requires that all elements with greater values than the element be slide one position right to make space.

An efficiency hint: The tasks of finding the appropriate insertion point for the current element and sliding greater elements to the right can be combined. This can be done by scanning left from the position from which the current element was copied, sliding each element one space to the right if its value exceeds that of the current element. The insertion point will be known (and a spot will be open) when you either find a lesser value or bump into the left end of the array.


What To Turn In

You must turn in:

Everything must be turned in electronically (paper copies are not acceptable). We have created a directory for each student to turn in his or her assignment. The following command copies a file into a student's handin directory:

cp filename ~cs367-2/public/handin/prog1/username
You should replace filename with the name of the file you want to submit and replace username by your login name.

REMEMBER: No late assignments will be accepted!!! Thus, it is important that you start working soon and finish on time. However, partially finished programs are far better than no programs at all, so be sure to turn in whatever you've done -- even if you don't finish the assignment. (However, finishing should not be a problem for anyone in this first programming assignment. If you can't finish this assignment, which is a simple "warm-up" exercise, you should seriously re-think your decision to take this course. The remaining assignments will all be considerably more challenging.)


Finding/Using Our Files

Files for CS 367 live in the directory /u/c/s/cs367-2/public/html. The three C++ files that we provide and the test data files, are in a subdirectory of this directory called assign1. You should make yourself a copy of the file that you will be modifying, intseq.c, in an Assignment-1 subdirectory of your home directory. To make a subdirectory for this purpose, go to the private subdirectory of your home directory (cd ~/private), create a subdirectory there (mkdir assign1), and cd to it (cd assign1). You can then copy the code file (cp ~cs367-2/public/html/assign1/intseq.c). For the other two files, you should create links to our files (e.g., ln -s ~cs367-2/public/html/assign1/intseq.h .) so that you will always be using the same definitions and initial test data files as everyone else.