Category Archives: Assignment

Chapter 6: Coin and Purse ADTs

Make the following changes to the Purse ADT:

import java.util.ArrayList;

/**
   A purse holds a collection of coins.
*/
public class Purse
{
   /**
      Constructs an empty purse.
   */
   public Purse()
   {
      coins = new ArrayList();
   }

   /**
      Add a coin to the purse.
      @param aCoin the coin to add
   */
   public void add(Coin aCoin)
   {
      coins.add(aCoin);
   }

   /**
      Get the total value of the coins in the purse.
      @return the sum of all coin values
   */
   public double getTotal()
   {
      double total = 0;
      for (int i = 0; i < coins.size(); i++)
      {
         Coin aCoin = (Coin)coins.get(i);
         total = total + aCoin.getValue();       
      }
      return total;
   }

   private ArrayList coins;
}

/**
A coin with a monetary value.
 */
public class Coin
{
    /**
    Constructs a coin.
    @param aValue the monetary value of the coin.
    @param aName the name of the coin
     */
    public Coin(double aValue, String aName)
    {
        value = aValue;
        name = aName;
    }

    /**
    Gets the coin value.
    @return the value
     */
    public double getValue()
    {
        return value;
    }

    /**
    Gets the coin name.
    @return the name
     */
    public String getName()
    {
        return name;
    }

    public boolean equals(Object otherObject)
    {
        Coin other = (Coin)otherObject;
        return name.equals(other.name)
        && value == other.value;
    }

    private double value;
    private String name;
}

Modify the Purse class to be implemented with ArrayList<Coin> and to use a for-each loop.
Implement the following methods in the Purse class:

 /**
      Counts the number of coins in the purse
      @return the number of coins
   */
   public int count()
   {
     
   }

   /**
      Tests if the purse has a coin that matches
      a given coin.
      @param aCoin the coin to match
      @return true if there is a coin equal to aCoin
   */
   public boolean find(Coin aCoin)
   {

   }

   /**
      Counts the number of coins in the purse that match
      a given coin.
      @param aCoin the coin to match
      @return the number of coins equal to aCoin
   */
   public int count(Coin aCoin)
   {

   }

   /**
      Finds the coin with the largest value. 
      (Precondition: The purse is not empty)
      @return a coin with maximum value in this purse
   */
   pulic Coin getMaximum()
   {

   }

/**
      Adds coins in the purse - use for-each loop
      Comment on this implementation
      if any issues come up.
   */
   public void addCoin(ArrayList<Coin> aCoins)
   {
     
   }

/**
      Deletes coins in the purse - use for-each loop to find all "coins"
      Comment on this implementation if any issues come up.
      @return an object of Coin      
   */
   public Coin deleteCoin(Coin aCoin)
   {
     
   }

Finally, write a driver, PurseTest.java to demonstrate the behavior of the for-each loop performance. Comment on any issues that might arise.

Submit the files in a zip folder(compressed) or a link to GitHub.

Chapter 6: The Iterator


import java.util.ArrayList;

/**
   This bank contains a collection of bank accounts.
*/
public class Bank
{   
   /**
      Constructs a bank with no bank accounts.
   */
   public Bank()
   {
      accounts = new ArrayList<BankAccount>();
   }

   /**
      Adds an account to this bank.
      @param a the account to add
   */
   public void addAccount(BankAccount a)
   {
      accounts.add(a);
   }
   
   /**
      Gets the sum of the balances of all accounts in this bank.
      @return the sum of the balances
   */
   public double getTotalBalance()
   {
      double total = 0;
      for (BankAccount a : accounts)
      {
         total = total + a.getBalance();
      }
      return total;
   }

   /**
      Counts the number of bank accounts whose balance is atLeast a given value.
      @param atLeast the balance required to count an account
      @return the number of accounts having least the given balance
   */
   public int count(double atLeast)
   {
      int matches = 0;
      for (BankAccount a : accounts)
      {
         if (a.getBalance() >= atLeast) matches++; // Found a match
      }
      return matches;
   }

   /**
      Finds a bank account with a given number.
      @param accountNumber the number to find
      @return the account with the given number, or null if there
      is no such account
   */
   public BankAccount find(int accountNumber)
   {
      for (BankAccount a : accounts)
      {
         if (a.getAccountNumber() == accountNumber) // Found a match
            return a;
      } 
      return null; // No match in the entire array list
   }

   /**
      Gets the bank account with the largest balance.
      @return the account with the largest balance, or null if the
      bank has no accounts
   */
   public BankAccount getMaximum()
   {
      if (accounts.size() == 0) return null;
      BankAccount largestYet = accounts.get(0);
      for (int i = 1; i < accounts.size(); i++) 
      {
         BankAccount a = accounts.get(i);
         if (a.getBalance() < largestYet.getBalance())
            largestYet = a;
      }
      return largestYet;
   }

