CSCE 145

Rate This Professor

2010-04-09T09:32:00.001-04:00

I thought I would put up this post so students that took this class last Fall could add their comments for the benefit of those who will be taking it this Fall and for my own benefit. The reviews I got for the last class included the usual complaints:

"Tests were graded very harsh" Yes, you can see for yourself the point values for the final test. But points are not grades, the final letter grade for the class is based on a curve.
"challenging". Yes. More specifically, learning to program takes a lot of time. Be prepared to put in many hours in front of the computer.
"this should not be a requirement for Math/EE/x majors". That's out of my control. Still, ability to program comes in handy when you want to find a job.

The goal of this class is for every student to leave with basic programming skills. For example, look at question 1 in our final test. Every student who passes 145 should be able to write that program. To do so the student needs to know about variables, string manipulation, loops, and how to put all these together to get it done. These are just some of the basic skills students learn. You can take a look at the textbook to see all the topics we cover.

So, if you have taken this class and have some suggestions for me or future students on how to achieve this goal, please leave a comment.

Final Averages

2009-12-13T10:33:00.001-05:00

Below is the grade distribution for the final test. Some students did not show up for the final, thus the 0 grades.

The final grade distribution for the whole class is:

You will be receiving you final grade shortly.

Final Test

2009-12-11T17:05:00.026-05:00

145 Final Test

(10%) Implement a method which takes as input two Strings and returns one String which is formed by interleaving the two arguments. Assume that the two input strings have the same length. For example, if given the input

"abcde"
"12345"

then it should return a String with the value:

"a1b2c3d4e5"

Answer:

  /**
   * Interleaves the letters of first and second. Assumes that first and second have the same length.
   * @return the interleaved string
   */
  public static String interleave(String first, String second){
    String result = "";
    for (int i =0; i < first.length(); i++){
      result += first.substring(i, i+1) + second.substring(i,i+1);
    }
    return result;
  }

(10%) Implement a method that takes an array of long values representing phone numbers and prints out how many of those phone numbers are in Columbia (803), Greenville (864), and Charleston (843). You must use a switch statement in your method.
For example, if we call your method with the following array n as input:

long[] n = {8031234567l, 8649878787l, 8031223456l, 8034543212l, 8642323214l, 8432341231l};

you will print out:

Columbia:3
Greenville:2
Charleston:1

Answer:

  public static void countAreaCodes (long[] phoneNumber){
    int columbia = 0;
    int greenville = 0;
    int charleston = 0;
    for (int i =0; i < phoneNumber.length;i++){
      int areaCode = (int) (phoneNumber[i] / 10000000);
      switch (areaCode) {
      case 803: 
        columbia++;
        break; //Don't forget the breaks!
      case 864:
        greenville++;
        break;
      case 843:
        charleston++;
      }
    }
    System.out.println("Columbia:" + columbia);
    System.out.println("Greenville:" + greenville);
    System.out.println("Charleston:" + charleston);
  }

(10%) What does the following program print out?

public class Enigma {
  
  private static int x;
  
  protected String s; 
  
  public Enigma(int x, String s){
    System.out.println("Creating an Engima");
    this.x = x;
    this.s = s;
  }
  
  public void addItUp(int z){
    x = x + z;
  }
  
  public void merge(Enigma e){
    s = s + "+" +  e.s;
  }
  
  public String toString(){
    return "s=" + s + " x=" + Integer.toString(x);
  }

}

public class Mystery extends Enigma {
  
  private int y;
  
  public Mystery (int x, int y, String s){
    super(x,s);
    System.out.println("Creating a Mystery");
    this.y = y;
  }
  
  public void addItUp(int z){
    y = y + z;
  }
  
  public String toString(){
    return super.toString() + " y=" + Integer.toString(y);
    
  }
  
}

public class Paradox extends Mystery {

  public Paradox(int x, int y, String s) {
    super(x, y, s);
    System.out.println("Creating a Paradox");
  }
  
  public void merge (Paradox p){
    s = "Do not cross the paradoxes!";
  }
}

public class Main {

  public static void main(String[] args) {
    Paradox p = new Paradox (5,10,"This sentence is false");
    Enigma e = new Enigma(33, "Black hole");
    System.out.println(p);
    System.out.println(e);
    e.merge(p);
    System.out.println(e);
    p.merge(p);
    System.out.println(p);
    e.merge(p);
    System.out.println(e);
    p.addItUp(100);
    System.out.println(p);
    Enigma e2 = (Enigma)p;
    e2.addItUp(500);
    System.out.println(e2);
  }
}

Answer:

Creating an Engima
Creating a Mystery
Creating a Paradox
Creating an Engima
s=This sentence is false x=33 y=10
s=Black hole x=33
s=Black hole+This sentence is false x=33
s=Do not cross the paradoxes! x=33 y=10
s=Black hole+This sentence is false+Do not cross the paradoxes! x=33
s=Do not cross the paradoxes! x=33 y=110
s=Do not cross the paradoxes! x=33 y=610

