Category Archives: Class activity

Elevens lab: Install – Sorts Class Activity

CLASS ACTIVITY

NOTE: YOU CAN USE ANY RESOURCES
Quicksort Trace 1 through 10:
Gavin, Jackson, Philip, and Eric
IDENTIFY PIVOTS

Quicksort Trace 10 through 1:
Crystal, Ibhan, James, and Leon
IDENTIFY PIVOTS

Insertion sort trace 1 through 10:
David Cohen, Martha, Sam, and Aidan

Enactment of Quicksort: 25, 32, 5, 15, 100, 2, 75, 80
Larry, Nick, Harry, Alex, Erina, David Choo, Mo, David H, and Justin
IDENTIFY PIVOTS

Enactment of Mergesort: 25, 32, 5, 15, 100, 2, 75, 80
Daphne, Andy, Andrew, Mark, Adam, Peter, Steph, Jack and Niandong

Homework:
The Elevens game – installed the data and download the pdf.

Screen Shot 2015-02-23 at 2.26.16 PM

Elevens lab: Activity 3 Questions

Lab

The Elevens Game
Screen Shot 2015-02-23 at 11.00.25 PM

Activity 3: Shuffling the Cards in a Deck

Introduction:
Think about how you shuffle a deck of cards by hand. How well do you think it randomizes the cards in the deck?

Exploration:
We now consider the shuffling of a deck, that is, the permutation of its cards into a random-looking sequence. A requirement of the shuffling procedure is that any particular permutation has just as much chance of occurring as any other. We will be using the Math.random method to generate random numbers to produce these permutations.

Several ideas for designing a shuffling method come to mind. We will consider two:

Perfect Shuffle
Card players often shuffle by splitting the deck in half and then interleaving the two half-decks, as shown below.

vendingmachines

This procedure is called a perfect shuffle if the interleaving alternates between the two half-decks. Unfortunately, the perfect shuffle comes nowhere near generating all possible deck permutations. In fact, eight shuffles of a 52-card deck return the deck to its original state!

Consider the following “perfect shuffle” algorithm that starts with an array named cards that contains 52 cards and creates an array named shuffled.

Initialize shuffled to contain 52 “empty” elements. Set k to 0.

For j = 0 to 25,
−– Copy cards[j] to shuffled[k];
−– Set k to k+2. Set k to 1.

For j = 26 to 51,
−– Copy cards[j] to shuffled[k];
–− Set k to k+2.

This approach moves the first half of cards to the even index positions of shuffled, and it moves the second half of cards to the odd index positions of shuffled.

The above algorithm shuffles 52 cards. If an odd number of cards is shuffled, the array shuffled has one more even-indexed position than odd-indexed positions. Therefore, the first loop must copy one more card than the second loop does. This requires rounding up when calculating the index of the middle of the deck. In other words, in the first loop j must go up to (cards.length + 1) / 2, exclusive, and in the second loop j most begin at (cards.length + 1) / 2.

Selection Shuffle
Consider the following algorithm that starts with an array named cards that contains 52 cards and creates an array named shuffled. We will call this algorithm the “selection shuffle.”

Initialize shuffled to contain 52 “empty” elements.
Then for k = 0 to 51,
−– Repeatedly generate a random integer j between 0 and 51, inclusive until cards[j] contains a card (not marked as empty);
−– Copy cards[j] to shuffled[k];
−– Set cards[j] to empty.

This approach finds a suitable card for the kth position of the deck. Unsuitable candidates are any cards that have already been placed in the deck.

While this is a more promising approach than the perfect shuffle, its big defect is that it runs too slowly. Every time an empty element is selected, it has to loop again. To determine the last element of shuffled requires an average of 52 calls to the random number generator.

A better version, the “efficient selection shuffle,” works as follows:

For k = 51 down to 1,
−– Generate a random integer r between 0 and k, inclusive;
−– Exchange cards[k] and cards[r].

This has the same structure as selection sort:
For k = 51 down to 1,
−– Find r, the position of the largest value among cards[0] through cards[k];
−– Exchange cards[k] and cards[r].

