Till Next Time

The grades have been posted to VIP. This site will remain up until the next time I teach this class.

If you are a visitor to this site and want to take a free intro to Java class, simply watch the 62 Java tutorial videos (or, watch them without ads at udemy.com) and do the 25 Lab assignments (2-hour programming projects) and 10 homework assignments (longer programming projects) to get some practice. You can then the tests to see how much you have learned. Have fun!

Also, if you want to leave any advise to future students, you can do so in the comments to this post.

Final Tests

These are the final tests. If you want your graded final just send me an email and I will tell you when I'll be in my office so you can pick it up.

1. (10%) Implement a method that prints out all the numbers between 1 and 10,000,000 except that if the number is a multiple of 3 you will print "GO", if it is a multiple of 7 you print "Cocky" and if its a multiple of both 3 and 7 you print "Go Gamecocks". That is, the first part of the output looks like

   1
   2
   GO
   4
   5
   GO
   Cocky
   8
   GO
   10
   11
   GO
   13
   Cocky
   GO
   16
   17
   GO
   19
   20
   Go Gamecocks
   22
   ...and so on...

2. (10%) Implement the method int add(String a, String b) (notice, a and b are String) which adds the two arguments and returns the sum, but only if the two are integers. If they are not then it returns 0. For example

   add("5", "3") //returns 8
   add("bob", "3")  //returns 0
   add("bob", "alice")  //returns 0
   add("1.456", "8")  //returns 0
               

3. (10%) Implement a method String myCode(boolean[] msg) which translates the boolean array into a string using the following
   code:
   

   true → E
   false true → T
   false false true → A
   false false false → b

   For example,

   boolean[] m1 = {true};
           System.out.println(myCode(m1)); //prints "E"
   
           boolean[] m2 = {false, true, false, false, false};
           System.out.println(myCode(m2)); // "Tb"
   
           boolean[] m3 = {true, false, false, true, false, false, false};
           System.out.println(myCode(m3)); // "EAb"
   
           boolean[] m4 = {false, false, false, false, false, false, false, true};
           System.out.println(myCode(m4)); // "bbT"
               

4. (10%) Given that you have

   public enum SmartPhone {iphone3g, iphone4, iphone4s, android};
             

   Implement a method that takes SmartPhone as an argument and returns its price, as given by the following table
   
   

   Item	Price
   iphone 3g	300
   iphone 4	349
   iphone 4s	400
   android	200

5. (10%) What does the following program printout?
   

   public class PrintoutExceptions {
   
       public static String xkcd(int x) throws Exception{
           if (x < 0){
               return "Magnets";
           }
           else if (x < 5){
               return "Sticks";
           }
           else if (x % 2 == 1){
               return "Number:" + Integer.toString(x);
           }
           else throw new Exception("Caramba");
       }
   
   
       public static void main(String[] args) {
   
           int[] a = {-5,0,1,3,7,8};
           for (int i = 0; i < a.length; i++) {
               try {
                   System.out.println(i + "-" +  xkcd( a[i] ));
               } catch (Exception e) {
                   System.out.println("Ooops");
               }
           }
       }
   }

6. (10%) Does the program below run or crash? If it runs, show what it prints out when it runs. If it crashes, explain why.

   public class A {
   
       public String toString() {
           return "I am A";
       }
   }
   
   public class B extends A {
   
       public String toString() {
           return "I am B";
       }
   }
   
   public class C extends A {
   
       public String toString(){
           return "I am C";
       }
   }
   
   public class Q6 {
   
       public static void main(String[] args) {
           A[] as = new A[3];
           as[0] = new A();
           as[1] = new B();
           as[2] = new C();
           for (A a : as) {
               System.out.println(a.toString());
           }
       }
   } 

7. (10%) Given the following code:

   public class Person {
   
       private int money;
   
       private Person[] friends;
   
       public int minDistanceToMillionaire(){
           //TODO: implement this method
       }
   }

   implement the missing method using recursion, which will return the distance to the closest millionaire. For example, if the person is a millionaire (has money >= 1,000,000) then it will return 0. Otherwise, if the person has a friend who is a millionaire then it will return 1. Otherwise, if the person has a friend who has a friend that is a millionaire then it will return 2, and so on.
   You can assume that the graph does not have loops in it. That is, you will never see the same Person twice.
   
   
   
8. (10%) Assume that you are given a class called Person which has a method called int distanceTo(Person other) that returns the distance between where this person lives and where other lives.
   Implement a method

   ArrayList<Person> hasFriendsCloserThan(HashMap<Person, HashSet<Person>> socialNet, int n) 

   that takes as input a socialNet, which is a mapping between a Person and his friends, and returns the list of all the people who have at least one friend that lives a distance of less than n away from them.
   
   

The other test:

1. (10%)Implement a method that returns the sum of all the odd numbers between 1 and 1,000,000 except that those that are multiples of both 3 and 5 count double, while those that are multiples of either just 3 or just 3 don't get counted. For example, if the sum was just between 1 and 20 then you would return 98 because that is the sum of 1 + 7 + 11 + 13 + (15*2) + 17 + 19.
2. (10%) Implement a method int ssnToInt(String ssn) which, when given a a String represenation of a social security number that looks like "123-45-6789" returns the integer that represents that number, namely 123456789. If given a String that does not match then it returns -1. Specifically,

   ssnToInt("123-45-6789") //returns 123456789
   ssnToInt("123456789") //returns -1
   ssnToInt("12304506789") //returns -1
   ssnToInt("12389") //returns -1
   ssnToInt("7aa-90-879B") //returns -1
           