(10%) A diagonal matrix is a 2-dimensional square array of integers where the numbers on the diagonal are all 1 and the rest are 0. For example, the following is a 1x1 diagonal matrix:
```
1
```
and this is a 4x4 diagonal matrix:
```
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
```
Implement a method that takes an integer n and returns an n x n array of integers that is a diagonal matrix.
Answer:
```
  public static int[][] makeDiagonalMatrix (int size){
    int [][] result = new int[size][size];
    for (int i = 0; i<size; i++ ){
      result[i][i] = 1;
    }
    return result;
  }
```
(10%) Implement a class called Tracker which keeps track (in variables) of
1. how many times each instance's toString() method has been called
2. the total number of times all instances of the class have had their toString() invoked.
Answer:
```
public class Tracker {
  
  private static int totalCount = 0;
  
  private int count;
  
  public Tracker(){
    count = 0;
  }
  
  public String toString() {
    count++;
    totalCount++;
    
    return "";
  }
}
```
(10%) Implement an Exception called SilentException such that a we do not have to place within a try.catch block a method that throws SilentException.
Answer:
```
public class SilentException extends RuntimeException {
}
```
(10%) Implement a method that calculates the shipping and handling costs of an Order, which has methods (these exists, you don't have to write them):
1. boolean oversized(): returns true if this order is for an oversized item.
2. CARRIER getCarrier(): where CARRIER is defined as enum CARRIER {UPS, FEDEX, USPS}, returns the carrier. (A carrier is a company that ships packages. UPS, FEDEX, and USPS are the names of three different carrier companies.)
3. boolean rush(): return true if this a rush order.
The method you will implement is called double getShippingCosts(Order o) and it will calculate the the shipping and handling costs. The shipping costs for the different carries are given in this table:

UPS
FEDEX
USPS

Regular
$10
$12
$9

Oversized
$15
$22
$9

The is also a standard handling fee of $4 for all packages. Also, if it is a rush order then you must add an extra 10% to the regular shipping costs.
Answer:
```
  public static double getShippingCosts(Order o){
    double basePrice = 0;
    switch (o.getCarrier()) {
    case UPS:
      if (o.oversized())
        basePrice = 15;
      else 
        basePrice = 10;
      break;
    case FEDEX:
      if (o.oversized())
        basePrice = 22;
      else
        basePrice = 11;
      break;
    case USPS:
      basePrice = 9;
    }
    if (o.rush())
      basePrice = basePrice * 1.10;
    basePrice += 4;
    return basePrice;
  }
```

	UPS	FEDEX	USPS
Regular	$10	$12	$9
Oversized	$15	$22	$9

(15%) Implement a method that takes a String input which represents a DNA sequence and returns the index of the start of longest string of 'A' letters in the sequence. If there are no A's then return -1. For example,

given input "ACTAAAGA" you return 3,
given input "AAAAGA" you return 0,
given input "CTGATTAAAA" you return 6,
given input "CTG" you return -1

Answer:

  /**
   * This solution is good enough for 145*/
  public static int longestRepeatA(String dna){

    int longestIndex = -1;
    int longestCount = 0;
    for (int i =0; i < dna.length(); i++){
      int lengthA = 0;
      while (i + lengthA < dna.length() && dna.charAt(i+lengthA) == 'A'){
        lengthA++;
      };
      if (lengthA > longestCount){
        longestCount = lengthA;
        longestIndex = i;
      }
    }
    return longestIndex;
  }

  /** More experienced developers realize that the above is O(N^2) and that 
   * there is a way to implement it in linear time, like this: */ 
  public static int longestRepeatB(String dna){
    int longestIndex = -1;
    int longestCount = 0;
    int count = 0;
    for (int i = 0; i < dna.length(); i++){
      if (dna.charAt(i) == 'A') {
        count++;
      }
      if (count > longestCount) {
        longestCount = count;
        longestIndex = i - count + 1;
      }
      if (dna.charAt(i) != 'A'){
        count = 0;
      }
    }
    return longestIndex;
  }

(15%) Implement a method that calculates the average of an array of grades after first dropping the lowest 4 grades. That is, implement:

double getAverageDropFourLowest(double [] grade)

Assume that grades.length >= 5. For example, when given

double[] grade = {100,0,0,0,5,80,90};

as input, your method should return

90.0

Alert: Notice that this has to work when the lowest grades match, like in the example above where 3 of them where 0.

Answer:

  /** Returns an an array identical to grades but without the lowest number in grades dropped.
   * if there are more than one minimum we only drop the first one.
   * @param gradesthe array of grades
   * @return a new array of size 1 less than grades.
   */
  public static double[] dropMin(double [] grade){
    double minval = grade[0];
    double[] result = new double[grade.length - 1];
    for (double i : grade){
      if (i < minval)
        minval = i;
    }
    int j = 0; //index into result
    for (int i = 0; i < grade.length; i++){
      if (j < i){ //already dropped min, so just copy the rest of the array
        result[j++] = grade[i];
      }
      else if (grade[i] > minval) { //not the min
        result[j++] = grade[i];
      }
      //if j==i and grades[i] == minval we do nothing, so i increases while j stays the same, 
      // thus ignoring this grade[i]        
    }
    return result;
  }
  
  /** Returns the average after dropping the lowest 2 grades. */  
  public static double getAverageDropFourLowest(double [] grades){
    double[] g = FinalTest.dropMin(grades);
    g = FinalTest.dropMin(g);
    g = FinalTest.dropMin(g);
    g = FinalTest.dropMin(g);
    
    double sum = 0;
    for (double i : g){
      sum += i;
    }
    return sum / (double) g.length;
    
  }

Screencasts: kinda useful

2009-12-04T18:00:00.004-05:00

The result of my little screencast survey thus far is:

Were the screencasts useful to you?

So, slightly more useful than not. Most of the people who did not find them usefull did not leave comments. But, one did express a preference for textbook. I too prefer to learn new programming languages by sitting back with a book, so I definitely sympathisze.

Someone else pointed out that he could not ask me a question when he got to a part he did not understand and would forget by the time class came around. In class I suggested students should send me a quick email (or IM) when they came across some part of the video that confused them and I would answer these in class, but I only received a couple of emails during the semester.

Someone who liked them felt it is good to actually see things getting done. This is why I like watching screencasts of, say, using the Google App Engine, and I thought more students would mention it. But only one did.

In any case, the survey is still open so fill it out if you haven't! The graph above will automatically update to show your vote. Isn't software wonderful!

Grade Distributions

2009-12-03T09:31:00.002-05:00

The grade distribution for Test 3 is:

The grade distribution of the weighted average of all grades so far (that is, the grade you would get if there was no final) is:

And, one final correlation graph:

Were the Screencasts useful to You?

2009-12-02T10:13:00.004-05:00

This semester, for the first time, I did screencasts (videos) for each chapter in the textbook. Could you please fill out the survey below so I can gauge how useful they were to students. Thanks! (Remember to click on the submit button when you are done.)

Loading...

Final Exam Practice Questions

2009-12-02T10:06:00.000-05:00

As mentioned in class, the final is on Friday December 11 @ 2:00pm (to 5:00pm) in our classroom. It will be just like all the other tests: open book, no computers. The test will focus a bit more on the first chapters as these deal with the basic of all programming languages: variables, loops, methods, arrays, etc. Below are links to some practice questions. I also recommend you do all the programming exercises from the textbook. Like I said the first day, the only way to learn to program is by programming, a lot. Have fun with these!

Write a method that finds a given number in a sorted array.
Write a method that returns an array with the first n Fibonnaci numbers.
Write a method that takes as input a 3x3 array of integers and returns true if that array is a magic square.
Implement a simple 1-dimensional automata.
Once your 1D automata works, try working an a simple 2D automata.
Write a method that prints out a simple distribution graph.
Implement a class that limits the number of instances of itself to 4.
Write a method that reverses an array in place.

Lab test 3 for Section 006

2009-12-01T15:36:00.003-05:00

Write a program to implement a simple selling machine.

Each instance of the selling machine can hold 10 items using ArrayList. Partial program is given and you need to finish all the methods. You can add new items to the selling machine and get items from it if there is one. You need to implement a method to save the selling record (date & item name) to a file. You can use the Exception class for exception handling.

In this lab test, we only consider one type of the items, the Drink class. Code is given.

Please check your email box for the codes.

Test 3

2009-12-01T14:00:00.004-05:00

145 Test 3: Fall 2009

(20%) What does the following program print out?

public class MyExceptions {

  public int trySomething(int x) throws Exception{

    if (x < 0) {
      throw new Exception("X is less than 0");
    }
    return 5;

  }


  public static void main(String[] args){
    MyExceptions m = new MyExceptions();
    try {
      System.out.println("Starting");
      int result = m.trySomething(10);
      System.out.println("Got " + result);
      result = m.trySomething(- 10);
      System.out.println("Got " + result);
      System.out.println("No more tries");
    }
    catch (Exception e){
      System.out.println(e.getMessage());
    }
    System.out.println("Done");
  }

}

Answer:

Starting
Got 5
X is less than 0
Done

(10%) In the program above, what would happen with we removed the whole catch block? Would the program compile or not? If you think it would not compile then explain what the compiler complains about. If you think is would compile then show what the program would print out when run.

Answer: It does not compile. You cannot have a try without a catch.
(10%) Implement a class called Employee, with data members String name and int salary. Make sure that instances of your Employee can be written out to a binary file. But, do not write the code to write instances to a file, just make sure that instances of Employee can be written out to a binary file.
Answer:
```
public class Employee implements Serializable {

  private String name;
  private int salary;

  /** Add other methods, as needed. */

}
```

(20%) Given the following text file, called data.txt:

123432
3.14151
Ringo

write a program that reads those three values from the text file into an integer, double, and string variables, respectively.

Answer:

import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;

public class ReadFile {

  public static void main (String[] args){

    String fileName = "data.txt";

    try {
      Scanner inputStream = new Scanner(new File(fileName));
      int i = inputStream.nextInt();
      inputStream.nextLine();
      double d = inputStream.nextDouble();
      inputStream.nextLine();
      String s = inputStream.next();
      System.out.println("i=" + i + "\nd=" + d + "\ns=" + s);
    }
    catch (FileNotFoundException e){
      System.out.println("File Not Found");
    }
  }

}

(20%) A fast way of finding the greatest common divisor (gcd) of two numbers x and y is by using the following recursive definition of gcd(x,y):

the gcd(x,y) is equal to the gcd of y and x%y,
the gcd(x,0) is equal to x.

Implement a recursive function that calculates the greatest common division of any two integers.

Answer:

public class GCD {

  /** Calculate the greatest common division, using the recursive function:
      gcd(x,y) = gcd(y,x%y)
      gcd(x,0) = x  */
  public static int gcd (int x, int y){
        if (y == 0)
          return x;
        return GCD.gcd(y, x%y);
  }

  public static void main (String[] args){
    System.out.println(GCD.gcd(10,5));
    System.out.println(GCD.gcd(10,1));
    System.out.println(GCD.gcd(8,6));
    System.out.println(GCD.gcd(121,11));
  }


}

(20%) The following program contains two compile-time errors. What are they?

import java.util.ArrayList;

public class Test<Type, E>{

  private ArrayList<Type> list;

  private ArrayList<E> another;

  public Test(){
    list = new ArrayList<E>();
    another = new ArrayList<E>();
  }

  public Type badFunction(E x, Type t){
    E y = x;
    Type tt = t;
    list.add(t);
    another.add("Alice");
    Test<String,String> justMe = new Test<String,String>();
    justMe.add("Bob", "Charlie");
    return tt;
  }

}

Answer:

The line
```
list = new ArrayList<E>();
```
is wrong because the type E should be Type as per the declaration of list.
The line
```
another.add("Alice");
```
because we cannot assume that the type of another will be ArrayList<String>.

SECTION 005: Lab test 03

2009-12-01T14:00:00.003-05:00

The Towers of Hanoi is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:

1. Only one disk may be moved at a time.

2. Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.

3. No disk may be placed on top of a smaller disk.

Below you will find a partial implementation of a Tower of Hanoi with two methods missing: getHeight and hanoi. For this test you will implement these methods.

--- the start Pole, destination Pole and the intermediate Pole are labeled A, B, C.

--- Each disk is labeled (from 1 to the n, n is the height of the tower)

--- Disk 1 is the smallest disk, and Disk n is the largest one.

Hint : The idea is that the method of moving n disks from start pole to destination pole is the same as the method of moving n-1 disks. For example, initially the tower has height 5, we must recursively move a tower of height 4 from A to C, move the biggest disk 5 from A to B (by simply calling method moveDisk), and finally recursively move the tower of height 4 to B from C.

public class HanoiTower {
 
static int moves = 0;  //number of moves so far

/*Method getHeight is used to get the height of tower from user input*/
static int getHeight()
{
   // TO DO
      
}

/*Method hanoi moves the tower of height n recursively
 * it accept four arguments: the height of the current tower n, the fromPole, the toPole and the withPole.
 * @param n the height of the current tower
 * @param fromPole the start pole
 * @param toPole the destination pole
 * @param withPole the intermediate pole
 * */
static void hanoi(int n, char  fromPole, char  toPole, char  withPole)
{
   // TO DO
}

/*Method moveDisk move the disk of diskLabel by simply printing on the console each move*/
static void moveDisk(int diskLabel, char fromPole, char toPole)
{
     moves++;
     System.out.println("steps: "+ moves);
     System.out.println("Move " + diskLabel + " from " + fromPole + " to " +toPole);
}

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub

    int TowerHeight;
    char FromPole='A', ToPole='B', WithPole='C';

    System.out.println("Please Enter Tower height...");

    TowerHeight = getHeight();

    hanoi(TowerHeight, FromPole, ToPole, WithPole);


}

}

