Class Notes: Data Structures and Algorithms

Summer-C 1999 - M WRF 2nd Period CSE/E119

Instructor: M.S. Schmalz -- TAs: TA Mailing List

Project 2 Assignment -- Final Version

This is the final version of the assignment for Project #2. An important difference between this version and the draft version is that you will not have to write your program output to a file. All that is required is that you read input from a file, as described below.

Recent updates are listed in red typeface, below. A link to a file reader written by Lloyd Noronha has been added below, and the deadline has been extended to midnight, to make the submission process easier.

Project 2 consists of writing a Java application that uses arrays as well as singly- and doubly-linked lists.

• Goal. The purpose of this project is to provide intermediate hands-on experience with Java programming for all COP3530 students, especially those who may be new to Java. The purpose of the application is to familiarize students with reading from a file, and especially with manipulation of sequences in arrays as well as singly- and doubly-linked lists.

  The program you develop as Project 2 will (a) read a sequence of integers from a file (instead of stdin as in Project 1), (b) store the sequence in an array, a singly-linked list, or a doubly-linked list, (c) reverse the input sequence,(d) output a header (shown in the example below) and the reversed sequence to the screen (not to a file as shown in the draft version of this assignment), (e) scramble the order of the sequence by swapping every third integer, and (f) write the scrambled sequence to the screen as in d). An example of input and output is shown below.

  When the TAs test the program, the numbers will be read in from a text file (input-file), and the command line will be as follows:

  java Proj2 switch input-file

  where switch is one of the following switches: -a for array, -s for singly-linked list, or -d for doubly-linked list. Also, input-file, a text file that you enter using a word processor, and which is stored on disk, will be opened by your Java program. Your program will read the input sequence from that file, then will close the file.

  More information about the test procedure is posted below under Example Test Procedure.

• Features. We will be making a modular program with object-oriented design and implementation, as well as Java file I/O, as follows.