3. (10%) Implement a method String compress(String dna) which takes as input a String that contains only the characters A,C,G, and T, and then compresses the string by counting how many times each one appears consecutively. If a character appears more than once in a row the whole sequence is replaced by the character followed by the number of times it appeared in a row. For example:
   

   String d1 = "ACGT";
           System.out.println(compress(d1)); //prints ACGT
   
           String d2 = "AAAAACGT";
           System.out.println(compress(d2)); //prints A5CGT
   
           String d3 = "CCCTTTTAGGGGG";
           System.out.println(compress(d3)); //prints C3T4AG5
   
           String d4 = "AAAAAA";
           System.out.println(compress(d4)); //prints A6
               

4. (10%) Given that you have

   public enum Tablet {ipad, ipad2, newipad, galaxy}; 

   Implement a method that takes a SmartPhone and returns its price, as given by the following table
   
   

   Item	Price
   ipad	300
   ipad2	400
   newipad	600
   galaxy	300

   
   
5. (10%) What does the following program printout?
   

   public class PrintoutExceptions {
   
       public static String onion(int x) throws Exception{
           if (x % 2 == 1){
               return "Carrot";
           }
           else if (x <= 0){
               return "Sticks";
           }
           else if (x < 5){
               return "Number:" + Integer.toString(x);
           }
           else throw new Exception("Caramba");
       }
   
   
       public static void main(String[] args) {
   
           int[] a = {-5,0,1,3,7,8};
           for (int i = 0; i < a.length; i++) {
               try {
                   System.out.println(i + "-" +  onion( a[i] ));
               } catch (Exception e) {
                   System.out.println("Ooops");
               }
           }
       }
   }

6. (10%) Does the program below run or crash? If it runs, show what it prints out when it runs. If it crashes, explain why.

   public class A {
   
       public String toString() {
           return "I am A";
       }
   }
   
   public class B extends A {
   
       public String toString() {
           return "I am B";
       }
   }
   
   public class C extends A {
   
       public String toString(){
           return "I am C";
       }
   }
   
   public class Q6 {
       static void foo(A a){
           System.out.println(a.toString());
       }
   
       public static void main(String[] args) {
           foo(new A());
           foo(new B());
           foo(new C());
       }
   } 

7. (10%) Given the following code:

   public class Person {
   
       private Person mother;
   
       private Person father;
   
       public int generationsToOldestKnownAncestor(){
           //TODO: implement this method
       }
   
   }

   implement the missing method using recursion, which will return the distance to the oldest known ancestor. If we don't know a Person's mother or father we set those properties to null. For example, if a Person has both mother and father as null then the method should return 0. But, if the person has only a mother, who in turn has both mother and father set to null then it should return 1, and so on.
   You can assume that the graph does not have loops in it. That is, you will never see the same Person twice.
   
8. (10%) Implement the method

   String topPerson(HashMap<String, ArrayList<Double>> gradeMap)

   which takes as input a gradeMap, which is a mapping from a student's name to his list of grades, and which returns the name of the student with the highest grade. For example, if Alice has grades of 10, 20, 88, and Bob has grades of 77, 55, then it would return Alice because of her 88.
   
   

Final Test Point Distribution

The final test point distribution is below, these are points not grades. You will receive the actual grade along with your class grade in an email that I have just sent.

Lab 25: Social Zombies

In this lab you will write a program to simulate the spread of a virus among a population. Our virus of choice is the zombie virus. We assume that each person has the same number of friends, all chosen randomly from the population. Then, at each time step, all zombie persons will randomly choose one of their friends (zombie or not) and bite him. If the friend was not a zombie he will turn into a zombie. Zombie bites on zombies do nothing.

More specifically, for this lab you will implement a Person class and a Graph class.

The Person has (at least, you will need more methods):

• a data member friends that holds all his friends (which are of type Person)
• a boolean zombie which tells us if he is a zombie

The Graph class has (at least, you will need more methods)

• a people data member which holds all the people
• a getRandomPerson() which returns a random person from people
• a getRandomOther(Person p) which returns a random person from people that is not p
• a makeFriends(int x) which gives each person in the graph x randomly chosen friends
• a infectOne() method which infects (sets as a zombie) one random person
• a go() method which runs one step of the simulation: all the zombies bite one of their friends at random

Thus, the following main

public static void main(String[] args) {
    Scanner keyboard = new Scanner(System.in);
    System.out.print("Enter the number of people:");
    int numPeople = keyboard.nextInt();
    System.out.print("Enter the number of friends each person has:");
    int numFriends = keyboard.nextInt();
    Graph g = new Graph(numPeople);
    g.makeFriends(numFriends);
    //print it out, for testing.
    //System.out.println(g);
    g.infectOne();
    int day = 1;
    int count = 0;
    do {
      count = g.getNumZombies();
      System.out.println("Day " + day + ": Zombie count is " + count);
      g.go();
      day++;
    } while (count < numPeople);
    System.out.println("Zombieland");
   }

will print out something like:

Enter the number of people:100
Enter the number of friends each person has:5
Day 1: Zombie count is 1
Day 2: Zombie count is 2
Day 3: Zombie count is 4
Day 4: Zombie count is 10
Day 5: Zombie count is 21
Day 6: Zombie count is 35
Day 7: Zombie count is 59
Day 8: Zombie count is 77
Day 9: Zombie count is 89
Day 10: Zombie count is 91
Day 11: Zombie count is 96
Day 12: Zombie count is 97
Day 13: Zombie count is 97
Day 14: Zombie count is 99
Day 15: Zombie count is 100
Zombieland