Here is the output of height of 3 after you properly implement the methods:

Please Enter Tower height...

steps: 1

Move 1 from A to B

steps: 2

Move 2 from A to C

steps: 3

Move 1 from B to C

steps: 4

Move 3 from A to B

steps: 5

Move 1 from C to A

steps: 6

Move 2 from C to B

steps: 7

Move 1 from A to B

Notes:

Submit your HanoiTower.java file to espiggy@gmail.com before 4:00pm. No late submission accepted!

Lab 22

2009-11-19T13:20:00.009-05:00

Question 8 on Page 850.

Hint:

here is the code of class Spices .


import java.util.Scanner;

/**
 Class for data on endangered species.
*/
public class Species
{
    private String name;
    private int population;
    private double growthRate;

    public void readInput( )
    {
        Scanner keyboard = new Scanner(System.in);
        System.out.println("What is the species' name?");
        name = keyboard.nextLine( );

        System.out.println(
                      "What is the population of the species?");
        population = keyboard.nextInt( );
        while (population < 0)
        {
            System.out.println("Population cannot be negative.");
            System.out.println("Reenter population:");
            population = keyboard.nextInt( );
        }

        System.out.println("Enter growth rate (% increase per year):");
       growthRate = keyboard.nextDouble( );
    }

    public void writeOutput( )
    {
         System.out.println("Name = " + name);
         System.out.println("Population = " + population);
         System.out.println("Growth rate = " + growthRate + "%");
    }

