CIS5100 - Data Structures and Programming (Java)

www.cs.fit.edu/~mmahoney/cis5100

Schedule

Aug. 22-Dec 16, 2005, Tuesdays, 5:15-7:45 PM, Crawford Science Tower room 523.

Topic

This course covers introductory programming in Java. Prior programming experience is not required. You will need a computer with a Java compiler.

Instructor

Matt Mahoney, mmahoney@cs.fit.edu or matmahoney@yahoo.com

Textbook

Java, How to Program, Deitel & Deitel, 6th Ed. We will cover approximately the first half of the book (chapters 1-10) this semester and the second half in CIS5200. The book comes with a CD that you won't need.

Introduction
Quick reference
Java Tutorials

Homework

All programming assignments must run under Java 1.4.2 or an earlier version. This is not the latest version, but it is the version installed on my.fit.edu and it is the latest version that will run on a PC with less than 512 MB memory or a version of Windows older than XP or 2000. Note that some programs in the book are written for Java 5.0 and will not run in 1.4.2 (e.g. using printf() or Scanner). You may use Windows (98 or later), Linux, Solaris, or Mac.

Grading Policy

50% homework and 50% exams. Programming assignments will be submitted by email only. Submit only source code (.java) preferably as ONE file. There is a late penalty of 20% per day including non-class days, weekends and holidays.

There will be 4 exams including the final. Your lowest grade is dropped. The other 3 exams are weighted equally. There are no makeup exams for any reason. Exams are open book and open notes. Exams will usually be given in the first hour of class before break so that we can go over them afterwards.

Attendance is not mandatory. However you are responsible for (and will be tested on) all material covered in class.

Students are expected to do their own work (no group projects) and to cite all outside sources, including help received from other students. You are responsible for knowing the policy on academic honesty, covered in the student handbook, p. 33.

Conflict Resolution

I normally answer email within 24 hours. In case of a conflict that cannot be resolved with me, resolution policy is covered in the student handbook, p. 55. The CIS program chair is Dr. Rhoda Baggs Koss, 321-223-4821, rkoss (at) fit.edu. Her office is on the 5th floor of the Crawford Science Tower.

Mailing List

Within 24 hours after the first class you should receive an email notifying you that you have been added to the fit-cis5100 mailing list. If you do not, then email me to request an invitation. You are responsible for all material posted to the list, such as homework assignments, test announcements, and additional course material. Once you are a member, you are encouraged to post questions (or answers) to the class at fit-cis5100@googlegroups.com. If you have a Google account you may also access the list at the members-only website groups.google.com/group/fit-cis5100.

Homework

Assignment 1

Due Fri. Sept 9, 2005, midnight (15 pts). Write a Java program, Average.java, that accepts one or more integer arguments, prints them, and prints their average (rounded down to an integer). For example:
  javac Average.java
  java Average 3 8 2 6
  The average of 3 8 2 6 is 4
If the program is run without arguments, then it should print a helpful error message.

Assignment 2

Due Fri. Sept 16, 2005, midnight (10 pts). Write a program, WordCount.java, which takes the name of a file as input, and prints the number of words in that file. A word is defined as any sequence of one or more consecutive letters, A-Z or a-z, and no other characters. For example:
  Hello world!            (2 words)
  e-mail                  (2 words)
  it's                    (2 words)
  2005                    (not a word)
  - - - - -               (0 words)
  U.S.A.                  (3 words)
  Win98                   (1 word)
The program should accept a file name as a command line argument. If there is no file name given, then the program should prompt the user to enter one. If the file does not exist, then print an error message. For example, if the above text was in a file called input.txt then:
  javac WordCount.java
  java WordCount input.txt
  input.txt has 10 words

  java WordCount
  Please enter a file name: input.txt
  input.txt has 10 words

  java WordCount foo
  File foo not found

Be sure to document (comment) your code so that someone unfamiliar with this assignment could still understand how to use your program.

Assignment 3

Due Wed. Oct 12, midnight (15 pts). Write a public class Temp (in file Temp.java) for converting between Fahrenheit and Celsius. Objects of type Temp can store a value representing a temperature. The class should have 4 public methods:
  setC(t)  // set temperature to t in Celsuis
  setF(t)  // set temperature to t in Fahrenheit
  getC()   // return temperature in Celsius
  getF()   // return temperature in Fahrenheit