Note that if you use a small number of friends (say, 2) then it might get into an infinite loop with a fixed number of zombies. This is because none of the zombies have a friend that is not a zombie (what you have then are 2 or more disconnected graphs, in graph theoretic terms). As always, turn it in on the dropbox.cse.sc.edu. You have an extra 48 hours to finish this lab, if you can't finish it during lab.

This is the last lab for the year. See you at the Final!

Test 3 Points Distribution

The points distribution for Test 3 is below. These are points, not grades. I will talk about grades in class.

Test 3

Here are the two tests, with some sample solutions.

1. (25%) What does the following program print out when run?
   

   public class Q1 {
   public static boolean swing (int strength) throws Exception{
           if (strength < 5)
               throw new Exception("Too weak");
           if (strength > 10)
               return false;
           return true;
       }
   public static void main(String[] args)  {
           int[] strengths = {5,6,-1,12};
           for (int s : strengths) {
               try {
                   if (swing(s))
                       System.out.println("Homerun");
                   else
                       System.out.println("Strike!");
               } catch (RuntimeException e){
                   System.out.println("You are OUT!");
               } catch (Exception e) {
                   System.out.println(e.getMessage());
               }
           }
           System.out.println("Done.");
       }
   } 

   
   
2. (25%)Given a text file called sales.txt which contains data that looks like

   aba 55.99
   akdkd8dj 12.95
   iwjwhe 4
   Iji8keJl 44.99
   ijdddawe 10.00
   ...and so on for many more rows...
   

   where each row represents one item that is for sale in a store. The first column is a String that uniquely identifies the item and the second column is a double that represents the price of the item. Write a program which
   
   
   
   1. Implements a simple Item class that can represent one item.
   2. In the main, your program reads the complete contents of the file sales.txt into an ArrayList<Item> variable called items.
   Answer:
   

   public class Item {
       private String sku;
   
       private double price;
   
       public Item(String sku, double price){
           this.sku = sku;
           this.price = price;
       }
   
       public String toString(){
           return sku + " " + price;
       }
       public static void main(String[] args) {
           try {
               Scanner in = new Scanner(new FileInputStream("sales.txt"));
               ArrayList<Item> items = new ArrayList<Item>();
               while (in.hasNext()){
                   String sku = in.next();
                   double price = in.nextDouble();
                   items.add(new Item(sku,price));
               }
               System.out.println(items);
           } catch (FileNotFoundException e) {
               e.printStackTrace();
           }
      }
   } 

3. (25%) Read over the code below and implement the empty method.

   import java.util.ArrayList;
   
   public class Q3 {
   
       private ArrayList<Q3> data;
   
       private Integer number;
   
       public Q3(Integer number){
           data = new ArrayList<Q3>();
           this.number = number;
       }
   
       public void add(Q3 q){
           data.add(q);
       }
   
       public void add(Integer number){
           data.add(new Q3(number));
       }
       
       /**
        * Calculates and returns the sum of all even numbers in
        * this object or in any of the ones in 'data', and so on
        * recursively.
        * @return The sum.
        */
       public int sumEven(){
           //TODO: implement this method
           int result = 0;
           if (number % 2 == 0)
               result = number;
           for (Q3 q: data){
               result += q.sumEven();
           }
           return result;
       }
       
   
       public static void main(String[] args) {
           Q3 q = new Q3(0);
           Q3 first = new Q3(1);
           q.add(first);
           Q3 second = new Q3(2);
           q.add(second);
           q.add(3);
           q.add(4);
           first.add(8);
           second.add(5); 
           System.out.println(q.sumEven());
       }
   }

   For example, when the main above is run it should print out

   14

4. (25%) Implement a method String mostFrequent(String s) which returns the 3-character substring that appears most frequently in s, or one of the most frequent if there is a tie. For example

   mostFrequent("AABABA") returns "ABA" because "ABA" appears twice
   mostFrequent("AAAAAB") returns "AAA" because it appears 3 times
   mostFrequent("ATATATA") returns "ATA" because it appears 3 times
               

   Answer:

   public static String mostFrequent(String seq){
           HashMap<String, Integer> count = new HashMap<String, Integer>();
           int max = 0;
           String maxKey = null;
           //add them all
           for (int i = 0; i <= seq.length() - 3; i++) {
               String key = seq.substring(i,i+3);
               if (count.containsKey(key))
                   count.put(key, count.get(key) + 1);
               else
                   count.put(key, 1);
               if (count.get(key) > max){
                   max = count.get(key);
                   maxKey = key;
               }
           }
           return maxKey;
       }

   
   

And, the other one:

1. (25%) What does the following program print out when run?
   
   

   public class Q1 {
   public static boolean pitch (String type) throws Exception {
           if (type.startsWith("f"))
               return true;
           if (type.startsWith("c"))
               return false;
           if (type.startsWith("x"))
               throw new Exception("Oops");
           return true;
       } 
   public static void main(String[] args)  {
           String[] types = {"fast", "foo", "curve", "xoom"};
           for (String t : types) {
               try {
                   if (pitch(t))
                       System.out.println("Hit");
                   else
                       System.out.println("Miss");
               } catch (RuntimeException e){
                   System.out.println("You hit the umpire");
               }
               catch (Exception e) {
                   System.out.println(e.getMessage());
               }
           }
           System.out.println("Done.");
       }
   } 

   
   