    /**
     Precondition: years is a nonnegative number.
     Returns the projected population of the calling object
     after the specified number of years.
    */
    public int predictPopulation(int years)
    {
  int result = 0;
        double populationAmount = population;
        int count = years;
        while ((count > 0) && (populationAmount > 0))
        {
            populationAmount = (populationAmount +
                          (growthRate / 100) * populationAmount);
            count--;
        }
        if (populationAmount > 0)
            result = (int)populationAmount;
 
        return result;
    }

    public void setSpecies(String newName, int newPopulation,
                           double newGrowthRate)
    {
        name = newName;
        if (newPopulation >= 0)
            population = newPopulation;
        else
        {
            System.out.println("ERROR: using a negative population.");
            System.exit(0);
        }
        growthRate = newGrowthRate;
    }

    public String getName( )
    {
        return name;
    }

    public int getPopulation( )
    {
        return population;
    }

    public double getGrowthRate( )
    {
        return growthRate;
    }

    public boolean equals(Species otherObject)
    {
        return (name.equalsIgnoreCase(otherObject.name)) &&
               (population == otherObject.population) &&
               (growthRate == otherObject.growthRate);
    }
}

Here is the code from Listing 12.5 on Page 821.



public class StringLinkedListSelfContained
{
    private ListNode head;