This way, the “efficient” selection shuffle algorithm does not require a loop to find the largest (or smallest) value to swap, so it works quicker than the selection shuffle seen above.

Questions:

  1. Write a static method named flip that simulates a flip of a weighted coin by returning either “heads” or “tails” each time it is called. The coin is twice as likely to turn up heads as tails. Thus, flip should return “heads” about twice as often as it returns “tails.”
  2. Write a static method named “arePermutations” that, given two int arrays of the same length but with no duplicate elements, returns true if one array is a permutation of the other (i.e., the arrays differ only in how their contents are arranged). Otherwise, it should return false.
  3. Suppose that the initial contents of the values array in Shuffler.java are {1, 2, 3, 4}. For what sequence of random integers would the efficient selection shuffle change values to contain {4, 3, 2, 1}?

Teacher’s Comments:
1. If you run the two methods with VALUE_COUNT = 10, how often would there be duplicate results?
2. Can the number of duplicate results show the efficiency of the two different shuffles?

https://www.youtube.com/watch?v=hPNRtbbf-Jg

Picture Lab: Activities 1 and 2

A1-1

A1-2

Questions
1. How many bits does it take to represent the values from 0 to 255?
2. How many bytes does it take to represent a color in the RBG color model?
3. How many pixels are in a picture that is 640 pixels wide and 480 pixels high?

A2: Picking a color

A2-1

A2-2

Questions
1. How can you make pink?
2. How can you make yellow?
3. How can you make purple?
4. How can you make white?
5. How can you make dark gray?

Homework
Picture Lab Activity
Finish up A1 and A2

Elevens Lab: Activities 1 and 2 – Sorts Class Activity

Sorts activities:
Quicksort Trace 1 through 10:

QuicksortA

Quicksort Trace 10 through 1:

QuicksortD1

Insertion sort trace 1 through 10:
Inserion Sort

Insertion


Enactment of Quicksort: 25, 32, 5, 15, 100, 2, 75, 80

Enactment of Mergesort: 25, 32, 5, 15, 100, 2, 75, 80

Screen Shot 2015-02-23 at 2.26.16 PM

New Labs

The Elevens Game
Screen Shot 2015-02-23 at 11.00.25 PM

Sign in your account to access support files for the labs
Screen Shot 2014-03-01 at 6.33.26 AM

@Override
Screen Shot 2015-02-23 at 10.02.32 PM

Classwork and Homework: Work on activities 1 and 2

Chapter 8: Tracing and enacting one of the sorts

February 20th, 2015

Homework:
Review the algorithms for non-recursive and recursive sorts we learned in class.
Pay special attention to how the code is written!
Monday you will have an assessment of the sort by participating in one of the following group activities:

Tracing and enacting one of the sorts.

Screen Shot 2015-02-20 at 1.51.52 PM

NOTE: Mrs. Elia will choose the groups.
2 groups of 10 for the enacting and 3 groups of 3 for tracing on posters.

Chapter 7: Pet Shop v2 – Inheritance and Interface

Pet Shop v2 Application Project

PetShop v2

Without changing the Animal class add a new instance field, name. Each animal class ( like Bird ) implements Nameable.

public interface Nameable
{
    String getName();
}

PetSet2
This class groups the objects of different classes, different animal classes, that are only associated by the Nameable interface type. Write the class PetSet2 to add objects of the Nameable interface type.

PetShop2
This class tests the PetSet2 class by adding Nameable type objects and printing the PetSet2 collection.

Sample test:

…
PetSet2 myPetShop2 = new PetSet2();
        
Nameable tweety = new Bird2("tweety",45.00);
Nameable duffy = new Bird2("duffy",5.00);
Nameable nemo = new Fish2("nemo",62.00);
Nameable bear = new Dog2("bear",1100.00);
…        
…
myPetShop2.add(tweety);
myPetShop2.add(duffy);
myPetShop2.add(nemo);
myPetShop2.add(bear);
…
System.out.println(myPetShop2);

Sample output:

My name is tweety
My name is duffy
My name is nemo
My name is bear