2. (25%) Given a text file called points.txt which contains data that looks like

   1.44 5.666
   12.999 0
   9.163 3.1415
   6 7
   5 6.999
   ...and so on for many more rows...
   

   where each row represents the x and y coordinates of a point in 2-dimensional space. Both columns are doubles. Write a program which
   
   
   
   1. Implements a simple Point class that can represent one point in space.
   2. In the main, your program reads the complete contents of the file points.txt into an ArrayList<Point> variable called points.
   Answer:
   

   public class Point {
   
       private double x;
       private double y;
       public Point(double x, double y){
           this.x = x;
           this.y = y;
       }
       public String toString(){
           return "(" + x + "," + y + ")";
       }
       public static void main(String[] args) {
           try {
               Scanner in = new Scanner(new FileInputStream("points.txt"));
               ArrayList<Point> points = new ArrayList<Point>();
               while (in.hasNext()){
                   double x= in.nextDouble();
                   double y = in.nextDouble();
                   points.add(new Point(x,y));
               }
               System.out.println(points);
           } catch (FileNotFoundException e) {
               e.printStackTrace();
           }
       }
   }

3. (25%) Read over the code below and implement the empty method.

   import java.util.ArrayList;
   
   public class Q3 {
   
       private ArrayList<Q3> data;
   
       private Integer number;
   
       public Q3(Integer number){
           data = new ArrayList<Q3>();
           this.number = number;
       }
   
       public void add(Q3 q){
           data.add(q);
       }
   
       public void add(Integer number){
           data.add(new Q3(number));
       }
   
       
       /**
        * Find if x is either equal to number, or equal to one of
        * the numbers in 'data', and so on recursively.
        * @param x the number we are looking for
        * @return true if x is there, false otherwise.
        */
       public boolean find(Integer x){
           //TODO: implement this method
           if (number == x)
               return true;
           for (Q3 q : data) {
               if (q.find(x))
                   return true;
           }
           return false;
       }
   
       public static void main(String[] args) {
           Q3 q = new Q3(0);
           Q3 first = new Q3(1);
           q.add(first);
           Q3 second = new Q3(2);
           q.add(second);
           q.add(3);
           q.add(4);
           first.add(8);
           second.add(5); 
           System.out.println(q.find(3));
           System.out.println(q.find(5));
           System.out.println(q.find(10));
       }
   }

   For example, when the main above is run it should print
   out

   true
   true
   false

4. (25%) Implement a method String mostPoints(String[] name, int[] points) which returns the name that has the most points, assuming that for all indeces i we have that points[i] has the number of points for name[i]. For example

      String[] name1 = {"a", "b", "c", "a", "b", "a"};
      int[] points1 =  { 1,   2,   7,   4 ,  3,   1};
      mostPoints(name1, points1); //returns "c" because it has 7
      // points and "a" has 6, and "b" has 5.
   
      String[] name2 = {"a", "b", "c", "a", "b", "a"};
      int[] points2 =  { 5,   2,   7,   4 ,  3,   1};
      mostPoints(name2, points2); //returns "a"
   
      String[] name3 = {"a", "a", "a", "a", "b", "c"};
      int[] points3 =  { 1,   1,   1,   1 ,  3,   2};
      mostPoints(name3, points3); //returns "a"

   Answer:

   public static String mostPoints(String[] name, int[] points){
           HashMap<String, Integer> count = new HashMap<String, Integer>();
           int max = 0;
           String maxKey = null;
   
           for (int i = 0; i < points.length; i++) {
               if (count.containsKey(name[i]))
                   count.put(name[i], points[i] + count.get(name[i]));
               else
                   count.put(name[i], points[i]);
               if (count.get(name[i]) > max){
                   max = count.get(name[i]);
                   maxKey = name[i];
               }
           }
           return maxKey;
       }

Lab 24: Cards

For this lab you will implement two classes, a Card and a Hand class.

The Card represt a card, which has a number and a Suit, there is also a Joker. The toString() method of this class will return the card's name in English, as shown below.

The Hand class uses a HashSet<Card> to hold a set of cards, which starts out empty. It has an add(Card c) which adds Card c to the hand. It has a methods makeFullDeck() which populates the hand with a full deck of cards (one Joker).

Finally, you will implement a public static HashSet<Hand> getAllHands(int numCards, Hand h) which returns the set of all the hands of numCards cards which can be created using the cards in hand h. You can do this the following recursive algorithm:

getAllHands(int numCards, Hand h)
  if numCards is 1
      then return the set of hands of just 1 card from h  
  hand = h.clone()
  result = empty set of hands
  foreach card in hand:
      remove card from hand
      allOtherHands =  getAllHands(numCards - 1, hand)
      add card to every hand in allOtherHands
      add allOtherHands to result
  return result

For example, the following main

public static void main(String[] args){
        Card twoClubs = new Card(2,Card.Suit.Clubs);
        System.out.println(twoClubs);
        
        Card oneSpades = new Card(1,Card.Suit.Spades);
        System.out.println(oneSpades);
        
        Card joker = new Card(0,Card.Suit.Hearts); //0 is the Joker 
        System.out.println(joker);
        
        Card kingDiamonds = new Card(13, Card.Suit.Diamonds); 
        System.out.println(kingDiamonds);
        
        Hand mine = new Hand();
        mine.add(twoClubs);
        mine.add(oneSpades);
        mine.add(joker); //0 is Joker
        mine.add(kingDiamonds);
        
        System.out.println("My hand is " + mine);

        //All the possible ways to pick 2 cards from mine
        System.out.println("All the possible ways to pick 2 cards from my hand are:");
        HashSet<Hand> pickTwo = getAllHands(2, mine);
        for (Hand hand : pickTwo) {
            System.out.println(hand);
        }
        System.out.println("Thus, there are " + pickTwo.size() + " possible ways.");
        System.out.println("");
        
        //All the possible ways to pick 3 cards from mine
        System.out.println("All the possible ways to pick 3 cards from my hand are:");
        HashSet<Hand> pickThree = getAllHands(3, mine);
        for (Hand hand : pickThree) {
            System.out.println(hand);
        }
        System.out.println("Thus, there are " + pickThree.size() + " possible ways.");
        System.out.println("");
        

        Hand deck = new Hand();
        deck.makeFullDeck(); //makes a full deck, with 1 Joker.
        System.out.println("The full deck is:");
        System.out.println(deck);
        
        System.out.println("All the possible ways to pick 2 cards from a full duck are:");
        HashSet<Hand> a = getAllHands(2, deck); //this will take a few seconds to run
        for (Hand hand : a) { //and a minute to print
            System.out.println(hand);
        }
        System.out.println("Thus, there are " + a.size() + " possible ways.");
        
        System.out.println("All the possible ways to pick 4 cards from a full duck are:");
        a = getAllHands(4, deck); //this will take a few seconds to run
        for (Hand hand : a) { //and a minute to print
            System.out.println(hand);
        }
        System.out.println("Thus, there are " + a.size() + " possible ways.");
    }