    public StringLinkedListSelf( )
    {
        head = null;
    }

    /**
     Displays the data on the list.
    */
    public void showList( )
    {
        ListNode position = head;
        while (position != null)
        {
            System.out.println(position.data);
            position = position.link;
        }
    }

    /**
     Returns the number of nodes on the list.
    */
    public int length( )
    {
        int count = 0;
        ListNode position = head;
        while (position != null)
        {
            count++;
            position = position.link;
        }
        return count;
    }

    /**
     Adds a node containing the data addData at the 
     start of the list.
    */
    public void addANodeToStart(String addData)
    {
        head = new ListNode(addData, head);
    }

    /**
     Deletes the first node on the list.
    */
    public void deleteHeadNode( )
    {
        if (head != null)
            head = head.link;
        else
        {
            System.out.println("Deleting from an empty list.");
            System.exit(0);
        }
    }

    /**
     Sees whether target is on the list.
    */
    public boolean onList(String target)
    {
        return find(target) != null;
    }

    // Returns a reference to the first node containing the
    // target data. If target is not on the list, returns null.
 private ListNode find(String target)
    {
  boolean found = false;
        ListNode position = head;
        while ((position != null) && !found)
        {
            String dataAtPosition = position.data;
            if (dataAtPosition.equals(target))
    found = true;
   else
    position = position.link;
        }

        return position;
    }

    public String[] toArray( )
    {
        String[] anArray = new String[length( )];

        ListNode position = head;
        int i = 0;
        while (position != null)
        {
            anArray[i] = position.data;
            i++;
            position = position.link;
        }

        return anArray;
    }

    private class ListNode
    {
        private String   data;
        private ListNode link;
  
        public ListNode( )
        {
            link = null;
            data = null;
        }
  
        public ListNode(String newData, ListNode linkValue)
        {
            data = newData;
            link = linkValue;
        }
    }
}

Homework 8 Solution

2009-11-17T12:30:00.016-05:00

Below is my solution for the Binary Search Tree:

public class BinarySearchTree {

 private BinarySearchTree left;
 
 private BinarySearchTree right;
 
 private int data;
 
 public BinarySearchTree() {
  left = null;
  right = null;
 }
 
 /** Create a tree that consists of just one node with no children. */
 public BinarySearchTree(int data) {
  left = null;
  right = null;
  this.data = data;
 }
 
 /** Adds new number n to this BinarySearchTree, placing it in its correct place.
  * 
  * @param n the number to be added
  */
 public void add (int n) {
  if (n <= data) {
   if (left != null) 
    left.add(n);
   else 
    left = new BinarySearchTree(n);
  }
  else { // n > data
   if (right != null) 
    right.add(n);
   else 
    right = new BinarySearchTree(n);
  }
 }
 
 /** Returns the maximum number in this tree. */
 public int max() {
  if (right == null)
   return data;
  return right.max();
 }
 
 /** Returns the height of this tree. */
 public int height() {
  //The base cases are when a child is null.
  return 1 + Math.max((left == null ? 0: left.height()), 
       (right == null ? 0: right.height()));
 }
}

Homework 9: Sets

2009-11-17T12:30:00.013-05:00

For this homework you will implement a simple generic Set class. That is, you will implement a class Set<T> using Java's ArrayList as the data member that holds the values.