….

I can sing

….

NOTE: Again, how close you follow the outline and polymorphism concepts will determine your grade

Chapter 7: Pet Shop v1 Application Project

Pet Shop v1 Application Project

This is the story about a pet shop with few pets but really cute ones. You will write an application designed to get information about this unusual pet shop. You will be applying concepts about polymorphism to develop your classes and driver program. This version one (v1) of Pet Shop will focus on inheritance. In addition, this application will help you better prepare for the AP exam Inheritance, and Polymorphism.

PetShop v1

The way you should focus on this project:

1. DO NOT VIOLATE ENCAPSULATION
2. Use INHERITANCE CONCEPTS to re-use code and functionality.

Specifications:
You will create only one animal class and two of your classmates will share one of their own each for you to have a complete Pet Shop application.

The sample test below is given only to help you understand this assignment. Write your own test class but follow this general outline:
(NOTE: How close you follow the outline and polymorphism concepts will determine your grade)

  • Create an object of PetSet.
  • Create multiple instances of at least three different kinds of animals. Observe that they are Animal objects.
  • Print each Animal object’s sound.
  • Add them to the PetSet object.
  • Print the PetSet object to display what the animals are.

Sample test:

…
PetSet myPetShop = new PetSet();
        
Animal tweety = new Bird(45.00, "I am a bird");
Animal duffy = new Bird(5.00, "I am a bird");
Animal nemo = new Fish(62.00, "I am a fish"); 
Animal bear = new Dog(1100.00, "I am a dog");
…
…
myPetShop.add(tweety);
myPetShop.add(duffy);
myPetShop.add(nemo);
myPetShop.add(bear);
…
System.out.println(myPetShop);

tweety duffy nemo bear

Sample output:

I can sing // phrase
…
I am a bird
I am a bird
I am a fish
I am a dog

1. PetSet class has the following members:
Attributes:

  • an ArrayList of Animal objects (use type parameter)
  • sum (type double)
  • maxPrice (type double)

Behaviors:

  • one constructor
  • add() an animal to the ArrayList and keeps track of largest price, it also updates the sum variable with the price of the animal
  • getAverage()
  • getMaximum()
  • toString()
  • whatIam() uses the for each loop to create a string with all the strings. Look at the sample output above.

This class should be very similar to the DataSet class.

2. The Animal class has the following members:
Attributes:

  • price (type double)
  • animal (type String)

Behaviors:

  • one constructor with one input argument, the “animal” or “price”
  • whatIam()
  • getPrice()
  • setPrice()

3. Animal’s children classes:
Each animal ( as an example: Bird) has the following members:
Attribute:

  • phrase (type String)

    • // For one choice of design. The other design, you do not have an instance field.

Behaviors:

  • one constructor
  • whatIam() returns “I am a bird”
  • getPrice()
  • a method of your choice unique to all animal’s child class. In the case of a bird, tweet() returns “I can sing”. This can be done in two different ways according to your design.

4. Driver and a bit more:

  • Create your own driver with all the necessary components to test all parts of your application.
  • Keep to the specification given so everyone can exchanges classes and have an easy integration into everyone’s application.
  • Maintain good documentation so everyone understands your code.
  • Talk to your classmates to find out what animal they are implementing so there is not unnecessary duplication.
  • Since the specifications for each class have been already defined above, work on the animal’s child class first so you can share with your classmates before the end of the period.

Chapter 7: Pet Shop v1 Questions

Pet Shop v1

Answer these questions:
1. What is the relationship between the Animal class and the Bird class?
2. Why doesn’t the java compiler give an error here: Animal tweety = new Bird(45.00);?
3. Can an Animal object “sing”? Explain
4. What collection is used in the PetSet class?
5. Why is the method whatIam() necessary in the Animal class?
6. Which whatIam() method is called in the PetShop class?
7. What statement shows late binding? Identify the line(s) of code where this takes place in your Pet Shop application.
8. What statement shows early binding? Give an example from your Pet Shop application.
9. What is the difference between the two bindings? Read below to help you answer this question.