Should print out:

2 of Clubs
Ace of Spades
Joker
King of Diamonds
My hand is (Ace of Spades, King of Diamonds, 2 of Clubs, Joker)
All the possible ways to pick 2 cards from my hand are:
(Ace of Spades, 2 of Clubs)
(King of Diamonds, 2 of Clubs)
(Ace of Spades, King of Diamonds)
(King of Diamonds, Joker)
(Ace of Spades, Joker)
(2 of Clubs, Joker)
Thus, there are 6 possible ways.

All the possible ways to pick 3 cards from my hand are:
(Ace of Spades, King of Diamonds, Joker)
(Ace of Spades, King of Diamonds, 2 of Clubs)
(Ace of Spades, 2 of Clubs, Joker)
(King of Diamonds, 2 of Clubs, Joker)
Thus, there are 4 possible ways.

The full deck is:
(4 of Spades, 5 of Clubs, Queen of Spades, 8 of Spades, 8 of Clubs, Jack of Spades, Ace of Diamonds, Ace of Hearts, Queen of Clubs, 10 of Clubs, 3 of Spades, Queen of Diamonds, King of Spades, Ace of Spades, 6 of Diamonds, 9 of Clubs, King of Hearts, 7 of Clubs, 9 of Hearts, 4 of Hearts, Jack of Hearts, 3 of Diamonds, 4 of Diamonds, 10 of Hearts, Jack of Diamonds, 5 of Spades, Joker, 2 of Hearts, 9 of Diamonds, Ace of Clubs, 3 of Clubs, Jack of Clubs, King of Clubs, 5 of Diamonds, 10 of Diamonds, 7 of Diamonds, 8 of Hearts, King of Diamonds, 6 of Hearts, 9 of Spades, 7 of Spades, 6 of Clubs, 4 of Clubs, 3 of Hearts, 2 of Diamonds, 10 of Spades, 8 of Diamonds, 2 of Clubs, 6 of Spades, 5 of Hearts, Queen of Hearts, 2 of Spades, 7 of Hearts)
All the possible ways to pick 2 cards from a full duck are:
(Queen of Spades, Ace of Spades)
(Jack of Clubs, 5 of Hearts)
(2 of Diamonds, 5 of Clubs)
...and so on...
(King of Hearts, 3 of Diamonds)
(Jack of Clubs, 7 of Hearts)
(5 of Diamonds, Ace of Clubs)
Thus, there are 1378 possible ways.

All the possible ways to pick 4 cards from a full duck are:
(10 of Spades, 5 of Diamonds, Jack of Diamonds, Ace of Hearts)
(10 of Spades, 9 of Spades, Jack of Hearts, 7 of Diamonds)
(2 of Clubs, 7 of Hearts, Jack of Diamonds, 4 of Diamonds)
...and so on...
(6 of Diamonds, 9 of Diamonds, Ace of Hearts, 9 of Clubs)
(6 of Diamonds, 8 of Hearts, 7 of Clubs, King of Spades)
(King of Diamonds, 9 of Hearts, Jack of Hearts, 5 of Spades)
(Jack of Clubs, 10 of Hearts, 9 of Diamonds, 4 of Clubs)
(2 of Clubs, 4 of Spades, 4 of Clubs, 9 of Clubs)
Thus, there are 292825 possible ways.

Getting the recursive algorithm working might take you longer than the allotted lab time, so you can turn in this lab within 48 hours of the end time of your lab, in the dropbox.cse.sc.edu.

Hint: You will probably need to use an Iterator, because you need to Iterator.remove().

Lab and Homework Solutions

Here are my solutions to past labs:

• Lab 16: Iterator
• Lab 17: Exceptions
• Lab 18: Pride and Prejudice
• Lab 19: Sierpinsky
• Lab 20: Stock Plot
• Lab 21: Disjoint Sets
• Lab 22: Thumbs Up
• Lab 23: Linked List

and homeworks:

• HW 8: Employment data
• HW 9: Numbers
• HW 10: WordCloud

CodingBat Bonus

As in the previous tests, you will get an extra point in Test 3 for each one of the following codingbat sections you finish before Monday at noon: AP-1, Recursion-1 and Recursion-2. Remember that to get credit you have to login to coding bat, then click 'prefs' and under 'Share To' put jmvidal@gmail.com, also set your name to the name as it appears on my roster.

Also remember to study all of Chapters 9--12, as they cover material that is not in the codingbat questions but will be on the test. Do the programming problems from the back of these chapters.

Sample Programming Questions