A set is defined as a collection of elements (in our case, all of the same type) such that every element appears at most once in the collection. The methods your Set<T> must implement are:

Set() the constructor takes no arguments and creates an empty set.
String toString() returns a string with all the elements of this set in printed form, as usual.
void add(T x) adds element x to the set. If x is already in the set then it does nothing.
boolean contains(T x) returns true if the set contains the element x, false otherwise.
void add(Set<T> other) adds the complete contents of the set other to this set.
void subtract(Set<T> other) removes every element of other that is in this set.
boolean isSubset(Set<T> other) returns true if and only if this set is a subset of other, that is, if all the elements in this set are also contained in other.

You will also implement some test cases in your main() to ensure that your class works correctly. This homework is due on Tuesday, November 24 @noon.

Lab 21

2009-11-17T12:17:00.001-05:00

Question 1 on Page 849.

Lab 20

2009-11-12T13:18:00.003-05:00

Given an array of unsorted integers, implement a recursive method to find the minimal value.

Input: 3, 7, 12, -3, 6, 0, -1, 23

Output: -3

(Hint: you can refer to the merge sort as listing 11.7)

Chapter 12: Generics

2009-11-12T10:42:00.000-05:00

Below is the screencast for Chapter 12 which talks about generics. The chapter also covers dynamic data structures but we will not be focusing on those, so you can skip those sections if you want, or you can read them and be ready for CSCE 146.

CSCE 145: Chapter 12 from Jose Vidal on Vimeo.

You should watch the screencast before class on Tuesday, November 17. Here are the slides from the textbook:

Homework 7 Solution

2009-11-10T13:30:00.001-05:00

Below is my solution for the Field Notebook homework:

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.Date;
import java.util.Scanner;


public class Notebook {

 private Reading[] reading;

 private int nextIndex = 0;

 /** Maximum number of readings. */
 private static final int SIZE = 100;

 public Notebook(){
  reading = new Reading[SIZE]; 
 }

 /**
  * Creates a notebook by reading its contents from the given file.
  * @param filename
  * @throws IOException
  */
 public Notebook(String filename) throws IOException {
  try {
   ObjectInputStream input = new ObjectInputStream (new FileInputStream(filename));
   nextIndex = input.readInt();
   reading = (Reading[])input.readObject();
   input.close();
  }  catch (ClassNotFoundException e) {
   System.out.println("ERROR: File corrupted.");
   e.printStackTrace();
  }
 }

 /**
  * Adds a reading to the notebook
  * @param species name of the species
  * @param count how many you saw
  * @param comment 
  * @throws Exception if the notebook gets too big
  */
 public void addReading(String species, int count, String comment) throws Exception{
  //The right thing to do is use a data structure that expands as needed, but that's CSCE 146
  //  so we just crash.
  try {
   if (nextIndex >= SIZE) 
    throw new Exception("Too many readings!");
   reading[nextIndex] = new Reading(new Date(), species, count, comment);
   nextIndex++;
  }
  catch (NegativeCountException e) {
   System.out.println("Sorry, no negative animals allowed.");
  }
 }

 public String toString(){
  String result = "";
  for(int i=0; i< nextIndex; i++){
   result += reading[i].toString() + "\n";
  }
  return result;
 }

 /**
  * Write this notebook out to a file. It can be read back using the constructor.
  * @param filename name of the file
  * 
  */
 public void writeToFile(String filename) {
  try {
   ObjectOutputStream out = new ObjectOutputStream( new FileOutputStream(filename));
   out.writeInt(nextIndex);
   out.writeObject(reading);
   out.close();
  } catch (FileNotFoundException e) {
   System.out.println("ERROR: No such file. Did not write.");
  } catch (IOException e) {
   System.out.println("ERROR: IO. Did not write to file.");
  }
 }

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

  Scanner keyboard = new Scanner(System.in);
  Notebook notebook = new Notebook();


  while (true){
   System.out.println("Command list: \n");
   System.out.println("r - enter new Reading");
   System.out.println("l - List all readings");
   System.out.println("o - Open file with readings");
   System.out.println("w - Write readings to a file");
   System.out.println("q - Quit");
   System.out.print("\nEnter command:");
   String command = keyboard.nextLine();

   if (command.equalsIgnoreCase("r")) {
    System.out.print("Species name:");
    String species = keyboard.nextLine();
    System.out.print("Count:");
    int count = Integer.parseInt(keyboard.nextLine());
    System.out.print("Comment:");
    String comment = keyboard.nextLine();
    notebook.addReading(species, count, comment);
   }
   else if (command.equalsIgnoreCase("l")) {
    System.out.println(notebook);   
   }
   else if (command.equalsIgnoreCase("o")) {
    System.out.print("Enter name of file to read:");
    String filename = keyboard.nextLine();
    try {
     notebook = new Notebook(filename);
    }
    catch (FileNotFoundException e) {
     System.out.println("ERROR: File " + filename +  " does not exists.");
    }
   }
   else if (command.equalsIgnoreCase("w")) {
    System.out.print("Enter name of file to write to:");
    String filename = keyboard.nextLine();
    notebook.writeToFile(filename);    
   }
   else if (command.equalsIgnoreCase("q")) {
    System.out.println("Bye bye.");
    System.exit(0);
   }
  }


 }

}

