Thursday, November 19, 2009

Lab 22

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;
        }
    }
}

 

Tuesday, November 17, 2009

Homework 8 Solution

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

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:

  1. Set() the constructor takes no arguments and creates an empty set.
  2. String toString() returns a string with all the elements of this set in printed form, as usual.
  3. void add(T x) adds element x to the set. If x is already in the set then it does nothing.
  4. boolean contains(T x) returns true if the set contains the element x, false otherwise.
  5. void add(Set<T> other) adds the complete contents of the set other to this set.
  6. void subtract(Set<T> other) removes every element of other that is in this set.
  7. 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

Question 1 on Page 849.

Thursday, November 12, 2009

Lab 20

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

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:

Tuesday, November 10, 2009

Homework 7 Solution

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

Question 8 on page 786.

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

Homework 8: Binary Search Trees


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.

Thursday, November 5, 2009

Lab 18

Question 1 on Page 744.

Note: only use a text file.

Chapter 11: Recursion

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:

Tuesday, November 3, 2009