Exercise Sheet 3b: Starting to list...

Aims

In this lab we:

1. introduce the datlab automatic code submission software,
2. download and practice using the DAT and Exceptions packages,
3. practice using the linked list covered in lectures,
4. create a variation of the Queue ADT presented in lectures for holding Strings.

1. Submitting your work to datlab

   The datlab system is an automated system that allows you to submit some of your solutions to the lab questions for checking and feedback. It is designed to allow students to make multiple submissions, so that you are able to find and correct your mistakes and gain full marks.

   To gain familarity with the system, this week's exercise requires that you submit your combination lock work from last week. You must submit four classes:

   • Lock.java
   • LockInt.java
   • LockString.java
   • Lock.html

   To access the system, follow the "Connect to datlab" link from the DSA home page. After entering your student number and PIN you should reach the main menu page which has a list of available labs and their deadlines, and options for viewing your marks to date and submitting a lab for marking.

   Choose "Submit a Lab for Marking". Select Lab 3 and press "Next". This should bring up the submission screen.

   Now click on "Choose File". This will bring up a file selection box. (On some browsers the file selection box by default this has a "*.html" filter. If so, change this to "*.*".) Change to the directory with your Java files and select Lock.java. You should now see that file's name in the "Filename" field. Press "Add Files" and you will see it inserted under "Selected Files For Lab 3". (If there is no response it may have timed out and you may have to return to the main page and start again.) Note that each time you choose a file, you must also press "Add Files" to add it to the submitted files.

   You might like to try submitting this file by pressing "Mark Lab" to see what happens. You should get a report saying that it couldn't find all the files required for this lab.

   Now try submitting again, and include each of the four required files. datlab will make some checks, and if successful, and submitted before the deadline, it will award you with 2 marks.

   Now return to the main page and select "View Your Marks". This should bring up a table with your marks for this lab, the number of submissions, and your total marks. Once you have finished, logout from the system.

   Resubmitting to Datlab

   The main aim of providing the datlab system is to give you quick feedback on your work, and allow you to use the information provided to improve your code. You are therefore allowed to resubmit to the datlab system as many times as you like. We hope that it will provide you with a valuable learning tool.

   Policy on Plagiarism

   The ability to resubmit as many times as you like is also provided to give you extra encouragement (in addition to the obvious learning benefits) to be self-reliant, rather than relying on others. The policy for datlab submissions is that you may discuss concepts with others as part of the learning process, but all code that you submit must be written, from scratch, by yourself. Note that all submissions to datlab are logged and checks will be carried out from time to time for similarities, including the use of sophisticated code analysis software. Cases of plagiarism will be treated extremely seriously.

   Important: This means that for assessed work you may not work on code together.

   Policy on Extensions

   It is intended that you submit work from labs in the week that they are set in labs. However, in order to allow for medical problems, and the difficulty of administering these on a weekly basis with a large class, everyone is automatically granted a one week extension. Further extensions will therefore only be granted where a doctor's certificate is produced showing that you are ill for both weeks, and not if you are only ill in the extension week. Once the deadline has passed, the datlab system will continue to check work. Within one working day of the deadline it will deduct one mark, and after that will automatically stop allocating points.

2. Using the DAT Package

   The following section provides practice using an ADT written by a third party, as well as increasing your familiarity with the linked list covered in lectures. It uses the LinkedListChar class, which is part of the DAT package.

   A package is a mechanism in Java for grouping together a collection of logically related classes. When you first open the Java API documentation you will see a list of all the packages included with Java.

   You can similarly view the documentation for the DAT package and other packages used on this course by following the DAT Package docs link from the DSA home page.

   Note that the source files for the classes you will be using below are intentionally not available as you are required to import them as "third-party" products, rather than compile them (and potentially alter them) yourself.

   To practice using the packages and the linked list we will create a simple program that stores the letters of your name. Create a project called MyName. Build the project once to create the subdirectories. Now follow the link DSA Java sources | Download Jar packages from the DSA web site. Download the files DAT.jar and Exceptions.jar. They should end up in your Downloads directory.

   The only difference between using a user-defined package such as the DAT package, and the built-in API packages, is that you must tell Java where to find user-defined packages. This is achieved using Java's CLASSPATH. There are different ways of doing this depending on which operating system you are using.

   Returning to your MyName project, open the build.xml file. Find the javac command in the "compile" target. Notice the argument classpathref. If you follow this back (you should be starting to get used to "reading" the Ant build file, but you can always refer back to the documentation for anything you don't understand) you can see that it is set up to include all the .jar files in the lib (short for "library") directory. (If you look in the target "jar" you will see that the these jar files also get included in the final distributed jar file.) The simplest way to include the third party jar files is therefore to place them in the lib directory.

   Place the DAT and Exception jar files in your project's lib directory.

3. Using a Recursive Data Structure - the LinkedListChar ADT

   As an example of using a class in the DAT package look up the on-line documentation for the class DAT.LinkedListChar. This tells you what methods are publicly available in that class (as covered in lectures).

   Now that Java knows where to find the DAT package, you can use the LinkedListChar class in your program by including, as the first line in your file, the command:

     import DAT.LinkedListChar;

   You will also need to import the Exceptions package, eg:

     import Exceptions.*;

   Use LinkedListChar in the following programs. Note that you can only use publically available methods (as described in its documentation.)
   1. Write a program (i.e. a class) MyName that creates a LinkedListChar, stores the letters of your name in it one by one (you don't need to enter your name from the terminal - you can "hardwire" it in the code for the purposes of this exercise), then prints the whole list out with a single command using System.out.println.

      • How does System.out.println know what to print? (Hint: It uses one of the publically available methods.)

      • If you stored your name starting with the first letter, it will come out backwards. Why is this? (Hint: Think about the way the linked list, as described in the lectures, is constructed.)

   2. Modify your program so that it stores the letters of your name in a LinkedListChar, then extracts the characters one at a time and prints them on separate lines. The latter should be done using a while-loop. (Note that this will destroy your list - don't worry about this for now.)

4. A Queue of Strings

   In the DSA Notes we examine a block representation of a character Queue ADT. The source for the ADT, QueueCharBlock.java and its documentation can be found by following the Java source and DAT package documentation links from the DAT page.

   In this exercise it is suggested you copy the source code and modify it. (Note that only selected source files in the DAT package can be downloaded.)

   Remember that the first line of the source code

     package DAT;
   

   defines this class as part of the DAT package. Your own modified class will not be part of the DAT package, and therefore you must remove this line. Remember also that if your program uses other classes in the DAT package (such as the QueueChar and QueueString interfaces) you need to tell Java where to find them by including the command:

     import DAT.*;
   

   • Copy QueueCharBlock and modify it to hold a queue of strings. Your new ADT, called QueueStringBlock should implement the QueueString interface (see the on-line documentation).

   • Test your new ADT by writing a small program PrimeMinisters containing the following code:

          q.enqueue("Fraser");
          q.enqueue("Hawke");
          q.enqueue("Keating");
          q.enqueue("Howard");
          q.dequeue();
          q.dequeue();
          q.dequeue();
          q.enqueue("Gillard");
          q.enqueue("Watson");
          person = q.examine();
          System.out.println("The Prime Minister is " + person);
     

     What happens when you initialise q to a block of only 5 items? (Test this.) What is this an example of?