import java.io.Serializable;
import java.util.Date;

public class Reading implements Serializable {

 private Date date;

 private String species;

 private int count;

 private String comment;

 public Reading(Date date, String species, int count, String comment) throws NegativeCountException {
  super();
  if (count < 0)
   throw new NegativeCountException("There are no negative animals you dummy.");
  this.date = date;
  this.species = species;
  this.count = count;
  this.comment = comment;
 }

 public String toString() {
  return date + "\t" + species + "\t" + count + "\t" + comment;
 }

}


public class NegativeCountException extends Exception {

 public NegativeCountException(String m) {
  super(m);
 }

}

Lab 19

2009-11-10T13:01:00.003-05:00

Question 8 on page 786.

Hint: refer to binary search class and demo on page 777-778.

Homework 8: Binary Search Trees

2009-11-10T12:20:00.012-05:00

A Binary Search Tree is a very commonly used data structure, about which you will learn much more in 146, that stores numbers in a tree where every node has two children (thus, binary). Each node contains a number. All the numbers on the left branch of a node are smaller than that node and, similarly, all the numbers on the right branch of a node are bigger than the node. The figure on the right shows an example.
Below you will find a partial implementation of a binary search tree with three methods missing: add, max, and height. For this homework you will implement these methods.

public class BinarySearchTree {

 private BinarySearchTree left;
 
 private BinarySearchTree right;
 
 private int data;
 
 public BinarySearchTree() {
  left = null;
  right = null;
 }
 
 /** Create a tree that consists of just one node with no children. */
 public BinarySearchTree(int data) {
  left = null;
  right = null;
  this.data = data;
 }
 
 /** Adds new number n to this BinarySearchTree, placing it in its correct place.
  * 
  * @param n the number to be added
  */
 public void add (int n) {
           //TODO
 }
 
 /** Returns the maximum number in this tree. */
 public int max() {
           //TODO
 }
 
 /** Returns the height of this tree. */
 public int height() {
           //TODO
 }
 
 public String toString() {
  return toString("");
 }
 
 public String toString(String prefix) {
  String result = "";
  if (right != null)
   result += right.toString(prefix + "-");
  else
   result += prefix + "- *\n"; 
  
  result += prefix + " " + data + "\n";
  
  if (left != null)
   result += left.toString(prefix + "-");
  else
   result += prefix + "- *\n";
    
  return result;  
 }
 
 
 public static void main(String[] args) {
  BinarySearchTree tree = new BinarySearchTree(8);
  tree.add(3);
  tree.add(10);
  tree.add(1);
  tree.add(6);
  tree.add(14);
  tree.add(4);
  tree.add(7);
  tree.add(13);
  System.out.println(tree);
  System.out.println("Max=" + tree.max());
  System.out.println("Height=" + tree.height());

 }
}

The main method shown above constructs the tree shown in the figure. After you properly implement the methods, that main will run and will print out:

--- *
-- 14
---- *
--- 13
---- *
- 10
-- *
 8
---- *
--- 7
---- *
-- 6
---- *
--- 4
---- *
- 3
--- *
-- 1
--- *

Max=14
Height=4

This homework is due Tuesday, November 17 at noon.

Lab 18

2009-11-05T13:12:00.001-05:00

Question 1 on Page 744.

Note: only use a text file.

Chapter 11: Recursion

2009-11-05T10:51:00.001-05:00

Chapter 11 deals with the topic of recursion. Recursion is not a language feature, it is simply having a method call itself. All programming languages are capable of recursion. Recursion is a technique that makes certain algorithms (which we do not cover in this class) much easier to write and understand.

CSCE 145: Chapter 11 from Jose Vidal on Vimeo.

You will need to have watched the above screencast by Tuesday, November 10, before class. Here are the slides from the textbook:

Lab 17

2009-11-03T13:48:00.001-05:00

Qestion 2 on Page 673.

Chapter 10 Lecture

2009-10-30T15:30:00.002-04:00

Below is the screencast for the chapter 10 which deals with reading and writing streams to files. I/O operations like these are slightly different on every programming language, but the basic ideas are the same.

CSCE 145: Chapter 10 from Jose Vidal on Vimeo.

You must have watched the screencast by Tuesday, November 3 before class. The textbook slides are below.

Homework 7: Field Notebook

2009-10-30T14:20:00.001-04:00

For this homework you will implement a minimal field notebook, as might be used by a bird or butterfly watcher on the field (on her Android phone, one presumes). Your application will need to implement at least three classes:

Reading is a specific observation that the user makes. This class has data members
1. date of type Date, the date of the reading, which you will assign automatically to the current time.
2. species is a String which is the name of the species of animal the user saw.
3. count is an int that is the number of animals the user saw.
4. comment a String comment
Notebook is a collection of up to 100 readings. It should support, adding a new reading, printing, saving to a file, and reading back from a file.
NegativeCountException is an Exception that you will raise if the user ever tries to enter a negative number of animals. Your program will throw this exception and also catch it, so the program does not crash.