All values are type double. The temperature should be represented internally using a private instance variable. All members should be non-static. It should work with the following program:

/* TestTemp.java takes 2 arguments, a number and a letter (C or F),
   separated by a space.  It interprets this value as a temperature
   (Fahrenheit or Celsuis) and then prints the temperature in
   both formats, for example:

     java TestTemp 32 F
     32.0 F
     0.0 C

     java TestTemp 100 C
     212.0 F
     100.0 C

     java TestTemp 70.5 F
     70.5 F
     21.38888888888889 C

   To compile: javac Temp.java TestTemp.java
*/    
   
public class TestTemp {
  public static void main(String args[]) {
    try {
      Temp temp = new Temp();  // you will write class Temp
      if (args[1].equalsIgnoreCase("F"))
        temp.setF(Double.parseDouble(args[0]));
      else if (args[1].equalsIgnoreCase("C"))
        temp.setC(Double.parseDouble(args[0]));
      else
        throw new Exception("Temperature must be F or C");
      System.out.println(temp.getF()+" F");
      System.out.println(temp.getC()+" C");
    }
    catch (Exception x) {
      System.out.println("Usage: java TestTemp (temperature) (F/C)\n"
        +"for example: java TestTemp 20 C");
    }
  }
}
Submit only Temp.java. I will test using the program TestTemp.java above. To write Temp.java should cut and paste this program into TestTemp.java for testing.

Assignment 4

Due Wed. Oct. 26, midnight (15 pts). First draft is due Fri. Oct. 21. The first draft will not be graded and does not need to work, but you must turn in something. This assignment is to create a Stack class representing a stack of integers. A stack is a data structure in which items are removed (popped) in the opposite order in which they are inserted (pushed). A stack is sometimes also called a LIFO (last in, first out). Your Stack class should have the following public methods:

  Stack(int size);   // A constructor specifying the number of elements it will hold
  void push(int x);  // Push x onto the top of the stack
  int pop();         // Remove an item from the stack and return its value
  boolean isEmpty(); // Returns true if there is nothing else to pop
  boolean isFull();  // Returns true if there is no room to push another item
For example:
  Stack s = new Stack(3);  // initially empty, will be full after 3 pushes
  s.push(10);
  s.push(20);
  s.push(30);  // stack is now full
  System.out.println(s.pop());  // 30
  System.out.println(s.pop());  // 20
  System.out.println(s.pop());  // 10
It is normally an error to push a full stack or pop an empty stack. I will leave it up to you how your class behaves under these condtions, but you MUST document your decision in the comments in your program. Some possible responses are to throw an exception, ignore the operation, pop a default value, print an error message and exit, etc.

Your program must work with TestStack.java below. See the comments for some test cases.


// TestStack.java - program to test the Stack class.
// To compile: javac TestStack.java Stack.java

public class TestStack {
  public static void main(String args[]) throws Exception {

    // Test a stack of size 5 by pushing numbers until full, then
    // popping and printing them until empty.  The numbers should
    // print in the reverse order in which they were pushed.

    Stack st = new Stack(5);  // create with room for 5 elements

    // push 1, 2, 3, 4, 5
    int i = 1;
    while (!st.isFull())
      st.push(i++);

    // pop, should print 5 4 3 2 1
    while (!st.isEmpty())
      System.out.print(st.pop()+" ");
    System.out.println();

    // Now push the command line arguments, then pop and print them.
    // The first argument is the size of the stack.  The remaining
    // arguments are integer values to be pushed either until the
    // last argument or the stack is full, whichever comes first.
    // For example,
    //
    //   java TestStack 3 10 20 30 40 50       (stack size is 3 in second test)
    //   5 4 3 2 1                             (from first test)
    //   30 20 10                              (from second test)
    //
    //   java TestStack 10 2 4 6 8             (stack in second test does not fill up)
    //   5 4 3 2 1
    //   8 6 4 2

    if (args.length >= 1) {
      st = new Stack(Integer.parseInt(args[0]));
      for (i=1; i<args.length && !st.isFull(); ++i)
        st.push(Integer.parseInt(args[i]));
      while (!st.isEmpty()) {
        int poppedValue = st.pop();
        System.out.print(poppedValue+" ");
      }
      System.out.println();
    }
  }
}
Submit only Stack.java. I will test with the above StackTest.java.