Below are a few programming questions that are good practice for the next test and the final (some of these questions are from past topcoder competitions. We will be solving (some of) these in class today.

1. Implement a method minCycle that takes a String s as an argument and returns the shortest string which when repeated generates s. For example:
   

   minCycle("aaaaaaaa") returns "a"
   minCycle("ababababab") returns "ab"
   minCycle("ababa") returns "ababa"
   minCycle("12345") returns "12345"
   minCycle("123123123") returns "123"
   

2. Implement a method blackJackWinner(int[] points) which takes as an argument the points each player on the table ended up with and return the index of the winner, or -1 if there is a tie. Any player with more than 21 points loses. Of the remaining players, the one with the most points wins. If there is a tie, or if there are no winners, return -1. For example:
   

   blackJackWinner({1,2}) returns 1
   blackJackWinner({1,2,3,3,2}) returns -1
   blackJackWinner({21,22,19}) returns 0 
   blackJackWinner({1,20,15,22}) returns 1 
   blackJackWinner({22,23,25}) returns -1 //no winners
   

3. Implement a method int[] findTeam(boolean[][] canWork) which takes as input a 2-dimensional array of booleans that tells us wether a particular employee (row) can work with another (col) and returns an array containing the indexes of 3 employees that can work together in a team, or null if there is none. That is canWork[2][3] is true if employee 2 can work with 3. For example:
   

   findTeam({true,true,true},
            {true,true,true},
            {true,true,true}) returns {0,1,2}
   
   findTeam({true,true,true},
            {false,true,true},
            {true,true,true}) returns null
   
   findTeam({true,false,true,true},
            {true,true,true,true},
            {true,true,true,true},
            {true,true,true,true}) returns {1,2,3}
   
   
   findTeam({true,false,true,true},
            {true,true,false,true},
            {true,true,true,true},
            {true,true,true,true}) returns null
   

4. Implement a method String decrypt(String spell) which decrypts the 'spell' by reversing the order in which the 'A' and 'Z' characters appear in it, but leaves all other characters in the same position. For example:
   

   decrypt("AZ") returns "ZA"
   decrypt("ABZ") returns "ZBA"
   decrypt("ABACDA") returns "ABACDA"
   decrypt("ZBACDA") returns "ABACDZ"
   decrypt("AAATZZ") returns "ZZATAA"
   

Lab 23: Linked List

The code below is a slightly modified version of Listing 12.12 from your textbook. It implements a basic linked list. For this lab you will implement the missing methods in the code below.

/**
 * LinkedList.java
 * 
 * @author Jose M Vidal  A slight modification of Listing
 *         12.12 from the textbook. Created on Apr 5, 2012
 * 
 */

public class LinkedList<T> {

    /**
     * The ListNode is a private inner class of the LinkedList.
     */
    private class ListNode {
        /**
         * The data this node holds
         */
        private T data;

        /**
         * A reference to the next node on the list. next is null if this node
         * is the tail.
         */
        private ListNode next;

        public ListNode() {
            next = null;
            data = null;
        }

        public ListNode(T data, ListNode next) {
            this.data = data;
            this.next = next;
        }

        public T getData() {
            return data;
        }

        public ListNode getNext() {
            return next;
        }
     }

    private ListNode head;

    public LinkedList() {
        head = null;
    }

    /**
     * Adds data at the head of the list.
     * 
     * @param data
     */
    public void add(T data) {
        head = new ListNode(data, head);
    }

    /**
     * Adds data to the end of the list.
     * 
     * @param data
     */
    public void append(T data) {
    //TODO: add your code here
    }

    /**
     * Insert data into list so that it is at position index. If index is too
     * large, or small, we throw an exception.
     * 
     * @param index
     * @param data
     * @throws Exception
     */
    public void insert(int index, T data) throws Exception {
    //TODO: add  your code here
    }

    /**
     * Turns this list into a pretty String, like: 1 -> 5 -> 8 -> null
     */
    public String toString() {
    //TODO: add your code here
    }

    public static void main(String[] args) {
        LinkedList<Integer> l = new LinkedList<Integer>();
        l.add(13);
        l.add(5);
        l.add(8);
        System.out.println(l);
        l.append(55);
        l.append(21);
        System.out.println(l);
        System.out.println("insert 33 at position 3");
        try {
            l.insert(3, 33);
        } catch (Exception e) {
            e.printStackTrace();
        }
        System.out.println(l);

        System.out.println("insert 2 at position 0");
        try {
            l.insert(0, 2);
        } catch (Exception e) {
            e.printStackTrace();
        }
        System.out.println(l);

        System.out.println("insert 77 at position 7");
        try {
            l.insert(7, 77);
        } catch (Exception e) {
            e.printStackTrace();
        }
        System.out.println(l);

        System.out.println("try to insert 100 at position 100");
        try {
            l.insert(100, 100);
        } catch (Exception e) {
            System.out.println("ERROR:" + e.getMessage());
        }
        System.out.println(l);

    }

}

Add your methods so that when we run that main it prints out:

8 -> 5 -> 13 -> null
8 -> 5 -> 13 -> 55 -> 21 -> null
insert 33 at position 3
8 -> 5 -> 13 -> 33 -> 55 -> 21 -> null
insert 2 at position 0
2 -> 8 -> 5 -> 13 -> 33 -> 55 -> 21 -> null
insert 77 at position 7
2 -> 8 -> 5 -> 13 -> 33 -> 55 -> 21 -> 77 -> null
try to insert 100 at position 100
ERROR:index is longer than the list
2 -> 8 -> 5 -> 13 -> 33 -> 55 -> 21 -> 77 -> null

As always, turn it in on the dropbox.cse.sc.edu.

Iterators and Generics

Chapter 12 also talks about the Iterator interface. Iterators are a bit clumsier than using the 'foreach' (for (Type item: Collection) form), but they have the advantage that you can remove elements from the collection while iterating over it. The video below shows you how to use them:



The video below is a longer example showing how one might implement the Iterator interface in a class.




Finally, the next one shows you how to build your own generic class.

Lab 22: Thumbs Up

For this lab you will use what you learned about Swing to implement a very simple app like the one shown here. All that the app does is keep track of how many times each of the thumbs up or thumbs down buttons have been pressed.

As always, turn in your lab in the dropbox.cse.sc.edu

Augmented Reality

Its just a matter of programming...

Swing Applications

On Wednesdays' lecture we will be talking about the Java Swing library (Chapter 13 from the textbook, which you can download from the textbook website. This material will not be on the tests, but it will be on the next Lab. The video below also shows you how to build a simple Swing app.

In class I also demoed the windowbuilder plugin for eclipse, which lets you drag-and-drop your way to a working GUI. But, if you are planning on doing a lot of GUI drawing, you will want to use netbeans. It is much more stable.

Lab 21: Disjoint Sets

For this lab you will extract the set of unique words in two file and then determine the set of words that is in one file but not the other. We will be using Pride and Prejudice and Sense and Sensibility.

We want to find all the unique words in these texts. In other words, the set of all words that appear at least once on the text. You will read the words using the Scanner.next(). As you noticed in a previous lab, the .next() method only stops at whitepaces, this means that it will read thinks like "house." and "don't!"" as one word. This presents a problem when trying to find the set of unique words.

We can fix this problem by cleaning the words we read: removing any non-letter character from them. A simple way of doing that is by using the following method

/**
 * Clean up word by removing any non-letter characters from it and making it lower case
 * @param word
 * @return the cleaned up word
 */
    public String cleanWord(String word){
        //It is OK to use a regular String with + to create the new string, in CSCE145.
        //However, StringBuilder is much faster in this case because it does not
        // create a new String each time we append.
        StringBuilder w = new StringBuilder();
        char[] chars = word.toLowerCase().toCharArray();
        for (char c : chars) {
            if (Character.isLetter(c))
                w.append(c);
            }
        return w.toString();
    }

Your code for this lab will read and clean all the words from both Pride and Prejudice and Sense and Sensibility into HashSet of words. It will then printout how many unique words there are in each, as well as the number of words in one that are not in the other. The output I got is:

Numer of unique words in Pride and Prejudice: 7016
Numer of unique words in Sense and Sensibility: 7649
Number of Words in Sense and Sensibility but not in Pride and Prejudice : 3070
Number of Words in Pride and Prejudice but not in Sense and Sensibility: 2437
They are:
chambermaid
quadrille
holding
affords
luckless
extractions
quarrelsome
yesthere
halfhours
surmise
undervaluing
furnish
bribery
httpgutenbergorglicense
...and so on...your ordering might be different from mine...
jenkinson
george
breakfasted
hedge
musicbooks
coquetry
term
boulanger
halfamile
distrusted
cluster
culprit
phillipses

As always, your lab is due on the dropbox.cse.sc.edu.

HW 10: Word Cloud

Word Cloud for Pride and Prejudice

Word clouds, like the one you see on the right that I made with wordle, are created by first scanning over a text, figuring out which words are most common in that text but not in others and then printing these words in font size proportional to how often those words appear. For this homework you will write a program that finds the most frequent words in a text and prints out how many times they appear.

Your program will

1. Read in a text file, one word at a time.
2. Clean up the word by throwing away any non-letter characters, like ".,!? and turning it to lowercase.
3. If the word is not a stop word then keep track of how many times it appears on the file.
4. Printout the number of unique words you found and the top 20 most frequent words found along with the number of times they appear in the file.

Here is the output of the program for Pride and Prejudice

There are 6898 unique words.
mr 783
elizabeth 594
such 393
darcy 371
mrs 343
much 328
more 326
bennet 293
miss 283
one 266
jane 263
bingley 257
know 239
before 229
herself 224
though 221
never 220
soon 216
well 212
think 211

and here is for Sense and Sensibility

There are 7531 unique words.
elinor 616
mrs 525
marianne 488
more 403
such 359
one 317
much 287
herself 249
time 237
now 230
know 228
dashwood 224
though 213
sister 213
edward 210
miss 209
well 209
think 205
mother 200
before 198

The list of stop words you will use is

private static final String[] stopWordsList = {
  "a","able","about","after","all","almost","also","am","among","an",
  "and","any","are","as","at","be","because","been","but","by","can",
  "cannot","could","dear","did","do","does","either","else","ever",
  "every","for","from","get","got","had","has","have","he","her","hers",
  "him","his","how","however","i","if","in","into","is","it","its","just",
  "least","let","like","likely","may","me","might","most","must","my",
  "neither","no","nor","not","of","off","often","on","only","or","other",
  "our","own","rather","said","say","says","she","should","since","so",
  "some","than","that","the","their","them","then","there","these","they",
  "this","tis","to","too","twas","us","very","wants","was","we","were","what",
  "when","where","which","while","who","whom","why","will","with",
  "would","yet","you","your"};

Your program will use a HashMap to keep track of the counts. You might also want to use the a HashSet.

This homework is due Monday, 9 April @noon in the dropbox.cse.sc.edu.

ArrayLists and HashSets

Next week we will be covering Chapter 12, which talks about some of the built-in collection classes in Java, such as ArrayList and HashSet and HashMap:

Lab 20: Stock Plot

In Java, like in most programming languages, reading data from a URL is nearly identical to reading from a file, or reading from the keyboard. Java uses the URL class for reading data from a URL, as shown in this example.

Google provides us with historical price information for all the stocks. Specifically, if you go to the url http://www.google.com/finance/historical?q=AAPL&output=csv you will get a text file, in CSV format, for the prices of AAPL (Apple Computer) stock for the last year. To get a different stock simply replace AAPL in that url with the sticker symbol for your desired stock (try GOOG, GE, INTC).

For this lab you will start with the code below:

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.net.MalformedURLException;
import java.net.URL;

import javax.swing.JFrame;
import javax.swing.JOptionPane;
import javax.swing.JPanel;


public class PlotStock extends JPanel {

  /**
   * Initial Screen size.
   */
  public static final int WIDTH = 640;
  public static final int HEIGHT = 400;


  /**
   * Fetches stock data from google and prints it out to the
   * console.
   */
  private void getData(){
    try {
      //Get data on AAPL (Apple Computer) stock.
      //To get data on other sticker symbols simply replace AAPL with your
      // desired symbol, like GOOG.
      URL data = new URL("http://www.google.com/finance/historical?q=AAPL&output=csv");
      BufferedReader in = new BufferedReader(
        new InputStreamReader(data.openStream()));
      String inputLine;
      //TODO: rather than printing them out, we need to pick out the
      //  closing prices and save them for later plotting.
      while ((inputLine = in.readLine()) != null){
        System.out.println(inputLine);
      }
    }
    catch (MalformedURLException e) {
      e.printStackTrace();
    } catch (IOException e) {
      System.out.println("Uh Oh, I cannot reach the Internet.");
    }
   }

  /**
   * This method gets called when the class first gets create and also whenever the
   * window needs to be redraw, like when the user changes its size, de-iconifies it,
   * moves it, etc.
   */
  public void paintComponent(Graphics g){
    Graphics2D g2 = (Graphics2D) g;
    g2.setColor(Color.black);
    getData();
    //Draw a line from 10,10 to the bottom right of the window.
    //TODO: draw the line graph of the closing prices instead.
    g2.drawLine(10,10, getWidth(), getHeight());
    //Notice that getWidth() and getHeight() can be used to give us
    // the width and height of the current window (which might be 
    // different from the original because the user changed it).
  }

  public static void main(String[] args) {
    String symbol = JOptionPane.showInputDialog("Enter Ticker Symbol:");
    if (symbol == null) System.exit(0); //quit if user hit Cancel
    JFrame frame = new JFrame("Window"); //frame is the window
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    PlotStock panel = new PlotStock(); //panel is the graphics area where we can draw
    frame.add(panel); //put the panel inside the window
    frame.setSize(WIDTH,HEIGHT); //set the window size to 640x400 pixels
    frame.setVisible(true); 
  }
}

When you run it you will notice that it first opens up a window asking you for a ticker symbol (try AAPL) and then prints out the prices for that stock on the console and pops up a graphic window with just a line.

For this lab you will change this program so that instead of printing out to the console it will draw a line chart of the closing prices of the given stock. Notice that the closing price is one of the columns on the give CSV file. You can ignore all the other columns. Your final plot should look something like the figure shown.

TIP: String.split(",",0) is very useful for parsing the CSV file.

Once you get it working, try re-sizing the window with your mouse: drag a corner to make the window bigger. Did your plot grow with the window? If not, that is OK, it is good enough for this lab.

However, if you want a fun little challenge (definitely doable within the lab time), try to make it so your plot stretches to fit the window. Note that you can get the current size of the window using getWidth() and getHeight(), as shown in the code. The rest is just a little bit of programming. You will need to find the max and min closing prices, and number of days of data, then scale these to fit the current window.

As always, turn it in at the dropbox.cse.sc.edu.

Lab 19: Sierpinsky Triangle

For this lab you will implement a recursive method that draws the Sierpinsky Triangle to various levels. You will start out with the following code:

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;

import javax.swing.JFrame;
import javax.swing.JPanel;

/**
 * Triangle.java
 * @author Jose M Vidal 
 * Created on Mar 19, 2012
 * 
 */

public class Triangle extends JPanel {

  public void drawTriangle(Graphics2D g, int x1, int y1, int x2, int y2, int x3, int y3){
    g.drawLine(x1, y1, x2, y2);
    g.drawLine(x2, y2, x3, y3);
    g.drawLine(x3, y3, x1, y1);
  }
 
  public void paintComponent(Graphics g){
    Graphics2D g2 = (Graphics2D) g;
    g2.setColor(Color.black);
    drawTriangle(g2,1,640, 320,0, 640,640);
  }

  public static void main(String[] args) {
    JFrame frame = new JFrame("Window"); //frame is the window
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    Triangle panel = new Triangle(); //panel is the graphics area where we can draw

    frame.add(panel); //put the panel inside the window
    frame.setSize(650,680); //set the window size to 640x640 pixels
    frame.setVisible(true); 
   }
}

which simply draws a triangle and change it so that it draws the Sierpinsky triangle to any desired level.

That is, change the drawTriangle method so that it takes as argument another variable, the level. If the level is 0 it will draw the triangle exactly as it does now.

But, if the level is 1 it will instead draw the 3 triangles, as shown in the first figure. In other words, it will draw three Sierpinsky level 0 triangles: one on the bottom left, one on the top, and one on the bottom right. Note that we do not draw the upside-down triangle in the middle, that one is just a side-effect from drawing the three other triangles. Similarly, if the level is 2 we draw 3 Sierpinsky level 2 triangles: one on the bottom left, one on the top, and one on the bottom right, and so on.

The program should work for all levels but, I note that running it for levels greater than 12 will take significant amounts of time, and will not change the look of the triangle because you have already reached the limits of the resolution (640 by 640 pixels)

As always, turn this in on the dropbox.cse.sc.edu.

Oh, and, how might this be related to exponential functions as discussed in class? Vihart explains: