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.