mdinfotech.net  



Monday March 30

Join the Google Classroom for this course. Announcements and assignments will be posted here. Email me at lwear@sd61learn.ca to get the course code.
  • lab rules, exactly what does "monitors OFF!" mean?
  • saving and renaming files, creating folders, SAVE EVERY PROGRAM YOU WRITE ON THE H (Host) DRIVE.
  • the "Back-up" talk: Google Drive and USB Sticks
  • Printing
  • Lots of 100/80/60 quizzes
  • There are a number of small programming exercises to be handed in and a few larger ones.
  • The Unit Test is worth 15% of your final mark.
  • The Group Java Game Project worth 20% of your final mark.
  • How to get an A on Programming Assignments: Program Marking Criteria
  • Test your code typing speed Typing.io.

Resources
Important Dates
  1. Canadian Computing Contest - Wed Feb 12 12-3
  2. Spring Break - March 14 to March 29
  3. End of Term 1 and Game Due - Friday April 3
  4. APCS Exam - Friday May 8
Programming with Eclipse Resources for Installing Eclipse at Home
  • At HOME: Download Eclipse IDE for Java Developers:
Other Eclipse Resources
What is Computer Science?
  1. Define in class. Class Notes
  1. What is a programming language? History of Programming Languages
  2. How does Java work? (compiler > bytecode > JRE) (JVM Video)
  3. Homework: Review all of CS 11 and CS 12 Java Units
  4. Quiz