Assignment 5

Due Fri. Nov. 4, midnight (10 pts). Write Stack as a public interface with two implementations, ArrayStack and LinkedListStack. An ArrayStack should be implemented using an array and work like Stack in assignment 4. A LinkedListStack should use a linked list. It differs from ArrayStack in that the constructor takes no arguments, there is no maximum size, and isFull() always returns false. It should work with TestStack2.java below.
// TestStack2.java - program to test the Stack interface, and two
// implementations, ArrayStack and LinkedListStack.

public class TestStack2 {
  public static void main(String args[]) throws Exception {

    // Push the command line arguments, then pop and print them.
    // The first argument is either the size of an ArrayStack, or
    // 0 for a LinkedListStack.  The remaining
    // arguments are integer values to be pushed either until the
    // last argument or the stack is full, whichever comes first.
    // For example,
    //
    //   java TestStack 3 10 20 30 40 50         (ArrayStack with size 3)
    //   30 20 10
    //
    //   java TestStack 0 2 4 6 8                (LinkedListStack)
    //   8 6 4 2

    if (args.length >= 1) {
      Stack st;  // Stack is an interface (not a class)
      int size = Integer.parseInt(args[0]);
      if (size > 0)
        st = new ArrayStack(size);
      else
        st = new LinkedListStack();
      for (int i=1; i<args.length && !st.isFull(); ++i)
        st.push(Integer.parseInt(args[i]));
      while (!st.isEmpty()) {
        int poppedValue = st.pop();
        System.out.print(poppedValue+" ");
      }
      System.out.println();
      st.pop();  // fails
    }
  }
}

Submit only Stack.java, with all other classes defined non-public in this file. I will test with the above revised StackTest2.java. As usual, be sure to document your classes thoroughly, including behavior during errors. Where the behavior is the same, document the interface. Where they differ, document the implementations. Be sure the implementations are hidden from the user (other than the suggestive names). There is no requirement to submit an early draft, but it is still recommended.

Assignment 6

Due Sun. Dec. 11, midnight (35 pts). This is the final project. Write a program, WordCount.java, that reads a text file, then prints an alphabetical list of words found in that file along with the number of times that word occurs. Your program should compute the result by several different methods which the user may select. All methods should produce identical output. The methods are as follows: The three methods, heapsort, quicksort, and sortedlist are extra credit (5 points each). Be sure your program comments indicate which methods work and which don't.

A "word" is any sequence of one or more letters (a-z) and does not include any other characters such as apostrophes, hyphens, digits, spaces, etc. For example, "don't" is two words, "don" and "t". Differences in case should be ignored. For example, "This", "THIS", and "this" are all the same word.

WordCount.java should take two arguments: a file name and a method. The output should be in two columns separted by a tab. The first column is the number of occurrences (1 or more), and the second column is the word, written in lower case. The words should be listed in alphabetical order. For example, if file.txt contains:

  This is a test, and
  this is another test!!!
  TEST-TEST---TEST
then:
  java WordCount file.txt bubblesort
  1       a
  1       and
  1       another
  2       is
  5       test
  2       this
To solve the problem, define an interface as follows:
  interface WordCounter {
    public void addWord(String);  // add a word
    public void print();  // output as described above
  }
Write 6 implementations corresponding to each method. Each WordCounter should take lowercase strings and add them to a data structure. It might be used like this:
  WordCounter wc;
  if ( /* method is bubblesort */ )
    wc = new BubbleSorter();
  else if // for the 5 other user selected methods...

  while ( /* there are more words to read */ ) {
    // read next word
    // convert to lower case
    wc.addWord(word);
  }
  wc.print();
The implementations should work as follows: Note that addWord() is identical in four of the six classes. Thus, you may benefit from a 3 level class hierarchy.

Your program should use appropriate error handling (not enough program arguments, file not found, invalid method, etc), and good object oriented methodology. Submit only one source code file, WordCount.java.

Recommended progress reports (not graded, earlier is better):

Exam Solutions

Fall 2005
Exam #1
Exam #2
Exam #3
Final Exam