   private ArrayList<BankAccount> accounts;
}

/** 
 * mrs.e
 * 12/14/2018
 * 
 * ArrayLists
 * for-each loop
 * Iterator
 * 
 * */

import java.util.ArrayList;
import java.util.Iterator;

public class ArrayListIterator 
{
   public static void main( String[] args )
   {
      // add elements to an ArrayList
      String[] pets = { "Puppy", "Kitten", "Gerbil", "Bunny", "Ferret" };
      ArrayList<String> aList = new ArrayList<String>();      

      for ( String pet : pets )
         aList.add( pet ); // for each loop - don't change the ArrayList   

      // add elements in removePets array to removeList
      String[] removePets = { "Gerbil", "Bunny" };
      ArrayList<String> removeList = new ArrayList<String>();

      for ( String pet : removePets )
         removeList.add( pet ); 

      // print items of the list
      System.out.println( "ArrayList: " );

      for ( int count = 0; count < aList.size(); count++ )
         System.out.printf( "%s ", aList.get( count ) );

      // remove from list the pets contained in removeList
      removePets( aList, removeList );

      // print items of the list 
      System.out.println( "\n\nArrayList after calling removePets: " );

      for ( String pet : aList )
         System.out.printf( "%s ", pet );
   } // end main

   // remove pets in collection2 found in collection1
   private static void removePets( ArrayList<String> collection1, 
      ArrayList<String> collection2 )
   {
      // get iterator
      Iterator<String> iterator = collection1.iterator(); 

      // loop while collection has items
      while ( iterator.hasNext() )         
      {
         if ( collection2.contains( iterator.next() ) )
            {
            iterator.remove(); // remove current pet
            }
      } // end while
   } // end method removePets
} // end class ArrayListIterator

Global Sequence Alignment

Write a program to compute the optimal sequence alignment of two DNA strings. This program will introduce you to the field of computational biology in which computers are used to do research on biological systems. Further, you will be introduced to a powerful algorithmic design paradigm known as dynamic programming.

Biology review.  A genetic sequence is a string formed from a four-letter alphabet {Adenine (A), Thymine (T), Guanine (G), Cytosine (C)} of biological macromolecules referred to together as the DNA bases. A gene is a genetic sequence that contains the information needed to construct a protein. All of your genes taken together are referred to as the human genome, a blueprint for the parts needed to construct the proteins that form your cells. Each new cell produced by your body receives a copy of the genome. This copying process, as well as natural wear and tear, introduces a small number of changes into the sequences of many genes. Among the most common changes are the substitution of one base for another and the deletion of a substring of bases; such changes are generally referred to as point mutations. As a result of these point mutations, the same gene sequenced from closely related organisms will have slight differences.

The problem.  Through your research you have found the following sequence of a gene in a previously unstudied organism.

A A C A G T T A C C

What is the function of the protein that this gene encodes? You could begin a series of uninformed experiments in the lab to determine what role this gene plays. However, there is a good chance that it is a variant of a known gene in a previously studied organism. Since biologists and computer scientists have laboriously determined (and published) the genetic sequence of many organisms (including humans), you would like to leverage this information to your advantage. We’ll compare the above genetic sequence with one which has already been sequenced and whose function is well understood.

T A A G G T C A

If the two genetic sequences are similar enough, we might expect them to have similar functions. We would like a way to quantify “similar enough.”

Edit-distance.  In this assignment we will measure the similarity of two genetic sequences by their edit distance, a concept first introduced in the context of coding theory, but which is now widely used in spell checking, speech recognition, plagiarism detection, file revisioning, and computational linguistics. We align the two sequences, but we are permitted to insert gaps in either sequence (e.g., to make them have the same length). We pay a penalty for each gap that we insert and also for each pair of characters that mismatch in the final alignment. Intuitively, these penalties model the relative likeliness of point mutations arising from deletion/insertion and substitution. We produce a numerical score according to the following table, which is widely used in biological applications:

Here are two possible alignments of the strings x = "AACAGTTACC" and y = "TAAGGTCA":

The first alignment has a score of 8, while the second one has a score of 7. The edit-distance is the score of the best possible alignment between the two genetic sequences over all possible alignments. In this example, the second alignment is in fact optimal, so the edit-distance between the two strings is 7. Computing the edit-distance is a nontrivial computational problem because we must find the best alignment among exponentially many possibilities. For example, if both strings are 100 characters long, then there are more than 10^75 possible alignments.

Not finished