Your program will support the saving of the whole notebook to a file and the subsequent loading of a notebook from a file. The whole thing will be controlled via a text-based interface, as such:

Command list: 

r - enter new Reading
l - List all readings
o - Open file with readings
w - Write readings to a file
q - Quit

Enter command:r
Species name:swallowtails
Count:3
Comment:Fluttering in the sunshine.
Command list: 

r - enter new Reading
l - List all readings
o - Open file with readings
w - Write readings to a file
q - Quit

Enter command:r
Species name:Jezebel
Count:11
Comment:Hard to count in the daylight.
Command list: 

r - enter new Reading
l - List all readings
o - Open file with readings
w - Write readings to a file
q - Quit

Enter command:l
Fri Oct 30 14:11:31 EDT 2009 swallowtails 3 Fluttering in the sunshine.
Fri Oct 30 14:12:02 EDT 2009 Jezebel 11 Hard to count in the daylight.

Command list: 

r - enter new Reading
l - List all readings
o - Open file with readings
w - Write readings to a file
q - Quit

Enter command:r
Species name:Duke of Burgundy
Count:1
Comment:Did not expect to see this one here!
Command list: 

r - enter new Reading
l - List all readings
o - Open file with readings
w - Write readings to a file
q - Quit

Enter command:l
Fri Oct 30 14:11:31 EDT 2009 swallowtails 3 Fluttering in the sunshine.
Fri Oct 30 14:12:02 EDT 2009 Jezebel 11 Hard to count in the daylight.
Fri Oct 30 14:12:37 EDT 2009 Duke of Burgundy 1 Did not expect to see this one here!

Command list: 

r - enter new Reading
l - List all readings
o - Open file with readings
w - Write readings to a file
q - Quit

Enter command:w
Enter name of file to write to:notebook.dat
Command list: 

r - enter new Reading
l - List all readings
o - Open file with readings
w - Write readings to a file
q - Quit

Enter command:l
Fri Oct 30 14:11:31 EDT 2009 swallowtails 3 Fluttering in the sunshine.
Fri Oct 30 14:12:02 EDT 2009 Jezebel 11 Hard to count in the daylight.
Fri Oct 30 14:12:37 EDT 2009 Duke of Burgundy 1 Did not expect to see this one here!

Command list: 

r - enter new Reading
l - List all readings
o - Open file with readings
w - Write readings to a file
q - Quit

Enter command:q
Bye bye. //at this point the program stops.

//we start it again
Command list: 

r - enter new Reading
l - List all readings
o - Open file with readings
w - Write readings to a file
q - Quit

Enter command:l

Command list: 

r - enter new Reading
l - List all readings
o - Open file with readings
w - Write readings to a file
q - Quit

Enter command:o
Enter name of file to read:notebook.dat
Command list: 

r - enter new Reading
l - List all readings
o - Open file with readings
w - Write readings to a file
q - Quit

Enter command:l
Fri Oct 30 14:11:31 EDT 2009 swallowtails 3 Fluttering in the sunshine.
Fri Oct 30 14:12:02 EDT 2009 Jezebel 11 Hard to count in the daylight.
Fri Oct 30 14:12:37 EDT 2009 Duke of Burgundy 1 Did not expect to see this one here!

Command list: 

r - enter new Reading
l - List all readings
o - Open file with readings
w - Write readings to a file
q - Quit

Enter command:r
Species name:Speckled wood
Count:200
Comment:A gaggle of butterflies.
Command list: 

r - enter new Reading
l - List all readings
o - Open file with readings
w - Write readings to a file
q - Quit

Enter command:l
Fri Oct 30 14:11:31 EDT 2009 swallowtails 3 Fluttering in the sunshine.
Fri Oct 30 14:12:02 EDT 2009 Jezebel 11 Hard to count in the daylight.
Fri Oct 30 14:12:37 EDT 2009 Duke of Burgundy 1 Did not expect to see this one here!
Fri Oct 30 14:14:53 EDT 2009 Speckled wood 200 A gaggle of butterflies.

Command list: 

r - enter new Reading
l - List all readings
o - Open file with readings
w - Write readings to a file
q - Quit

Enter command:r
Species name:zabulon skipper
Count:-1
Comment:lets try this
Sorry, no negative animals allowed.
Command list: 

r - enter new Reading
l - List all readings
o - Open file with readings
w - Write readings to a file
q - Quit

Enter command:o
Enter name of file to read:thisfilenamedoesnotexist.dat
ERROR: File thisfilenamedoesnotexist.dat does not exists.
Command list: 

r - enter new Reading
l - List all readings
o - Open file with readings
w - Write readings to a file
q - Quit

Enter command:q
Bye bye.

This homework is due Tuesday, November 10 @noon.

Lab test 2 review

2009-10-29T13:24:00.002-04:00

Today we will have review for lab test 2. No lab assignment.