Create an account on AP Classroom and join my class.
To write the Canadian Computing Contest on Wednesday Feb 12 :
  1. Join my CCC Google Classroom.
  2. Register (http://cemc.uwaterloo.ca/contests/computing/computing-grader.html). You will need the school number : 091301202
  3. Get me to approve your registration.
  4. Do practice questions. (http://cemc.uwaterloo.ca/contests/computing/computing-grader.html)
  5. Ensure you can submit solutions that are accepted by the online grader BEFORE the day of the test. A number of students submitted correct solutions last year but got marked with a zero because they did not follow the instructions.

Review the following topics:

Console Input and Output
  1. Review how to get user input from the command line: run this program using Eclispe: ConsoleInput.java and refer to the Scanner Class API.
Input and Output From Dialog Boxes
  1. Review dialog boxes: run this program using Eclispe: Greeting.java
Exception Handling
  1. See Greeting.java for an example of exception handling.
  2. Read about it here: Try Statements and Exception Handling
Additional Resources:
The precondition statement indicates what must be true before a method is called. The postcondition statement indicates what will be true when a method finishes its work. They go in the comments of a method.
// Preconditions: x >= 0
// Postconditions: returns the value of the square root of x
public static double squareRoot(double x) {
 return Math.sqrt(x);
}
The method calls squareroot(10) and squareroot(5) meet the precondition, but the method call squareroot(-1) does not.
//   Precondition:  letter is an uppercase or
//   lowercase letter (in the range 'A'...'Z' or 'a'...'z').
//   Postcondition:  returns true if letter is a vowel;
//   otherwise the value returns false
public static boolean isVowel(char letter)
In general:
  • When you write a method, you should make every effort to detect when a precondition has been violated.
  • If you detect that a precondition has been violated, then print an error message and end the program

Write a program that uses the Scanner class to read the (x,y) coordinates for two points. For each point, the input should be typed in with the format x, y, and the program will parse the values x and y out of the input. Compute the distance between the two points using the distance formula. Catch exceptions that may be thrown by the calculation. Use Math.pow() and Math.sqrt() where applicable.

Review this code from Grade 11 to see one way to read and write to files using Java: BufferedReader File Input Code and BufferedWriter File Output Code.
  1. Create a 10x10 integer array, initialized to 0
  2. Write a new class calledPoint with two instance variables (int x and int y) and get and set methods for each. Do not use the built in Java Point class.
  3. Write a test driver with a minimum of the six methods listed below:
    void init(int  board, Point p) - initializes board to 0, and sets start position to 1
    int sum (int  board) - returns sum of the board
    
    // the following methods return true if the move is successful,
    // or false if an ArrayIndexOutOfBounds Exception is thrown
    boolean north (int  board, Point p) - moves position north
    boolean south (int  board, Point p) - moves position south
    boolean east (int  board, Point p) - moves position east
    boolean west (int  board, Point p) - moves position west
    
    
    		 
  4. 0,0 is the top left.
  5. read in a file where:
    • first line is the x position to start at
    • second line is the y position to start at
    • the remaining lines of the file each contain N, E, S, W for North, East, South or West
  6. set the starting Point x,y to one in the array.
  7. for each line read, move current position by one space in that direction. North is up, East is right, South is down, West is left
  8. if the array element of the new position contains 0, replace it with a 1, otherwise multiply its current value by 2
  9. continue until the End of File is reached OR an ArrayIndexOutOfBounds Exception is thrown (print an error and end program) (that is not handled by north, south, east or west).
  10. If the end of file is reached, add up all the elements of the two dimensional array and output that number to the console.
  11. If any invalid data is read from the file, print invalid data and end the program.

The class will be split into groups to come up with two test cases each. These test cases will be used to evaluate the lab.

  1. Spires of Vulcan
  2. Watch this
  3. What is recursion: watch this
  4. When to choose recursion over iteration, watch this
  5. Discuss how these common algorithms can be recursive and iterative: factorial, isPrime, Fibonacci
Resources
  1. Java Recursion
  2. Fibonacci Problem
  3. Recursive Algorithms
AP Textbook: Chapter 7 Recursion
Examine this code: Fibonacci. Now write similar programs that compare the runtime and number of method calls for factorial and isPrime (both recursive and iterative solutions)

A word is considered emulike if it contains the letters: e, m, u in it, if any order. For example, the following words are emulike: "mustache", "umbrella", "temperature", and "guatemala".

Write a program WordLike.java to support the following features.

  • Write this method, any solution that works is acceptable:
    /* Precondition: word is a single word
     * Postcondition: returns true if word is emulike, otherwise false
     */
    public static boolean emulike(String word)
    
  • Write this recursive method
    /* Precondition: foo and bar are single words
     * Postcondition: returns true if all the letters of foo are contained in bar
     */
    public static boolean foobarlike(String foo, String bar)
    
    Examples:
    foobarlike("left", "felt") returns true.
    foobarlike("ado", "dormant") returns true.
    foobarlike("fold", "skyfall") returns false.
    
  • Write this recursive method:
    /* Precondition: sentence is a sentence in the form of a string array
     * Postcondition: returns a string of the leftlike words in the sentence
     */
    public static String keepLeftlike(String    sentence)
    
    Example:
    String    a = {"this", "stressful", "time", "on", "the", "twelfth", "felt", "extremely", "uneventful"};
    keepLeftlike(a) returns "stressful twelfth felt uneventful"

Use the skeleton code below:

public class Wordlike {
  public static void main(String    args) {
    System.out.println("Testing emulike: ");
    System.out.println("emulike(\"mustache\") is " + emulike("mustache"));
    System.out.println("emulike(\"horses\") is " + emulike("horses"));
    System.out.println("Testing foobarlike:");
    System.out.println("foobarlike(\"ado\", \"dormant\") is " + foobarlike("ado", "dormant")); 
    System.out.println("foobarlike(\"fold\", \"skyfall\") is " + foobarlike("fold", "skyfall"));
    String  a = {"this", "stressful", "time", "on", "the", "twelfth", "felt", "extremely", "uneventful"};
    System.out.println("Testing keepLeftlike:");
    System.out.println("keepLeftlike(a) is " +  keepLeftlike(a));
  } 

  /* Precondition: word is a single word
   * Postcondition: returns true if word is emulike, otherwise false
   */
  public static boolean emulike(String word) {
     ...
  }

  /* a recursive method
   * Precondition: foo and bar are single words
   * Postcondition: returns true if all the letters of foo are contained in bar
   */
  public static boolean foobarlike(String foo, String bar) {
     ...
  }

  /* a recursive method
   * Precondition: sentence is a sentence in the form of a string array
   * Postcondition: returns a string of the leftlike words in the sentence
   */
  public static String keepLeftlike(String    sentence) {
     ...
  } 

}
O(1), O(n), O(n^2), O(log n), O(n log n)

Resources
  1. Big O Notation Video
  2. Wikipedia
Note: For the AP Exam, you are required to know the "analysis of programs or algorithms in order to understand their time and space requirements when applied to different data sets." and "the relative running time of " search and sort algorithms. APCS Course Description.

Required for AP:

  1. searching in ordered and unordered lists
  2. Sequential/Linear O(n) vs Binary O(log n) searches
  3. Sorting - O(n2)
    • insertion
    • selection
    O(n log n)
    • merge
Resources
  1. Sorting Algorithms Compared
  2. HTML5 Canvas Demo: Sorting Algorithms
  3. Binary Search: Demo, Code
  4. Wikipedia:

In class activity: Each student will be assigned the Insertion, Selection or Merge Sort. Learn it. Get together in a group and demonstrate it to the class.

AP Textbook: Chapter 8 Sorting and Searching

Write a class that contains methods implementing the
  • iterative Linear Search
  • iterative and recursive Binary Search
  • iterative and recursive Insertion Sort,
  • iterative and recursive Selection Sort,
  • recursive Merge Sort.
  1. Create a sorted array of size 10, size 100 and another of size 1,000,000.
  2. Calculate the time each search alogorithm takes for a "worst case scenario" search, that is, the elements being searched for is not in the array. Use
  3. Create 3 sample arrays of sizes 10, 100, and 10000 initialized with random numbers between 0 and 5000.
  4. Calculate the time each alogorithm takes to sort each array or the time it takes for a "worst case scenario" search, that is, the elements being searched for is not in the array.
  5. You will need to use System.nanotime() WITHIN the iterative methods. Otherwise you will be timing method calls as well. To time the recursive algorithms, start timing before the method call and finish timing after the method call.
  6. Print all the times in ms.
  7. Run each test 1000 times and calculate the average the sort/search time for each data size.
  8. Display the output in a table like the one shown below:
                Average search times:
                             | 10(disregard)| 100           | 1 000 000  
                ---------------------------------------------------------
                Linear Src   |           ms |            ms |           
                ---------------------------------------------------------
                Binary Src   |           ms |            ms |         
                ---------------------------------------------------------
                Binary Rec   |           ms |            ms |          
  


                Average sort times:
                             | 10(disregard)| 100           | 10 000 
                -------------------------------------------------------
                Insertion It |           ms |            ms |          
                -------------------------------------------------------
                Insertion Rc |           ms |            ms |          
                -------------------------------------------------------
                Selection It |           ms |            ms |          
                -------------------------------------------------------
                Selection Rc |           ms |            ms |          
                -------------------------------------------------------
                Merge Rc     |           ms |            ms |             |  
                
Run this code:
              
int sum = 0, p = 1;
for (int count = 1; count <= 50; count++)
{
     sum += p;
     p *= 2;
}
System.out.println(sum);
What is the output? Why?
Barron's AP Text Chapter 2
  1. Objects
  2. Classes
  3. public, private and static
  4. methods: constructors, accessor and mutators
Resources
  1. Read Chapter 2 in the AP Textbook
  2. There will be an online progress check quiz.

Complete this exercise in the time provided.

  1. Class relationships
    • associations - a use relationship, when two classes are aware of each other through such as one class method accepting a parameter from another class type.
    • aggregation - a has-a relationship. An aggregate object is any object that has other objects as instance data.
  2. Object Interactions
    • Driver Programs - programs used to test methods and classes
    • Isolated Tests - test each class/method on its own, separate from other code
    • Using the Eclipse Debugger
  3. aliases - when two references point to the same object.
    Foo f1 = new Foo();
    Foo f2 = new Foo();
    			   
    f1 and f2 are two different Foo objects
    f1 = f2;
    			   
    The address stored in f2 is now also stored in f1. f1 and f2 are aliases of each other.
In Barron's AP Text Chapter 2
  1. Encapsulation: the packing of data and functions into a single component
  2. static final variables
  3. static vs instance methods
  4. scope and this
  5. References and null
  6. passing objects as parameters
    • references of passed objects are passed by value
    • "formal parameter" - the parameter in the method header
    • "actual parameter" - the parameter passed to the method call
    • the current value of the actual parameter is copied into the formal parameter
    • when an object is passed to a method, a reference to that object is passed, and the formal parameter and the actual parameter become aliases of each other
Resources
  1. Intro to OOP

You have been hired by an Insurance Company to determine if a recent increase in the number of insurance claims made for flood damage are valid.

  1. Download this zip file: PTPlot Package. This is a package from the Ptolemy Homepage that allows easy 2D plotting of data. Extract the zip file into your Eclipse Project folder, and add the package to an Eclipse project. This tutorial may help you: How to Add Existing Files to Eclipse Projects.
  2. Copy the program from below. It is from listing A.1 in this document: PT Plot PDF. Run this program as your PTPlot Hello World. It should show a plot of the cosine function.
    import ptolemy.plot.*;
    
    public class EasyPtPlot {
      public static final double Xmin = -5.0;
      public static final double Xmax = 5.0; // Graph domain
      public static final int Npoint = 500;
      public static void main ( String <> args ) {
        Plot plotObj = new Plot () ; // Create Plot object
        plotObj.setTitle("f(x) vs x") ;
        plotObj.setXLabel("x") ;
        plotObj.setYLabel ("f(x)");
        // plotObj.setSize (400 , 300) ;
        // plotObj.setXRange ( Xmin , Xmax ) ;
        // plotObj.addPoint ( int Set , double x , double y , boolean connect );
        double xStep = (Xmax - Xmin ) / Npoint;
        // Plotting loop
        for (double x = Xmin; x <= Xmax; x += xStep) {
          double y = Math.sin( x ) * Math.sin ( x ) ;
          plotObj.addPoint (0 , x , y , true ) ;
        }
        PlotApplication app = new PlotApplication ( plotObj ) ; // Display
      }
    }
                     
                     
  3. Now you are ready for some weather data! Download and extract this zip file: weather.zip. This is rainfall data in CSV files for two stations in Victoria for the past 25 years. The CSV files from Environment Canada are daily rainfall amounts in millimetres. There are data gaps sometimes in one or both files. Data missing in the record is blank and has an M in the next column.
  4. Your job is to determine when flooding would likely have occurred in the past based on say two days of heavy rainfall.
  5. Calculate a rainfall amount per month (when no data is missing, average the monthly rainfall between the two station) and plot it.
  6. Calculate a maximum amount over a two day period, averaged as above, for each month and plot it.
  7. Print out the top 10 results for each analysis.
  8. Write a report identifying the dates over the last 25 years most likely to coincide with flood claims. Use your plots to support your conclusions. Here is an outline for the report:
    • Title
    • Abstract - 1 paragraph summary of your entire project including the purpose, methods, results, and conclusion.
    • Introduction - introduce the purpose of the report. State the question being asked. Explain the significance of the data being investigated. Use additional research to provide some background information that leads into question being asked.
    • Methods - summarize how you processed the data.
    • Results - Choose the most appropriate method for representing your data. Make sure tables and graphs are appropriately titled, axes labeled. Be sure to include:
      1. Create a table titled: Top 10 Maximum Rainfall Over a 2-Day Period with the headings: Date, Total Rainfall (mm).
      2. A plot of Rainfall Over a 2-Day Period with bottom axis labelled in years.
      3. Create a table titled: Top 10 Monthly Rainfall with the headings: Date, Total Rainfall (mm).
      4. A plot of Maximum Monthly Rainfall with bottom axis labelled in years.
    • Conclusion - In paragraph form, make factual statements relevant your findings, and support with data. First, restate the original problem. State and describe the numerical data/results. Provide an explanation for the results by referring back to the scientific background information. State problems and sources of error with the data. Explain how they affected your results.

Evaluation (/30)

Code: Commenting and Formatting /10
Code: Efficiency and Design /10
Top 10 Tables: correct data and easy to read format /5
Plots: correct, with years labelled, important points highlighted /5
Written Report /5

Found in: Barron's AP Text Chapter 3. In class discussion on:

  1. Superclass and Subclass
  2. class hierarchy: parent class, child class
  3. is-a relationship
  4. method overriding - read about @override: Predefined Annotation Types.
  5. protected keyword
  6. extends keyword
  7. super keyword
  8. declaring subclass objects
  9. know the modifiers
                | Class | Package | Subclass | World
    ————————————+———————+—————————+——————————+———————
    public      |  y    |    y    |    y     |   y
    ————————————+———————+—————————+——————————+———————
    protected   |  y    |    y    |    y     |   n
    ————————————+———————+—————————+——————————+———————
    no modifier |  y    |    y    |    n     |   n
    ————————————+———————+—————————+——————————+———————
    private     |  y    |    n    |    n     |   n
    
    y: accessible
    n: not accessible
    					   
Need a refresher? Watch this video on inheritance.
Ms. Wear's Notes on the subject

Things to know from Barron's AP Text Chapter 4:
  1. inheriting from the Object class (p 171)
  2. Math Class, String Class (review from CS 11)
  3. Random Numbers
  4. Generic Types
  5. (p 239) Auto-boxing and -unboxing. Not on AP exam but allowed in Free Response Questions
  6. Integer and Double classes p 177-180

The following links describe what parts of Java you need to know for the AP Exam:

Java Subset
AP Java Quick Reference

Do Barron's APCS text MC Q's starting on page 184

  1. Download this starter code: download here
  2. Add a transfer method Account class so that funds can be moved from one account to another. Think of this as withdrawing money from one account and depositing it into another. Return true if the funds are successfully transferred, otherwise return false.
     //-----------------------------------------------------------------
       //  Validates the transaction.  If sufficent funds exist, withdraws the specified amount
       //  from the "from" account and deposits it into the "to" account returning true,
       //  else does nothing and returns false.
       //-----------------------------------------------------------------
       public static boolean transfer (double amount, double fee, Account from, Account to)
       {
    
          
       }
        //-----------------------------------------------------------------
       //  Validates the transaction.  If sufficent funds exist, withdraws the specified amount
       //  from this account and deposits it to the "to" account returning true,
       //  else does nothing and returns false.
       //-----------------------------------------------------------------
    
       public boolean transfer (double amount, Account to)
       {
          
       }               
                   
  3. Add an additional constructor so that a user can open an account with just a name and an account number, and a starting balance of 0.
     //-----------------------------------------------------------------
       //  Sets up the account by defining its owner and account number.
       //  Initial balance is set to zero
       //-----------------------------------------------------------------
       public Account (String owner, long account)
       {
         
       }           
                   
  4. For evaluation, you will be given a Banking class which contains a driver to test your Account class. See example below:
Sample Test Case:
      Account acct1 = new Account ("Ted Murphy", 12345, 214.56);
      Account acct2 = new Account ("Anita Gomez", 54321, 20.00);
     

      System.out.println ("Murphy balance after deposit: $" + acct1.deposit (14.58));
      System.out.println ("Gomez balance after deposit: $" + acct2.deposit (300.00));

      System.out.println ("Gomez balance after withdrawal: $" + acct2.withdraw (100.00, 2.00));

	  System.out.print("\nWithdraw $800 from Gomez account: ");
      acct2.withdraw (800.00, 0.0);  // exceeds balance

      acct1.addInterest();
      acct2.addInterest();
     
      System.out.println ("\nAccount Balances:");
      System.out.println (acct1);
      System.out.println (acct2);
     

      // transfer $50 from account 1 to account 2
	  System.out.println ("\nTransfer $50 from Murphy to Gomez:");
      acct1.transfer(50, acct2);

   

      System.out.println (acct1);
      System.out.println (acct2);
      
Sample Output
Murphy balance after deposit: $229.14000000000001
Gomez balance after deposit: $320.0
Gomez balance after withdrawal: $218.0

Withdraw $800 from Gomez account: 
Error: Insufficient funds.
Account: 54321
Requested: $800.00
Available: $218.00

Account Balances:
12345	Ted Murphy	$237.16
54321	Anita Gomez	$225.63

Transfer $50 from Murphy to Gomez:
12345	Ted Murphy	$187.16
54321	Anita Gomez	$275.63      
      
  • Interfaces: read pages 140-145 - video
  • Complete this exercise in class. Closed everything except you may use the Java API.

    A Lockable object is an object whose regular methods are secured: if the object is locked, the methods cannot be invoked; if it is unlocked, they can be invoked.

    Design a Java interface called Lockable that includes the following methods: setKey, lock, unlock, and locked.

    • The setKey, lock, and unlock methods take an integer parameter that represents the key. The setKey method establishes the key.
    • The lock and unlock methods lock and unlock the object, but only if the key used is correct.
    • The locked method returns a boolean of true for locked and false for unlocked.

    Redesign the Account class so that it is lockable.

    For evaluation, you will be given a Banking class which contains a driver to test your Account class.

    Sample Test Case
          Account acct1 = new Account ("Ted Murphy", 12345, 214.56);
          Account acct2 = new Account ("Anita Gomez", 54321, 20.00);
    
          System.out.println (acct1);
          System.out.println (acct2);
          
          System.out.println("\n---------Lock Account 1 and Try to Withdraw/Transfer/Deposit/AddInterest --------");
          acct1.setKey(333);
          acct1.lock(333);
    	  if (acct1.locked()) {
            System.out.println("1. Locked is on");
          } else {
            System.out.println("1. Locked is off");
          }
          System.out.println ("Withdraw $200: " + acct1.withdraw(200, 0));
          System.out.println ("Transfer $200: " + acct1.transfer(200, acct2));
          System.out.println ("Deposit $100: " + acct1.deposit(100));
          System.out.println ("Add Interest: " + acct1.addInterest());
    	  
          System.out.println();
          System.out.println (acct1);
          System.out.println (acct2);
          
          System.out.println("\n---------Unlock Account 1 and Try to Withdraw/Transfer/Deposit/AddInterest--------");
          acct1.unlock(333);
          if (acct1.locked()) {
            System.out.println("1. Locked is on");
          } else {
            System.out.println("1. Locked is off");
          }
          System.out.println ("Withdraw $200: " + acct1.withdraw(200, 0));
          System.out.println ("Transfer $200: " + acct1.transfer(200, acct2));
          System.out.println ("Deposit $100: " + acct1.deposit(100));
          System.out.println ("Add Interest: " + acct1.addInterest());
    	  
          System.out.println();
          System.out.println (acct1);
          System.out.println (acct2);
         
    Sample Output
    12345	Ted Murphy	$214.56
    54321	Anita Gomez	$20.00
    
    ---------Lock Account 1 and Try to Withdraw/Transfer/Deposit/AddInterest --------
    1. Locked is on
    Withdraw $200: 214.56
    Transfer $200: false
    Deposit $100: 214.56
    Add Interest: 214.56
    
    12345	Ted Murphy	$214.56
    54321	Anita Gomez	$20.00
    
    ---------Unlock Account 1 and Try to Withdraw/Transfer/Deposit/AddInterest--------
    1. Locked is off
    Withdraw $200: 14.560000000000002
    Transfer $200: false
    Deposit $100: 114.56
    Add Interest: 118.56960000000001
    12345	Ted Murphy	$118.57
    54321	Anita Gomez	$20.00     
         
    Ms. Wear's Notes on Polymorphism

    Barron's AP Text Chapter 3
    1. references and class hierarchies (p. 134)
    2. Polymorphism - tutorial: applies only to overridden methods in subclasses (p 135)
    3. static (early) binding and dynamic (late) binding - explained(p 135)
    4. downcasting (p 136)
    Do this: Barron's AP Chapter 3 p. 149 All MC Questions.
    Class Diagrams
    UML Basics
    Know these symbols

    Association - uses
    Inheritance - is-a
    Implementation - interfaces
    Dependancy - we are not going to use this
    Aggregation - has-a
    Composition - also has-a, but we are not going to use this
    Remind Ms. Wear to put this exercise online. In pairs, complete this exercise in class. Closed everything except you may use the Java API.
    1. Abstract Classes - read pages 138-140 in Barron's AP Text
    2. Abstract Classes Vs Interfaces
    3. In pairs, complete the Sample Written Response Question on pages 145-147.
    Chapter 3 Quiz.
    Covers all of Barron's APCS Text Chapters 1, 2, 4, 7, 8 and Inheritance(p128-134). 17 Multiple Choice Questions and 1 Written (you must write 3 methods).

    You have a stretchable cloth grocery bag that can hold up to 8.5 kg of groceries. You have won a contest where you get two minutes to fill your grocery bag with any items from the MINI-MARKET grocery store. These are the items available to you:

    1. 2 kg package of chicken for $15
    2. 1 kg bag of flour for $2.50
    3. 0.25 kg can of beans fror $2.40
    4. 0.5 kg box of cereal for $1.20
    5. 0.3 kg box of cookies for $3.99
    6. 1 kg bottle of soda for $0.99
    7. 0.3 kg can of Spam for $4.99

    Create a GroceryItem class as shown below:

    public class GroceryItem {
           double weight = 0;
           double cost = 0;
           String item = "";
          
    	  // write required methods
    	  
    
    }
    

    You are only allowed at most 2 of each item. Your goal is to fill the grocery bag so that the combined weight of all the items is <= 8.5 kg while maximizing the total value of the items.

    You will write two solutions to this problem. You may choose what type of algorithm (brute force, greedy, or recursive) to write for the first solution. Use it to determine the optimal answer to the problem. The second solution must be recursive IF your first solution was iterative. The second solution must be iterative IF your first solution was recursive.

    What are the time and space requirements of each algorithm?

    Use the skeleton code below:
    import java.util.ArrayList;
    
    public class Groceries {
    
        private static int counter = 0;
    
        // returns an array of Grocery items, the angle brackets should be square.
        private static GroceryItem <> groceryItems = {
                new GroceryItem(0.75, 2.5, "flour") ,
                new GroceryItem(0.25,2.4,"beans"),
                new GroceryItem(0.5,4.50, "cereal"),
                new GroceryItem(0.3, 3.99,"cookies"),
                new GroceryItem(1, 0.99, "soda"),
                new GroceryItem(0.3,4.99, "Spam") 
            };
    
        /* Precondition: b is an array of groceries already in the bag
         * Postcondition: returns the optimized bag
         */
        private static ArrayList bestBag(ArrayList   b) {
            
            // counts recursive calls
            counter++;
            if(counter % 10000000 == 0)
                System.out.println("# method calls : " + counter);
          
        } // bestBag
    
        // returns the weight of bag b
        public static double bagWeight(ArrayList  b) {
    
        }
    
        // returns the value of bag b
        public static double bagCost(ArrayList  b) {
    
        }
    
        // returns number of items of i in bag b
        public static int bagCount(ArrayList  b, String i) {
    
        }
    
        // prints contents of bag b
        public static void printBag(ArrayList  b) {
    
        }
    
        public static void main (String <> args) {
            ArrayList  temp = new ArrayList();
            long startTime = System.nanoTime();
            ArrayList  perfectBag = bestBag(temp);
            long endTime = System.nanoTime();
            long duration = (endTime - startTime);
    
            System.out.println("Time: " + duration/1000 + " ms");
            System.out.println("# method calls = " + counter);
            System.out.println("# items = " + perfectBag.size());
            System.out.println("weight items = " + bagWeight(perfectBag) + " kg.");
            System.out.println("cost items = $" + bagCost(perfectBag));
            printBag(perfectBag);
        }
    
    } // Groceries
     


    Evaluation Criteria (/22)
    How to hand in:
    1. Print iterative solution, commented so it is easy to read. (/5)
    2. Print iterative output (/5 if correct)
    3. Print recursive solution, commented so it is easy to read.(/5)
    4. Print recursive output (/5 if correct)
    5. Print GroceryItem.java (/2)
    6. Staple and hand in to my wire inbasket
    This exercise is a published lab by The College Board, who sets the AP CS curriculum. This lab uses photo manipulation to implement Object Oriented concepts inheritance and interfaces.

    Download:
    1. Elevens Lab Instructions (PDF).
    2. Elevens Lab Activity 3
    3. Elevens Lab Activity 4
    4. Elevens Lab Activity 11
    What to do:
    • Activity 3 - Complete this exercise. You will implement a shuffle algorithm.
    • Activity 4 - Complete this exercise. At the end you will have the ability to shuffle a deck of cards.
    • Activity 11 - Complete this exercise. You will learn about the role of simulations in testing software.
    What to Hand in
  • Answer the questions in the assignment on Google Classroom and turn it in.
    1. Read "The Comparable Interface" (p 141 of hard copy textbook, p 145 of digital copy of textbook). Note: This will not be tested on the AP exam. Students will, however, be required to use compareTo for comparison of strings.
    2. If you need more on Comparable, read compareTo and Comparable Explained.
    3. Examine, run, and understand this program that implements Comparable: Pipe.java, and PipeTest.java

    What you need to know:

    In the Java Collection Framework two abstract data types exist to check whether one object is larger, equal, or less to another object: Comparable and Comparator. Comparable is implemented by the class of the objects to compare. In that case only one ordering exist for these objects. Sometimes it is desirable to implement different orderings for the same class. In this case you can implement for each ordering the interface Comparator in a separated class.

    Comparable defines the method int compareTo(Object o) which returns 0 if the object is equal to o, a negative value if o is less, and a positive value if it is larger the object on which this method has been invoked. Carefully read the specification of Comparable. String is an exmaple of a class that implements Comparable.

    Optional: To learn about the differences between Comparable and Comparator (Comparator is not on the AP Exam), read: Java object sorting example (Comparable and Comparator).


    The Exercise

    1) Implement Ordering 1 in class Card by implementing Comparable.

    Ordering 1 defined: One specific ordering for the Card class created for the Elevens Lab is to order the card by suit, then by value. Suit order is Hearts, Spades, Diamonds, Clubs.

    2) Implement Ordering 2 in class Card. Create a class variable boolean useBySuitThenValueSort;. When useBySuitThenValueSort; is true, the ordering 1 is used, when it is false, the ordering 2 is used.

    Ordering 2 defined: Another specific ordering for the Card class created for the Elevens Lab is to order the card by value, then by suit. Suit order is Hearts, Spades, Diamonds, Clubs.

    3) Write a test driver that tests each sort implementation to sort a randomly shuffled Deck of cards (use Arrays.sort() or Collections.sort() ).
    The output of the test driver should be as follows:

    1. Print "Shuffled Deck 1"
    2. Print the list of shuffled cards.
    3. Print "Ordering 1".
    4. Print the list of card sorted using ordering 1.
    5. Print "Shuffled Deck 2"
    6. Print the list of shuffled cards. They should be in a new random order.
    7. Print "Ordering 2".
    8. Print the list of card sorted using ordering 1.

    4) Hand in on Google Classroom

    An ArrayList is an implementation of the List interface. A List is a Collection. To learn more about Collections, look at Collections Tutorial.

    1. Review what you need to know about ArrayLists for the AP Exam: AP ArrayList Skills List.
    2. Watch what you need of these AP Online Lessons:
    3. Read ArrayList Efficiency.
    4. Read the Notes from Ms. Wear.
    5. Read Barron's AP Text Chapter 6 p 238 - 243

    Exercise for Completion Marks:
    1) Complete the Unit 7 Progress Check on AP Classroom by Wednesday.
    2) Complete at least two written questions from old exams that use ArrayLists. Go here old AP exam questions and solutions. Note: these will not be collected.

    Additional Resources
    1. Generics, Generics Tutorial
    Complete the following project:

    RFS Project Description

    Use this Sample Program which uses this map to test your code.

    Please take the time to complete the following course evaluation. It will be used for future course offerings.

    Course Evaluation
    Do all the questions at the end of chapter 6.
    Covers everything.
    Read p. 243-246 of the textbook.
    1. an iterator is an object whose sole purpose is to traverse a collection, one element at a time
    2. there is an Iterator Interface
    3. the methods of the interface are
      • hasNext - returns true if there is at least one more element to be examined
      • next - returns the next element in the iteration, if no elements remain, throws an exception
      • remove - deletes from the collection the last element that was returned by next. Throws an exception if next has not yet been called.
    4. See examples on pages 244-245