• Functionality. The program implemented as a Java Class called Proj2 will perform the following steps:
  Step 1. Read input from an input file whose name is specified on the command line. The input file should be structured as a stream of integers, one per line. You should use a one-dimensional array (like the class you developed in Project 1) to store the input data for later processing. Array classes are described in Sections 3.3.3 and 4.1 of the text, as well as in Dr. Crummer's Java programming tutorial.

  Step 2. Reverse the input. For example, if the input is a sequence (11,22,33,44,55), then the reversed sequence will be (55,44,33,22,11). Open a text file as write-only and write the following header to the screen:

           your-name    your-SSN
           11 June 1999   COP3530-C99-Proj2
  

  Then, write the input and reversed sequences to the screen, ten integers per line. For example, if the input sequence is

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 

  then the screen will display the following information after the header, and separated from the header by two blank lines:

  Data Structure: Array
  
  Input Sequence:
       1   2   3   4   5   6   7   8   9  10 
      11  12  13  14 
  
  Reversed Sequence:
      14  13  12  11  10   9   8   7   6   5
       4   3   2   1
  

  Hint: You will want to develop a method that does this output function for each of the array, SLL, and DLL classes. Then, you can use this to generate output for each of the three sequences (input, reversed, and scrambled) that you must generate for each of the array, SLL, and DLL structures.

  Step 3. Scramble the reversed sequence, swapping every third integer. For example, if the reversed sequence is (6,5,4,3,2,1,0), then the scrambled sequence will be (3,2,1,6,5,4,0).

  Note: If the number of integers in the input sequence is not a multiple of six, then you should check to see that the last one to five integers in the input sequence are not scrambled. Hint: Think about this in terms of modulo arithmetic.

  Step 4. Write the reversed scrambled sequence to the screen, ten integers per line, like you did in Step 2. This is where the output method we discussed in Step 2 will be useful.

  Step 5. Build a class for a singly-linked list that has the standard ADT operations as discussed in Section 3.4 of the text. If you wish, you may adapt the code that Dr. Sahni used in the textbook. Then, repeat Steps 1-4 for the SLL.

  Hint: Reversing the sequence using the SLL will be tricky, since you cannot traverse backwards on the SLL. The brute-force way to do this is (1) get the n-th value by traversing the SLL to the end and output the value, (2) get the (n-1)th value by traversing the SLL to its (n-1)th internal node, then output that value and so forth, until you end up at outputting the value in the first node of the SLL. Exercise: Can you think of a more efficient way to do this?

  Step 6. Build a class for a doubly-linked list that has the standard ADT operations as discussed in Section 3.4.8 of the text. You will need to modify the class to include a pointer to the previous list element. Again, you may adapt the code that Dr. Sahni used in his textbook, if you wish. After you have built your DLL class, then repeat Steps 1-4 for the DLL. You will find it much easier to traverse the DLL, since you can move in either direction.

  Step 7. After you have tested and completed your program, use the submission procedure outlined below to submit your project.

  Example Test Procedure. Type up a text file "inFile" in either Dos or Unix with one value per line, like this:

  22
  36
  54
  14
  17
  65
  

  Now run your program this way:

  java Proj2 switch inFile

  where switch denotes the string -a, -s, or -d, as described previously.

  If the switch is -a, your sample output should look like this:

  
           John Smith      SSN: 123-345-6789
           11 June 1999    COP3530-C99-Proj2
  
           Numbers read in: 6
  
           Data Structure: Array
  
           Input Sequence:
           22  36  54  14  17  65
  
           Reversed Sequence:
           65  17  14  54  36  22
  
           Scrambled Sequence:
           54  36  22  65  17  14
  

  For the switch -s, the Data Structure line should read Singly-Linked List. For the switch -d, the Data Structure line should read Doubly-Linked List.

  Required Programming Procedure. Define each class in a separate .java file, with your master file as Proj2.java, where Proj2, which has a main method, is the class name that the TAs will use to run your program. (It is o.k. to have a main method in each class - the TAs are primarily interested in the main method in the Proj2 class.)

  Other Hints on Programming Procedure. Use the following steps to guide your implementation of the Java version of the preceding program.

  Hint 1. Get started early!!! Don't wait until the last two or three days, especially if you have not had much Java programming experience.

  Hint 2. Decide what classes you will use (Hint: An Array or Vector object might be useful, with Reader class or objects, System class, etc.) Also, it is strongly suggested that you adapt Dr. Sahni's classes as shown in the text, to avoid undue programming effort. After you have figured out what classes and objects to use, design your Java class specification(s) on paper. Then (and only then) should you start coding.

  Hint 3. Code your class(es) and methods, testing them incrementally (i.e., one at a time). Get each one working before you go on to the next one. If you write your program all in one blob of code, you will assuredly have difficulty debugging it.

  To make your code execution dependent on the command-line switch, use the following code:

  if args[0].equals("-a") {
    -- execute your array code
  }
  else if args[0].equals("-d") {
    -- execute your sll code
  }
  else if args[0].equals("-l") {
    -- execute your dll code
  }
  

  The construct args[] is an instance of a one-dimensional array of type String.

  Hint 4. Try your program on different kinds of output (e.g., large and small inputs, with both negative and positive integers. If your code breaks, fix it until it works on all inputs.

  Hint 5. File I/O may be performed in one of several ways:

  1. Use the Input class that Dr. Bermudez or Dr. Sanders supplied in your Java programming course. Pass the input filename from the command line to the class, and use the method for reading integers.

  2. Instead of using the Input class from the Java course, you should use the file reader code from Lloyd Noronha's Web page, of which he has requested that you be informed. The TAs would like you to use the code available at the above-listed link. You should modify their code to work on both negative and positive integers.

     For background purposes, the following code for a buffered reader is given. Using code like this, one could pass the input filename to the main method, and open the input file for reading using code similar to the following, where number denotes the input integer and line denotes the line on the input file fileName that contains the input integers:

     String fileName, line;
     int number;
     int count = 0;
     fileName = (get this from the argument list of Proj2);
     BufferedReader input;
     input = new Buffered Reader (new FileReader(fileName));
     line = input.readLine();              // Read a line of characters
     while (line != null)                  // File is terminated by a null
     {
        number = Integer.parseInt(line);   // Change to an integer
        count++;                           // Increment number of integers read
        line = input.readLine();           // Read next line 
     }
     

     Notice that input is declared to be an object of class Buffered Reader. If the opening operation is not successful, then program execution will be stopped. We say that this class throws an I/O exception. Thus, the line of code:

     throws IOException

     must be added to the header of your main method.

     The BufferedReader class is part of the java.io package. To use the class (and the other file reading and writing classes in java.io), the package must be imported into the class. This is done by adding the line:

     import java.io.*

     to the other import statements in the class. Refer to the Project #1 description to see how to do this.

     As described previously, each integer is recorded as a line of characters in the input file. Each line is parsed and converted to an integer by the statement:

     number = Integer.parseInt(line);

     Also, note that reading and writing to a file is similar to using the Java standard input and output System.in and System.out.

  3. Alternatively, you may have a favorite file I/O class that you wish to use. Feel free to do so, as long as: (a) you document what the code is supposed to do, in case there are problems, and (b) you test your code thoroughly on various inputs.

  Hint 6. The TAs are here to help you with your problems. We have scheduled office hours throughout the week, with the exception of Friday, when the instructor and TAs will be working on grading homework assignments. Please feel free to ask the TAs any questions about your Java program.

  Documentation. Illustrate your program with in-line comments, so the TAs know what you are doing. Consult your textbook and other Java programming references provided on the course Web page and elsewhere (e.g., Java books in library) for style guides.

• Evaluation. Maximum score = 100 points, as follows:

    CODE PRESENT & CLEAR                              10 points max.
    For each of the Array, SLL, and DLL classes:
      In-line Comments & Documentation   5 points max.
      Code compiles correctly            5 points max.
      File I/O works correctly           5 points max.
      Input integers counted correctly   5 points max.
      Sequence reversed correctly        5 points max.
      Sequence scrambled correctly       5 points max.
    TOTAL POINTS PER CLASS = 30 x 3 CLASSES           90 points max.
    ----------------------------------------------------------------
    TOTAL POINTS                                     100 points max.
  

  For example, if you have only 60 percent the code needed, and it doesn't compile and isn't documented, you would get three of the five points allocated for the code being present. If the code is present, well documented, compiles, reads in data, and reverses the sequence correctly with correct output (but doesn't do anything else), then you could get as many as 20 points per class that had the preceding characteristics.

• Submission Procedure. Please submit only your *.java files. You must be logged in to your CISE account to perform the submission procedure, which is described in detail at this link.

  In summary, type in the following commands within your directory to submit all the java files for Project-1:

  turnin -c cop3530 -p proj2 *.java {Return}

  where {Return} denotes the carriage return key.

  Important Note: In case you have developed your programs on any environment other than the CISE Unix system, please test your program on a CISE Unix machine before submission. We will only be testing programs for grading purposes on the CISE Unix machines.

• Due Date. Submit the completed project by MIDNIGHT on Friday 11 June 1999. Projects submitted a day late will be penalized -10%; two days late: -20%, three days late: -30%, and four days late: -40% . Projects turned in more than four days late will not be accepted unless accompanied by a documented excuse (e.g., note from your physician or advisor).

This concludes the description of Project #2. Use the E-mail link at the top of this Web page to ask the TAs, if you have any questions about programming or grading.