Commits

Eric Johnson committed 960c0a6

adding uw facilitator worksheets

Comments (0)

Files changed (138)

facilitator/tcss143/09sp/LinkedListProblems.pdf

Binary file added.

facilitator/tcss143/09sp/wk01.tex

+\documentclass[11pt]{article}
+\usepackage{amsmath}
+\usepackage{fancyhdr}
+\pagestyle{fancyplain}
+\lhead{TCSS 390A}
+\chead{Worksheet \#1}
+\rhead{March 30, 2009}
+
+\begin{document}
+
+\section{Basic Code Analysis}
+\subsection{Qualitative}
+\subsubsection*{Understanding and describing code}
+\begin{enumerate}
+\item Insert comments in the code below. Make sure to indicate \emph{what} the code does, not how it does it.
+\begin{verbatim}
+
+
+
+
+public void mystery(int number, int factor) {
+
+    if (Math.abs(factor) > 1) {
+        
+        int count = 0;
+        
+        int temp = number;
+
+        while (number % factor == 0) {
+
+            number = number / factor;
+
+            count += 1;
+        }
+
+        if (count > 0)
+            
+            System.out.println(``Equation: '' + temp + 
+                `` = '' + number + `` * ('' + factor + ``)^'' + count);
+        
+        else
+
+            System.out.println(``Factor '' + factor + 
+                `` not present in '' + number);
+    
+    } else 
+        System.out.println(``Trivial or invalid factor submitted.'');
+}
+\end{verbatim}
+\item Are there any parameter values one should watch out for? What would you do differently coding \verb!mystery!?
+\\\\\\*
+\newpage
+\item Insert comments in the code below. Make sure to indicate \emph{what} the code does, not how it does it.
+\begin{verbatim}
+
+
+
+
+
+public void mystery2(int[] data, int last) {
+    int temp;
+
+    for (int i = 0; i <= last; i++) {
+
+
+        temp = data[i];
+
+
+        data[i] = data[last - i];
+
+
+        data[last - i] = temp;
+
+    }
+}
+\end{verbatim}
+\item Is there anything unusual about \verb!mystery2!? Can you guess at the method's intent? Does intent match implementation? What would you do differently?
+\\\\\\*
+\newpage
+\item The code below needs some comments. Include some. Furthermore, evaluate \verb!mystery3(7, 1, 1)!.
+\begin{verbatim}
+
+
+
+
+
+
+
+
+public int mystery2(int n, int r0, int r1) {
+
+    if (n <= 1)
+
+
+        return r1;
+
+
+    else
+
+
+        return mystery2(n - 1, r1, r0 + r1);
+}
+\end{verbatim}
+\item Does the code resemble anything you've seen before? What is unusual about \verb!mystery3!? What advantages exist in the present implementation? What would you do differently?
+\newpage
+\subsubsection*{Evaluating and analyzing code}
+\item Evaluate the method \verb!mystery3! for $n \in\{2,3,4,5,6,7,8,9\}$
+\begin{verbatim}
+public int mystery3(int n) {
+    return coll(1, n);
+}
+
+private int coll(int iterations, int n) {
+    if (n <= 1)
+        return iterations;
+    else {
+        iterations += 1;
+        if ((n % 2) == 0) 
+            return coll(iterations, n / 2);
+        else
+            return coll(iterations, 3 * n + 1);
+    }
+}
+\end{verbatim}
+\newpage
+
+\item Is there anything you would do differently coding \verb!mystery3!?
+\\\\\\\\\\*
+\item Will the method \verb!mystery3! always return a value? Explore this.
+\newpage
+
+\subsubsection*{Programming with Arrays}
+\item Write a method named \verb!find(int val, int[] list)! that accepts an integer and an Array of integers as its parameters and returns the index of the first instance of the integer \verb!val! in \verb!list!, or -1 if it is not present.
+\newpage
+
+\item Write a method named \verb!countOccurrence(int val, int[] list)! that accepts an integer and an Array of integers as its parameters and returns the number of times the integer \verb!val! can be found in \verb!list!, or -1 if it is not present.
+\newpage
+
+\item Write a method named \verb!isPalindrome(char[] word)! that accepts a \verb!char! Array as its parameter and returns whether the Array is a palindrome. A palindrome is a word, phrase, number, or other sequence that can be read the same way in either direction.
+\newpage
+
+\item Write a method named \verb!cartesian(int[] a, int[] b)! that accepts two Arrays of inteters as its parameters and returns an Array of Points (as in ch. 8) representing all possible pairs of integers whose first coordinate comes from the array \verb!a!, and whose second coordinate comes from the array \verb!b!.
+\newpage
+\end{enumerate}
+
+\end{document} 

facilitator/tcss143/09sp/wk02.tex

+\documentclass[11pt]{article}
+\usepackage{amsmath}
+\usepackage{fancyhdr}
+\pagestyle{fancyplain}
+\lhead{TCSS 390A}
+\chead{Worksheet \#2}
+\rhead{April 7, 2009}
+
+\begin{document}
+\section{Warm-up}
+\subsection{Combinatorics}
+\begin{enumerate}
+\item Suppose $n$ people show up to a party and begin to mingle. At each point, the group of $n$ people can be separated into two groups - those people who have shaken hands with an even number of people, and those people who have shaken hands with an odd number of people. Prove that the amount of people who have shaken hands with an odd number of people is an even number.
+\\\\\\\\\\\\\\*
+\item Given a 4 x 4 square, provide a configuration of 7 stars such that no matter which two rows and columns are deleted, the remaining squares always contain at least one star.
+\\\\\\\\\\\\\\*
+\item Given a 4 x 4 square, show that it is impossible to provide a configuration of only 6 stars such that no matter which two rows and columns are deleted, the remaining squares always contain at least one star.
+\newpage
+\subsection{Basic Code Analysis}
+\item Calculate the value of \verb!sum! below in terms of $n$.
+\begin{enumerate}
+\item
+\begin{verbatim}
+sum = 0;
+for ( i = 0; i <= n; i++ )
+    for ( j = 0; j <= 50; j++ )
+        sum++;
+
+
+
+
+\end{verbatim}
+\item
+\begin{verbatim}
+sum = 0;
+for ( i = 0; i <= n; i++ )
+    for ( j = 1; j <= n; j *= 2 )
+        sum++;
+
+
+
+\end{verbatim}
+\item
+\begin{verbatim}
+sum = 0;
+for ( i = 0; i <= n; i++ )
+    for ( j = n * n; j > 0; j-- )
+        sum++;
+
+
+
+\end{verbatim}
+\item
+\begin{verbatim}
+sum = 0;
+for ( i = 0; i <= n; i++ )
+    for ( j = 0; j < i; j++ )
+        sum++;
+
+
+
+\end{verbatim}
+\end{enumerate}
+
+\section{Inheritance, Polymorphism, and Interfaces}
+\subsection{Inheritance}
+\item For the following classes, use inheritance to reduce code duplication and increase code flexibility.
+\begin{verbatim}
+public class EconomyCar {
+    private int maxSpeed;
+    private int fuelCapacity;
+    private int fuelEfficiency;
+    private String name;
+    
+    public EconomyCar() {
+        maxSpeed = 90;
+        fuelCapacity = 12;
+        fuelEfficiency = 50;
+        name = ``Economy Car'';
+    }
+
+    public int maxTravelDistance() {
+        return fuelCapacity * fuelEfficiency;
+    }
+
+    public int minTravelTime(int distance) {
+        return distance / maxSpeed;
+    }
+
+    public String toString() {
+        return name;
+    }
+}
+
+public class PerformanceCar {
+    private int maxSpeed;
+    private int fuelCapacity;
+    private int fuelEfficiency;
+    private String name;
+    
+    public PerformanceCar() {
+        maxSpeed = 180;
+        fuelCapacity = 16;
+        fuelEfficiency = 20;
+        name = ``Performance Car'';
+    }
+
+    public int maxTravelDistance() {
+        return fuelCapacity * fuelEfficiency;
+    }
+
+    public int minTravelTime(int distance) {
+        return distance / maxSpeed;
+    }
+
+    public String toString() {
+        return name;
+    }
+}
+
+public class Bicycle {
+    private int maxSpeed;
+    private boolean multispeed;
+    private String name;
+    
+    public Bicycle(boolean multispeed) {
+        maxSpeed = 40;
+        this.multispeed = multispeed;
+        name = ``Bicycle'';
+    }
+
+    public boolean isMultispeed() {
+        return multiSpeeed;
+    }
+
+    public int minTravelTime(int distance) {
+        return distance / maxSpeed;
+    }
+
+    public String toString() {
+        return name;
+    }
+}
+
+public class Human {
+    private int maxSpeed;
+    private boolean sprint;
+    private String name;
+    
+    public Human(boolean sprint) {
+        maxSpeed = 18;
+        this.sprint = sprint;
+        name = ``Human'';
+    }
+
+    public boolean canSprint() {
+        return canSprint;
+    }
+
+    public void setSprint(boolean sprint) {
+        this.sprint = sprint;
+    }
+
+    public int minTravelTime(int distance) {
+        return distance / maxSpeed;
+    }
+
+    public String toString() {
+        return name;
+    }
+}
+\end{verbatim}
+\newpage
+.
+\newpage
+\subsection{Polymorphism}
+\item Create a method \verb!displaySpecs(MotorizedVehicle mv)! that displays its name, the maximum possible travel distance on a single tank of gas and the minimum amount of time needed to travel that distance.
+\\\\\\\\\\\\\\\\\\\\\\*
+\item Create a method \verb!fastest(Vehicle[] vehicles)! that displays the name of the fastest Vehicle in the Array.
+\\\\\\\\\\\\\\\\\\\\\\*
+\item Create a method \verb!average(Vehicle[] vehicles)! that displays the average maximumSpeed for the Array.
+\newpage
+\item Create a method that takes a distance and a ``tired'' indicator and returns a minimum travel time that is twice that of a non-tired indicator.
+\\\\\\\\\\\\*
+\item How could a programmer quickly add the property ``tired'' to the four implementations without changing the four implementations? Ok, do it now.
+\\\\\\\\\\\\\\\\*
+\item Create two new classes - MountainBike and RoadBike - that are similar to Bike in all ways except each implement the methods \verb!changeGear(int newValue)! and \verb!changeCadence(int newValue)! in some way.
+\newpage
+\subsection{Interfaces}
+\item Write an interface called \verb!Fuelable! and modify your existing code so that the four implementations of vehicles will be forced to implement a \verb!getFuel()! method. Can your interface contain a constructor? What can your interface contain?
+\\\\\\\\\\*
+\item Write a method that accepts a Vehicle array and calls the \verb!getFuel()! method on those elements that are tired, updating the tired property to false, and returning the number of elements that were tired.
+
+\newpage
+\section{More Basic Code}
+\subsection{Carry-over}
+\item Write a method named \verb!cartesian(int[] a, int[] b)! that accepts two Arrays of inteters as its parameters and returns an Array of Points (as in ch. 8) representing all possible pairs of integers whose first coordinate comes from the array \verb!a!, and whose second coordinate comes from the array \verb!b!.
+\newpage
+\end{enumerate}
+
+\end{document} 

facilitator/tcss143/09sp/wk03.tex

+\documentclass[11pt]{article}
+\usepackage{amsmath}
+\usepackage{fancyhdr}
+\pagestyle{fancyplain}
+\lhead{TCSS 390A}
+\chead{Worksheet \#3}
+\rhead{April 7, 2009}
+
+\begin{document}
+\section{Warm-up}
+\subsection{Basic Arithmetic}
+\begin{enumerate}
+\item Suppose a ribbon is wrapped once around the equator of the Earth (assuming the Earth is a perfect sphere and you had a ribbon long enough).  If, everywhere simultaneously, the ribbon was lifted straight up one foot off the surface of the Earth, how much extra ribbon would you need to maintain a complete circle of ribbon one foot high everywhere?
+\\\\\\\\\\*
+\item Prove that $n^5 - n$ is divisible by 5, for every integer $n$.
+\\\\\\\\\\\\\\\\\\\\\\\\\\*
+\item Prove that there does not exist a non-zero integer that is increased five times when the initial digit is transfered to the end. 
+\newpage
+
+\subsection{Logic}
+\item A traveler having no money, but owning a gold chain having seven links, is accepted at an inn on the condition that he pay one link per day for his stay. If the traveler is to pay daily, but may take change in the form of links previously paid, and if he remains seven days, what is the least number of links that must be cut out of the chain?
+\\\\\\\\\\\\\\\\\\\\*
+\item Two-hundred students are positioned in 10 rows, each containing 20 students. From each of the 20 columns thus formed the shortest student is selected, and the tallest of these 20 (short) students is tagged A. These students now return to their initial places. Next the tallest student in each row is selected, and from these 10 (tall) students the shortest is tagged B. Which of the two tagged students is the taller (if they are different people)?
+\newpage
+
+\section{Inheritance, Polymorphism, and Interfaces}
+\subsection{Inheritance}
+\item For the following classes, use inheritance to reduce code duplication and increase code flexibility.
+\begin{verbatim}
+public class EconomyCar {
+    private int maxSpeed;
+    private int fuelCapacity;
+    private int fuelEfficiency;
+    private String name;
+    
+    public EconomyCar() {
+        maxSpeed = 90;
+        fuelCapacity = 12;
+        fuelEfficiency = 50;
+        name = ``Economy Car'';
+    }
+
+    public int maxTravelDistance() {
+        return fuelCapacity * fuelEfficiency;
+    }
+
+    public int minTravelTime(int distance) {
+        return distance / maxSpeed;
+    }
+
+    public String toString() {
+        return name;
+    }
+}
+
+public class PerformanceCar {
+    private int maxSpeed;
+    private int fuelCapacity;
+    private int fuelEfficiency;
+    private String name;
+    
+    public PerformanceCar() {
+        maxSpeed = 180;
+        fuelCapacity = 16;
+        fuelEfficiency = 20;
+        name = ``Performance Car'';
+    }
+
+    public int maxTravelDistance() {
+        return fuelCapacity * fuelEfficiency;
+    }
+
+    public int minTravelTime(int distance) {
+        return distance / maxSpeed;
+    }
+
+    public String toString() {
+        return name;
+    }
+}
+
+public class Bicycle {
+    private int maxSpeed;
+    private boolean multispeed;
+    private String name;
+    
+    public Bicycle(boolean multispeed) {
+        maxSpeed = 40;
+        this.multispeed = multispeed;
+        name = ``Bicycle'';
+    }
+
+    public boolean isMultispeed() {
+        return multiSpeeed;
+    }
+
+    public int minTravelTime(int distance) {
+        return distance / maxSpeed;
+    }
+
+    public String toString() {
+        return name;
+    }
+}
+
+public class Human {
+    private int maxSpeed;
+    private boolean sprint;
+    private String name;
+    
+    public Human(boolean sprint) {
+        maxSpeed = 18;
+        this.sprint = sprint;
+        name = ``Human'';
+    }
+
+    public boolean canSprint() {
+        return canSprint;
+    }
+
+    public void setSprint(boolean sprint) {
+        this.sprint = sprint;
+    }
+
+    public int minTravelTime(int distance) {
+        return distance / maxSpeed;
+    }
+
+    public String toString() {
+        return name;
+    }
+}
+\end{verbatim}
+\newpage
+.
+\newpage
+\subsection{Polymorphism}
+\item Create a method \verb!displaySpecs(MotorizedVehicle mv)! that displays its name, the maximum possible travel distance on a single tank of gas and the minimum amount of time needed to travel that distance.
+\\\\\\\\\\\\\\\\\\\\\\*
+\item Create a method \verb!fastest(Vehicle[] vehicles)! that displays the name of the fastest Vehicle in the Array.
+\\\\\\\\\\\\\\\\\\\\\\*
+\item Create a method \verb!average(Vehicle[] vehicles)! that displays the average maximumSpeed for the Array.
+\newpage
+\item Create a method that takes a distance and a ``tired'' indicator and returns a minimum travel time that is twice that of a non-tired indicator.
+\\\\\\\\\\\\*
+\item How could a programmer quickly add the property ``tired'' to the four implementations without changing the four implementations? Ok, do it now.
+\\\\\\\\\\\\\\\\*
+\item Create two new classes - MountainBike and RoadBike - that are similar to Bike in all ways except each implement the methods \verb!changeGear(int newValue)! and \verb!changeCadence(int newValue)! in some way.
+\newpage
+\subsection{Interfaces}
+\item Write an interface called \verb!Fuelable! and modify your existing code so that the four implementations of vehicles will be forced to implement a \verb!getFuel()! method. Can your interface contain a constructor? What can your interface contain?
+\\\\\\\\\\*
+\item Write a method that accepts a Vehicle array and calls the \verb!getFuel()! method on those elements that are tired, updating the tired property to false, and returning the number of elements that were tired.
+
+\end{enumerate}
+\end{document} 

facilitator/tcss143/09sp/wk04.tex

+\documentclass[10pt]{article}
+\usepackage{amsmath}
+\usepackage{fancyhdr}
+\pagestyle{fancyplain}
+\lhead{TCSS 390A}
+\chead{Worksheet \#4}
+\rhead{April 20, 2009}
+
+\begin{document}
+
+\section{Warm-up}
+\subsection{Combinatorics}
+\begin{enumerate}
+\item Among 80 similar coins, there is one counterfeit known to be lighter. Using only a pan balance, what is the minimum number of weighings needed to find the counterfeit?
+\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
+\subsection{Java Review}
+\item Answer the questions about constructors below:
+\begin{enumerate}
+\item Can a class have more than one constructor? 
+\\\\
+\item Are there any restrictions? 
+\\\\
+\item If one does not declare a constructor, what happens? 
+\\\\
+\item If a class is extending another, how does the extending class call the parent constructor? 
+\\\\
+\item How does a parent class ``hide'' a constructor from an extending class?
+\end{enumerate}
+\newpage
+\item Answer the questions about abstract classes below:
+\begin{enumerate}
+\item What are the characteristics of an abstract class? 
+\\\\
+\item How are they similar to concrete classes? 
+\\\\
+\item How are they different?
+\\\\
+\end{enumerate}
+\item Answer the questions about interfaces below:
+\begin{enumerate}
+\item What are the characteristics of an interface? 
+\\\\
+\item How are they similar to/different than concrete classes?  Abstract classes?
+\\\\
+\item What are some reasons for the existence of interfaces in java?
+\\\\
+\end{enumerate}
+\item Answer the questions about generic classes below:
+\begin{enumerate}
+\item What is a generic class? How are generic classes useful? 
+\\\\
+\item Give some examples of generic classes.
+\\\\
+\end{enumerate}
+\item The interface \verb!Comparable! guarantees an ordering for the objects of a class. Answer the questions about this interface below:
+\begin{enumerate}
+\item What method must be implemented by a class that adheres to the \verb!Comparable! interface?
+\\\\
+\item What is the return type of this method? 
+\\\\
+\item What common types in Java implement the \verb!Comparable! interface?  
+\end{enumerate}
+\newpage
+
+\section{Qualitative}
+\subsection{Code Analysis}
+\item The \verb!insertItem! method's intent is to correctly insert the \verb!Integer item! into the ascending sorted \verb!ArrayList<Integer>! of \verb!items!. Find the problems in the code (if any) and fix them. It is often very helpful to use a simple example and step throught the code. Any ideas on running time in terms of the size of the \verb!ArrayList!?
+\begin{verbatim}
+public void insertItem(Integer item, ArrayList<Integer> items) {
+    int location = 0;
+    boolean found = false;
+
+    while (location < items.size()) {
+
+        if (item <= items.get(location))
+
+            found = true;
+
+        else
+
+            location += 1;
+    }
+
+    for (int index = 0; index < location; index++)
+
+        items.set(index, items.get(index - 1));
+
+    items.set(location, item);
+
+}
+\end{verbatim}
+\newpage
+\item The \verb!binarySearch! method's intent is to determine if the \verb!Integer value! is a member of the ascending sorted \verb!ArrayList<Integer>! of \verb!items! and return its index (similar to the functionality of the \verb!indexOf! method). It is often very helpful to use a simple example and step throught the code. Find the problems in the code (if any) and fix them. Again, any ideas on the running time in terms of the size of the \verb!ArrayList!?
+\begin{verbatim}
+public int binarySearch(ArrayList<Integer> items, int value, 
+                                          int low, int high) {
+    int mid;
+    if (high < low)
+
+        return -1;
+
+    mid = (low + high) / 2;
+
+    if (items.get(mid) < value)
+
+        return binarySearch(items, value, low, mid - 1);
+
+    else {
+        
+        if (items.get(mid) > value)
+            
+            return binarySearch(items, value, mid + 1, high);
+
+        else
+        
+            return mid;
+    }
+
+}
+\end{verbatim}
+\newpage
+
+\subsection{Collections and their properties}
+\item What is a collection? What is a \verb!Collection! in Java? From memory, list as many methods in \verb!Collection! as you can. Now, using reference material, if necessary and given time, list the methods in \verb!Collection!, from ``most important'' to ``least important''.
+\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
+\item There are two main implementing ``branches'' of \verb!Collection!, the interfaces \verb!List! and \verb!Set!. What are some of the main differences between these two branches of implementations?  
+\\\\\\\\\\\\\\\\*
+\item Under the \verb!List! interface, there are two main implementations, the classes \verb!LinkedList! and \verb!ArrayList!. What are some of the main differences between these two main implementations?
+\newpage
+
+\section{Quantitative}
+\subsection{Programming with Lists}
+\item Write a method named \verb!sortedMerge! that accepts two \verb!List<Comparable>! objects, assumed to be ascending sorted, and merges the lists, returning an array that is the sorted merge of the two lists. For example, if the lists contain the values [1, 4, 5, 9] and [2, 6, 7], then the returned array would be [1, 2, 4, 5, 6, 7, 9]. 
+\newpage
+
+\subsubsection{Programming with Sets}
+\item Write a method named \verb!powerSet! that accepts a \verb!Set! as its parameter and returns the powerset of that set. The powerset is the set of all subsets of the given set. For example, if the set is $S = \{a, b, c\}$ then the powerset is $\wp(S) = \{\emptyset,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}$.
+\end{enumerate}
+\end{document} 

facilitator/tcss143/09sp/wk05.tex

+\documentclass[10pt]{article}
+\usepackage{amsmath}
+\usepackage{fancyhdr}
+\pagestyle{fancyplain}
+\lhead{TCSS 390A}
+\chead{Worksheet \#5}
+\rhead{April 27, 2009}
+
+\begin{document}
+
+\section{Quantitative}
+\subsection{Abstract Classes and Interfaces}
+The following questions concern an abstract super class MusicPlayer.java and five of its implementing children: Amarok.java, ITunes.java, MediaPlayer.java, Rythmbox.java, and Songbird.java. Be sure to leave lots of room for additions in your code. All five concrete classes must have the following, but may have additional supporting methods:
+\begin{itemize}
+\item a \verb!String name! private field with a value that is set in the constructor. 
+\item a \verb!Integer xFactor! private field with a value that is set in the constructor.
+\item a \verb!SoundFile currentlyPlaying! private field, initially null. A public getter must be included. 
+\item a \verb!play(SoundFile soundFile)! public method that sets the \verb!currentlyPlaying! field to the value passed in, and ``plays'' the file by writing ``I'm playing'' to standard out.
+\item a \verb!stop()! method. This method may behave differently for each implementing class. In all cases, however, a call to \verb!isPlaying! must return \verb!false! directly after a call to \verb!stop!, and must write ``I'm not playing'' to standard out.
+\item a \verb!boolean isPlaying()! public method that must return whether the player is playing music or not. Directly after a call to \verb!play!, this method should return \verb!true! and, after directly construction, should return \verb!false!. Use your own discretion on implementation.
+\end{itemize}
+\newpage
+
+\begin{enumerate}
+\item Develop the abstract super class MusicPlayer.java that supports the above requirements.
+\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
+\item Develop the five concrete classes. The \verb!stop()! method must set the \verb!currentlyPlaying! field to \verb!null! for Amarok, MediaPlayer, and Rythmbox, while it must leave the value of \verb!currentlyPlaying! for ITunes and Songbird to what it was when \verb!play! was called.
+\newpage
+.
+\newpage
+
+\item The classes ITunes and Songbird implement an overloaded method \verb!play()! that takes no arguments that plays the \verb!currentlyPlaying! file. Be sure to throw an exception if \verb!currentlyPlaying! is \verb!null!.
+\\\\\\\\\\\\\\\\\\\\\\\\*
+\item The classes ITunes and MediaPlayer implement the \verb!EvilInterface! interface, which has two methods \verb!void removeOptions()! and \verb!void bundle()!. Be sure they do implement this interface.
+\\\\\\\\\\\\\\\\\\\\\\\\*
+\item The classes Amarok, Rythmbox, and Songbird implement the \verb!OpenSource! interface, which has one method \verb!void contribute(Programmer programmer, Code code)!. Be sure they do implement this interface.
+\newpage
+
+\item Make sure that MusicPlayer.java class implements Comparable and compares two instances of MusicPlayer according to the value of \verb!xFactor!.
+\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
+\item Design a static method called \verb!sortPlayers! within MusicPlayer that takes a list of MusicPlayer instances and returns the list sorted using this comparison.
+\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
+\item Show an example piece of code that uses this static method for a list comprised of exactly one instance each of the five classes.
+\newpage
+
+\subsection{Programming with Lists}
+\item Write a method named \verb!sortedMerge! that accepts two \verb!List<Comparable>! objects, assumed to be ascending sorted, and merges the lists, returning an array that is the sorted merge of the two lists. For example, if the lists contain the values [1, 4, 5, 9] and [2, 6, 7], then the returned array would be [1, 2, 4, 5, 6, 7, 9]. Do not call sort
+\newpage
+
+\item Write a method \verb!ArrayList<Integer> onlySquares(ArrayList<Integer> list)! that returns only those elements that are a square of an integer themselves.
+\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
+\item Write a method \verb!ArrayList<Integer> onlyNthPowers(ArrayList<Integer> list, Integer n)! that returns only those elements that are an nth power of an integer themselves.
+\end{enumerate}
+\end{document} 

facilitator/tcss143/09sp/wk06.tex

+\documentclass[11pt]{article}
+\usepackage{amsmath}
+\usepackage{fancyhdr}
+\pagestyle{fancyplain}
+\lhead{TCSS 390A}
+\chead{Worksheet \#6}
+\rhead{May 4, 2009}
+
+\begin{document}
+
+\section{Quantitative}
+\subsection{For the following questions, consider the following possible LinkedList specification in Java}
+\begin{verbatim}
+public class LinkedList {
+    //this is the front of the list. may be null
+    public Node front = null;
+
+    public LinkedList();
+   
+    //returns the length of the linked list. zero if front is null
+    public int length() { /* COMPLETE THIS */ };
+
+    //adds the given node to the front of the list
+    public void push(Object element) { /* COMPLETE THIS */ };
+
+    //returns the front node's element, removing front node from list
+    public Object pop() { /* COMPLETE THIS */ };
+
+    public class Node {
+        public Object element;
+        public Node next;
+
+        public Node(Object element) {
+            this(element, null);
+        }
+
+        public Node(Object element, Node next) {
+            this.element = element;
+            this.next = next;
+        }
+    }
+}
+\end{verbatim}
+\newpage
+
+\begin{enumerate}
+\item Complete the implementation of this particular definition of LinkedList.
+\newpage
+
+What code would be required to change the sequence of the following linked lists as defined above from the \emph{before} states to the \emph{after} states? For the definition of the Node object, look at the LinkedList class above.
+
+\item
+\begin{itemize}
+\item Before: front = [ 1 ] -$>$ [ 2 ] /  
+\item After: front = [ 3 ] -$>$ [ 1 ] -$>$ [ 2 ] /
+\\\\\\\\\\\\\\\\\\\\\\\\*
+\end{itemize}
+\item 
+\begin{itemize}
+\item Before: front = [ 1 ] -$>$ [ 2 ] /  
+\item After: front = [ 1 ] -$>$ [ 2 ] -$>$ [ 3 ] /
+\end{itemize}
+\newpage
+
+\item
+\begin{itemize}
+\item Before: front = [ 1 ] -$>$ [ 2 ] -$>$ [ 3 ] -$>$ [ 4 ] /
+\item After: front = [ 2 ] -$>$ [ 4 ] -$>$ [ 5 ] -$>$ [ 3 ] -$>$ [ 1 ] /
+\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
+\end{itemize}
+\item 
+\begin{itemize}
+\item Before: front = [ 1 ] -$>$ [ 2 ] -$>$ ... -$>$ [ n ] /  
+\item After: front = [ 1 ] -$>$ [ 2 ] -$>$ ... -$>$ [ n ] -$>$ [ n + 1 ] / 
+\end{itemize}
+\newpage
+
+\item
+\begin{itemize}
+\item Before: front = [ Obj1 ] -$>$ [ Obj2 ] -$>$ ... -$>$ [ Objn ] /  
+\item After: front = [ Obj1 ] -$>$ [ Obj2 ] -$>$ ... -$>$ [ Objn+1 ] -$>$ [ Objn ] /  
+\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
+\end{itemize}
+\item
+\begin{itemize}
+\item Before: front = [ Obj1 ] -$>$ [ Obj2 ] -$>$ ... -$>$ [ Objn ] /  
+\item After: front = [ Objn ] -$>$ [ Objn-1 ] -$>$ ... -$>$ [ Obj1 ] /  
+\end{itemize}
+\newpage
+
+\item Add the method \verb!int count(int n)! that returns the number of times the integer \verb!n! occurs in a \verb!LinkedList!
+\\\\\\\\\\\\\\\\\\\\\\\\*
+\item Add the method \verb!void add(int index, Node node)! which adds a \verb!Node! at \verb!index!. Be sure to throw an \verb!IndexOutOfBounds! exception if the index is invalid.
+\newpage
+
+\item Write a function 
+\begin{verbatim}
+boolean havingPizzaParty(
+  LinkedList workshopScores, int classTotal, int classSize)
+\end{verbatim}
+that determines if the workshop students get pizza. Workshop students get pizza if their average is 10\% greater than the class average.
+\newpage
+
+\item Refactor the original LinkedList so that the front Node is always equal to \verb!Node(null)!. In other words, we never want the front node to be \verb!null! and we never want it to be populated with a node whose element is non-null.
+\end{enumerate}
+\end{document} 

facilitator/tcss143/09sp/wk07.tex

+\documentclass[11pt]{article}
+\usepackage{amsmath}
+\usepackage{fancyhdr}
+\usepackage{enumitem}
+\pagestyle{fancyplain}
+\lhead{TCSS 390A}
+\chead{Worksheet \#7}
+\rhead{May 11, 2009}
+
+\begin{document}
+
+\section{Recursion}
+
+\subsection{Arithmetic}
+\subsubsection*{Divisors}
+A divisor $d$ of $n$ is a positive integer that evenly divides $n$. In other words, there exists some $f$ such that $d\cdot f = n$. The greatest common divisor of a pair of positive integers $m$ and $n$ is the largest positive integer $d$ that is a divisor of both $m$ and $n$. All divisors of $n$ other than $n$ itself are called proper divisors.
+
+Euclid's algorithm for finding the greatest common factor is recursive in nature. Consider the recursive java implementation of Euclid's algorithm below.
+
+\begin{verbatim}
+public int gcd(int m, int n) {
+    if ((m < 0) || (n < 0))
+        throw new IllegalArgumentException(
+            "Only non-negative integers are considered.");
+    if (m == 0)
+        return n;
+    if (n == 0)
+        return m;
+    return gcd(n, m % n);
+}
+\end{verbatim}
+\begin{enumerate}
+\item Evaluate the following:
+\begin{enumerate}
+\item \verb!gcd(6, 8)!
+\\*
+\item \verb!gcd(16, 12)!
+\\*
+\item \verb!gcd(210, 36)!
+\\*
+\item \verb!gcd(40, -3)!
+\\*
+\item \verb!gcd(80, 49)!
+\\*
+\end{enumerate}
+\item What happens when the first argument is smaller than the second?
+\end{enumerate}
+\newpage
+The recursive method with wrapper below produces the sum of the proper divisors of a positive integer $n$. 
+
+\begin{verbatim}
+public int sumProperDivisors(int n) {
+    if (n < 1)
+        throw new IllegalArgumentException(
+            "Only positive integers are considered.");
+    return sumThem(n, 0, 1);
+}
+
+private int sumThem(int n, int sum, int i) {
+    if (i > n / 2)
+        return sum;
+    else {
+        if ((n % i) == 0)
+            sum += i;
+        return sumThem(n, sum, i + 1);
+    }
+}
+\end{verbatim}
+
+\begin{enumerate}[resume]
+\item Evaluate the following:
+\begin{enumerate}
+\item \verb!sumProperDivisors(6)!
+\\*
+\item \verb!sumProperDivisors(17)!
+\\*
+\item \verb!sumProperDivisors(24)!
+\\*
+\item \verb!sumProperDivisors(27)!
+\\*
+\item \verb!sumProperDivisors(28)!
+\\*
+\end{enumerate}
+\end{enumerate}
+
+Numbers which are the sum of their proper divisors are called perfect. It is unknown whether there are infinitely many even perfect numbers. There is a close connection between perfect numbers and Mersenne primes. The goal of the GIMPS distributed computing project is to discover new Mersenne primes. It is also unknown if there are any odd perfect numbers at all.
+\newpage
+
+\subsection{Two approaches}
+Problems will be approached using two paradigms in this section - an ``accumulative'' paradigm and a ``forgetful'' paradigm. The accumulative paradigm will exhibit a bit more complexity but will support greater efficiency and knowledge discovery. The difference between these approaches is akin to the difference between ``lazy evaluation'' and ``eager evaluation''. Lazy evaluation benefits include performance increases due to avoidance of unnecessary calculations and the ability to construct ``infinite'' data structures. 
+
+\subsubsection*{Factorial}
+Factorials are used in combinatorics and probability. The factorial of an integer $n$ is defined by the product $n! = n\cdot(n - 1)!; 1! = 1$ and is undefined for negative integers. The notion of a factorial can be extended to all real numbers (except for the negative integers) via the Gamma function (for further study, see Wikipedia:Gamma\_function).
+
+The recursive method below produces the factorial $n!$.
+
+\begin{verbatim}
+public int fact(int n) {
+    if (n < 0)
+        throw new IllegalArgumentException(
+            "Factorial not defined for negative integers");
+    if (n == 0)
+        return 1;
+    return n * fact(n - 1);
+}
+\end{verbatim}
+\begin{enumerate}[resume]
+\item Evaluate the following:
+\begin{enumerate}
+\item \verb!fact(4)!
+\\*
+\item \verb!fact(6)!
+\\*
+\item \verb!fact(-3)!
+\\*
+\item \verb!fact(8)!
+\\*
+\end{enumerate}
+\end{enumerate}
+\newpage
+
+The recursive method below can also produce the factorial $n!$.
+
+\begin{verbatim}
+public int fact2(int n, int r, int prod) {
+    if (n < 0)
+        throw new IllegalArgumentException(
+            "Factorial not defined for negative integers");
+    if (n < r)
+        return prod;
+    else
+        return fact2(n, r + 1, r * prod);
+}
+\end{verbatim}
+\begin{enumerate}[resume]
+\item Evaluate the following:
+\begin{enumerate}
+\item \verb!fact2(4, 1, 1)!
+\\\\\\*
+\item \verb!fact2(6, 1, 1)!
+\\\\\\*
+\item \verb!fact2(-3, 1, 1)!
+\\\\\\*
+\item \verb!fact2(8, 1, 1)!
+\\\\\\*
+\end{enumerate}
+\item What meaning does the value \verb!fact2(10, 6, 1)! have?
+\\\\\\\\*
+\item Evaluate \verb!fact(n, r, 0)!
+\end{enumerate}
+\newpage
+
+\subsubsection*{Fibonacci}
+The Fibonacci sequence is a sequence of integers $F_n$ defined by the following recurrence relation:
+
+\begin{equation}
+F_n = F_{n-1} + F_{n-2}; F_0 = 1, F_1 = 1
+\end{equation}
+
+Fibonacci numbers arise naturally in a multitude of situations and are rich in friendly and surprising properties. For example, the greatest common divisor of two Fibonacci numbers is also a Fibonacci number and can be found using $gcd(F_{m}, F_{n}) = F_{gcd(m,n)}$.
+
+The recursive method below produces the $n^{th}$ term in the Fibonacci sequence. 
+
+\begin{verbatim}
+public int fib(int n) {
+    if (n <= 1)
+        return 1;
+    return fib(n - 1) + fib(n - 2);
+}
+\end{verbatim}
+
+\begin{enumerate}[resume]
+\item Evaluate the following:
+\begin{enumerate}
+\item \verb!fib(5)!
+\\\\\\\\*
+\item \verb!fib(9)!
+\\\\\\\\*
+\item \verb!fib(-7)!
+\\\\\\\\*
+\item \verb!fib(13)!
+\end{enumerate}
+\end{enumerate}
+\newpage
+
+The recursive method below also produces the $n^{th}$ term in the Fibonacci sequence. 
+
+\begin{verbatim}
+public int fib2(int n, int r0, int r1) {
+    if (n <= 1)
+        return r1;
+    else
+        return fib2(n - 1, r1, r0 + r1);
+}
+\end{verbatim}
+
+\begin{enumerate}[resume]
+\item Evaluate the following:
+\begin{enumerate}
+\item \verb!fib2(5, 1, 1)!
+\\\\\\\\*
+\item \verb!fib2(9, 1, 1)!
+\\\\\\\\*
+\item \verb!fib2(13, 1, 1)!
+\\\\\\\\*
+\item \verb!fib2(17, 1, 1)!
+\\\\\\\\*
+\end{enumerate}
+\item What meaning does the value \verb!fib2(4, 1, 2)! have?
+\\\\\\\\\\*
+\item Evaluate \verb!fib2(8, -2, 1)!
+\end{enumerate}
+\newpage
+
+\subsection{Various}
+Hyperfactorials extend the notion of factorials. Hyperfactorials are defined by:
+
+\begin{equation}
+H(n) =\prod_{k=1}^n k^k =1^1\cdot2^2\cdot3^3\cdots(n-1)^{n-1}\cdot n^n
+\end{equation}
+
+Even though $H(14) \approx 1.85 \times 10^{99}$, nearly a googol, and $H(15)$ is approximately equal to the Shannon number, this function grows nominally faster than factorial. Java code represents this calculation below:
+
+\begin{verbatim}
+public int hyperfact(int n) {
+    if (n < 1)
+        throw new IllegalArgumentException(
+            "Only positive integers are considered.");
+    if (n == 1)
+        return 1;
+    return Math.pow(n, n) * hyperfact(n - 1, n - 1);
+}
+\end{verbatim}
+
+\begin{enumerate}[resume]
+\item Evaluate \verb!hyperfact(n)! for $n \in \{1, 2, 3, 4, 5\}$
+\newpage
+\item Write a hyperfactorial method that is recursive and is ``accumulative'' in nature.
+\end{enumerate}
+\newpage
+The Collatz function, also known as the Hailstone function can be defined recursively, as below.
+
+\begin{verbatim}
+public int collatz(int n) {
+    if (n < 1)
+        throw new IllegalArgumentException(
+            "Only positive integers are considered.");
+    return coll(1, n);
+}
+
+private int coll(int iterations, int n) {
+    if (n <= 1)
+        return iterations;
+    else {
+        iterations += 1;
+        if ((n % 2) == 0) 
+            return coll(iterations, n / 2);
+        else
+            return coll(iterations, 3 * n + 1);
+    }
+}
+\end{verbatim}
+
+\begin{enumerate}[resume]
+\item Evaluate \verb!collatz(n)! for $n \in \{2, 3, 4, 5, 6, 7, 8, 9\}$
+\\\\\\\\*
+\item Describe what this function does.
+\\*
+\end{enumerate}
+(Note: It is unknown whether the collatz function returns out of its recursion for all values of $n$.)
+\newpage
+
+The Ackermann function, in computability theory, is an example of a computable function that is not primitive recursive. It also grows extremely quickly in $n$, even for small values of $m$. The Ackermann function grows faster than hyperfactorials, but not as fast as the non-computable Busy Beaver function (see Wikipedia:Busy\_beaver).
+
+\begin{verbatim}
+public int ack(int m, int n) {
+    if (m <= 0)
+        return n + 1;
+    else {
+        if (n <= 0)
+            return ack(m - 1, 1);
+        else
+            return ack(m - 1, ack(m, n - 1));
+    }
+}
+\end{verbatim}
+
+\begin{enumerate}[resume]
+\item Evaluate the method \verb!ack! for $(m,n) \in\{(0,3),(2,0),(1,4),(2,3),(3,2),(4,0)\}$
+\end{enumerate}
+\end{document} 
+

facilitator/tcss143/09sp/wk08.tex

+\documentclass[11pt]{article}
+\usepackage{amsmath}
+\usepackage{fancyhdr}
+\usepackage{enumitem}
+\pagestyle{fancyplain}
+\lhead{TCSS 390A}
+\chead{Worksheet \#8}
+\rhead{May 18, 2009}
+
+\begin{document}
+
+\section{Recursion}
+
+\subsection{Various}
+\subsubsection*{Ackermann}
+The Ackermann function, in computability theory, is an example of a computable function that is not primitive recursive. It also grows extremely quickly in $n$, even for small values of $m$. The Ackermann function grows faster than hyperfactorials, but not as fast as the non-computable Busy Beaver function (see Wikipedia:Busy\_beaver).
+
+\begin{verbatim}
+public int ack(int m, int n) {
+    if (m <= 0)
+        return n + 1;
+    else {
+        if (n <= 0)
+            return ack(m - 1, 1);
+        else
+            return ack(m - 1, ack(m, n - 1));
+    }
+}
+\end{verbatim}
+
+\begin{enumerate}
+\item Evaluate the method \verb!ack! for $(m,n) \in\{(0,3),(2,0),(1,4),(2,3),(3,2),(4,0)\}$
+\end{enumerate}
+\newpage
+
+\section{Searching and Sorting}
+
+\subsection{Binary Search}
+\subsubsection*{Recursive}
+
+\begin{enumerate}[resume]
+\item Binary search uses the idea of ``Divide and Conquer'' to create efficiencies. For the recursive method below, assume that \verb!array! represents a sorted array, that \verb!valueSearching! is the value being searched for, and the return value represents the index of the matching value in the array. Please repair the implementation of binary search of integers below.
+\begin{verbatim}
+public int findIndex(int[] array, int valueSearching, 
+        int lowIndex, int highIndex) {
+    int mid = (lowIndex - highIndex) / 2;
+
+
+    if (valueSearching < array[mid])
+    
+    
+        findIndex(array, valueSearching, mid, highIndex);
+
+
+    else
+        
+        
+        findIndex(array, valueSearching, lowIndex, mid);
+
+
+}
+\end{verbatim}
+\item Implement binary search in an iterative manner.
+\newpage
+\subsection{Comparators}
+\subsubsection*{Geometry}
+Consider the set of ordered pairs $\{(x,y): x \in R^+, y \in R\}$ representing the right half of the Cartesian plane. Define a class representing instances of such pairs as follows:
+\begin{verbatim}
+public class PairR {
+    private double x;
+    private double y;
+    
+    public PairH(double x, double y) {
+        if (x < 0)
+            throw new IllegalArgumentException(
+                "x should be positive");
+        this.x = x;
+        this.y = y;
+    }
+
+    public double getX() { return x; }
+    public double getY() { return y; }
+}
+\end{verbatim}
+
+Furthermore, consider a \verb!Comparator<PairR>! on this set:
+\begin{verbatim}
+public class RightHalfComparator
+    implements Comparator<PairR> {
+    
+    public int compare(PairR p1, PairR p2) {
+        double tan1 = p1.getY() / p1.getX();
+        double tan2 = p2.getY() / p2.getX();
+        if (tan1 == tan2) {
+            double r1 = p1.getY() * p1.getY() + p1.getX() * p1.getX();
+            double r2 = p2.getY() * p2.getY() + p2.getX() * p2.getX();
+            return (r1 - r2); 
+        } else
+            return tan1 - tan2;
+            
+    }
+}
+\end{verbatim}
+\item Apply the \verb!RightHalfComparator! on the following pairs of \verb!PairR! instances:
+\begin{enumerate}
+\item \verb!PairR(1, 3)!, \verb!PairR(4, 3)!
+\item \verb!PairR(3, 3)!, \verb!PairR(6, 6)!
+\item \verb!PairR(10, -4)!, \verb!PairR(20, -6)!
+\item \verb!PairR(4, -6)!, \verb!PairR(10, -15)!
+\end{enumerate}
+\item Describe the geometric meaning of this comparator.
+\\\\\\\\\\\\\\\\*
+Consider another comparator below:
+\begin{verbatim}
+public class RightHalfComparator2
+    implements Comparator<PairR> {
+    
+    public int compare(PairR p1, PairR p2) {
+        if (p1.getY() == p2.getY()) {
+            return (p1.getX() - p2.getX()); 
+        } else
+            return p1.getY() - p2.getY();
+            
+\end{verbatim}
+\item Sort the following list of \verb!PairR! objects using each of these comparators:
+
+\verb!PairR(1, 3)!, \verb!PairR(4, 3)!, \verb!PairR(3, 3)!, \verb!PairR(6, 6)!, \verb!PairR(10, -4)!, \verb!PairR(20, -6)!, \verb!PairR(4, -6)!, \verb!PairR(10, -15)!
+\newpage
+\subsubsection*{Insertion Sort}
+Consider the following pseudocode for insertion sort:
+\begin{verbatim}
+insertionSort(array A)
+    for i := 1 to length[A]-1 do
+        value := A[i];
+        j := i-1;
+        while j >= 0 and A[j] > value do
+            A[j + 1] := A[j];
+            j := j-1;
+        A[j+1] := value;
+\end{verbatim}
+\item Implement the code above in Java for \verb!PairR! obeying the following signature: 
+
+\verb!insertionSort(PairR[] array, Comparator<PairR> c)!
+\newpage
+\item What is the Big-Oh running time of insertion sort?
+\\\\\\*
+\item Consider the array of \verb!PairR! objects. Step through each iteration of your insertion sort with each comparator, displaying the interim arrays along the way.
+\verb!PairR(1, 3)!, \verb!PairR(4, 3)!, \verb!PairR(3, 3)!, \verb!PairR(6, 6)!, \verb!PairR(10, -4)!, \verb!PairR(20, -6)!, \verb!PairR(4, -6)!, \verb!PairR(10, -15)!
+\end{enumerate}
+\end{document} 

facilitator/tcss143/09sp/wk09.tex

+\documentclass[11pt]{article}
+\usepackage{amsmath}
+\usepackage{fancyhdr}
+\usepackage{enumitem}
+\pagestyle{fancyplain}
+\lhead{TCSS 390A}
+\chead{Worksheet \#9}
+\rhead{June 1, 2009}
+
+\begin{document}
+
+\section{Quantitative}
+\subsection{Collections and Maps}
+\begin{enumerate}
+\item Write a method with the signature below. It should accept a \verb!String! and return a \verb!Map<Char,Integer>! containing a pairing of distinct \verb!Char! with an associated occurrence of \verb!Char! there were in the \verb!String!.
+\begin{verbatim}
+Map<Char,Integer> occurrenceCount(String text)
+\end{verbatim}
+\newpage
+
+\item Write a method obeying the signature below. It should accept a \verb!List! and return the element that occurs the greatest number of times.
+\begin{verbatim}
+Object maxCount(List list)
+\end{verbatim}
+\newpage
+
+\item Write a method with the signature below. It should accept a \verb!String[]! and return a \verb!Map<Char,Set<String>>!. The keys of the Map are the first character of the Strings in the array, and the values of the \verb!Map! are \verb!Set<String>! objects holding those Strings whose first character are those keys.
+\begin{verbatim}
+Map<Char,Set<String>> makeIndexedDictionary(String[] words)
+\end{verbatim}
+\newpage
+
+\item Write a method with the signature below. It should accept a \verb!Set! and return the powerset of that set. The powerset is the set of all subsets. For example, if the set is $S = \{a, b, c\}$ then the powerset is $\wp(S) = \{\emptyset,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}$.
+\begin{verbatim}
+Set powerSet(Set set)
+\end{verbatim}
+\newpage
+
+\subsection{Sorting and Searching}
+Merge sort is comprised of two components, the binary division of the collection into smaller collections, and the successive sorted merge of those collections.
+\item Write a method with the signature below. It should accept two \verb!ArrayList<Comparable>! objects, assumed to be ascending sorted, and merge the lists, returning a list that is the sorted merge of these. For example, if the lists contain the values [1, 4, 5, 9] and [2, 6, 7], then the returned list would be [1, 2, 4, 5, 6, 7, 9].\begin{verbatim}
+ArrayList<Comparable> merge(
+    ArrayList<Comparable> left, ArrayList<Comparable> right)
+\end{verbatim}
+\newpage
+
+\item Write a method with the signature below. It should accept an \verb!ArrayList<Comparable>! and two \verb!ArrayList<Comparable>! objects that will, by the end, populate them with the elements left and right of the midpoint of the original.
+\begin{verbatim}
+void splitList(ArrayList<Comparable> original, 
+    ArrayList<Comparable> left, ArrayList<Comparable> right)
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+\end{verbatim}
+\item The run-time advantage of Merge sort comes from the use of divide and conquer, which is typically done via recursion. What would the base case be?
+\newpage
+
+\item Combine the two methods above to implement the following pseudocode in Java.
+\begin{verbatim}
+merge_sort(m)
+  if length(m) < 1
+    return m
+  
+  splitList(m, left, right)
+
+  left = merge_sort(left)
+  right = merge_sort(right)
+  
+  return merge(left, right)
+\end{verbatim}
+\newpage
+\item Other questions?
+\end{enumerate}
+\end{document} 

facilitator/tcss143/10wi/code/Betty.class

Binary file added.

facilitator/tcss143/10wi/code/Betty.java

+public class Betty extends Person {
+  public String name() {
+    return "Betty";
+  }
+}

facilitator/tcss143/10wi/code/Eric.class

Binary file added.

facilitator/tcss143/10wi/code/Eric.java

+public class Eric extends Person {
+  @Override
+  public String greet() {
+    return super.greet() + "How are you?";
+  }
+  public String name() {
+    return "Eric";
+  }
+}

facilitator/tcss143/10wi/code/Greeter.class

Binary file added.

facilitator/tcss143/10wi/code/Greeter.java

+public class Greeter implements IGreeting {
+  public String greet() {
+    return "Welcome to UWT!";
+  }
+}

facilitator/tcss143/10wi/code/IGreeting.class

Binary file added.

facilitator/tcss143/10wi/code/IGreeting.java

+public interface IGreeting {
+  String greet();
+}

facilitator/tcss143/10wi/code/Joe.class

Binary file added.

facilitator/tcss143/10wi/code/Joe.java

+public class Joe extends Person {
+  public String name() {
+    return "Joe";
+  }
+}

facilitator/tcss143/10wi/code/Maria.class

Binary file added.

facilitator/tcss143/10wi/code/Maria.java

+public class Maria extends Person {
+  @Override
+  public String greet() {
+    return "Hola. Me llamo es " + name() + ".";
+  }
+  public String name() {
+    return "Maria";
+  }
+}

facilitator/tcss143/10wi/code/Person.class

Binary file added.

facilitator/tcss143/10wi/code/Person.java

+public abstract class Person implements IGreeting {
+  public String greet() {
+    return "Hello, my name is " + name() + ".";
+  }
+  public abstract String name();
+}

facilitator/tcss143/10wi/code/Tester.class

Binary file added.

facilitator/tcss143/10wi/code/Tester.java

+import java.util.*;
+
+public class Tester {
+  public static void main(String args[]) {
+    ArrayList<IGreeting> greeters = new ArrayList<IGreeting>();
+    greeters.add(new Joe());
+    greeters.add(new Betty());
+    greeters.add(new Maria());
+    greeters.add(new Eric());
+    greeters.add(new Greeter());
+    greeters.add(new Betty());
+    greeters.add(new Maria());
+    for (IGreeting greeter : greeters) {
+      System.out.println(greeter.greet());
+    }
+  }
+}

facilitator/tcss143/10wi/wk01.tex

+\documentclass[11pt]{article}
+\usepackage{amsmath}
+\usepackage{fancyhdr}
+\pagestyle{fancyplain}
+\lhead{TCSS 390A}
+\chead{Worksheet \#1}
+\rhead{January 4, 2010}
+
+\begin{document}
+\section{Warm-up}
+\subsection{Arithmetic and Combinatorics}
+\begin{enumerate}
+\item Suppose a ribbon is wrapped once around the equator of the Earth (assuming the Earth is a perfect sphere and you had a ribbon long enough).  If, everywhere simultaneously, the ribbon was lifted straight up one foot off the surface of the Earth, how much extra ribbon would you need to maintain a complete circle of ribbon one foot high everywhere?
+\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
+\item Using a faucet, a three-gallon and a five-gallon container, describe how you can measure exactly four gallons.
+
+\newpage
+\item Suppose $n$ people show up to a party and begin to mingle. At each point, the group of $n$ people can be separated into two groups - those people who have shaken hands with an even number of people, and those people who have shaken hands with an odd number of people. Prove that the amount of people who have shaken hands with an odd number of people is an even number.
+\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
+\item Two-hundred students are positioned in 10 rows, each containing 20 students. From each of the 20 columns thus formed the shortest student is selected, and the tallest of these 20 (short) students is tagged A. These students now return to their initial places. Next the tallest student in each row is selected, and from these 10 (tall) students the shortest is tagged B. Which of the two tagged students is the taller (if they are different people)?
+\newpage
+
+\item Given a 4 x 4 square, provide a configuration of 7 stars such that no matter which two rows and columns are deleted, the remaining squares always contain at least one star.
+\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
+\item Given a 4 x 4 square, show that it is impossible to provide a configuration of only 6 stars such that no matter which two rows and columns are deleted, the remaining squares always contain at least one star.
+\newpage
+
+\item Dazzy fishes for more than a week. He experiences three different levels of success. On a good day he catches 9 fish. On a bad day he catches only 5 fish. On other days he catches 7 fish. In all, Dazzy catches 53 fish. How many bad days does he have?
+\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
+\item In this game, there are 100 coins on one scale, and 200 coins on another scale. Each of two players in turn takes one or more of the coins from one of the scales. The player who makes the number of coins on the two scales equal loses. In an errorless game, who wins? 
+\newpage
+
+\subsection{Basic Code Analysis}
+\item The following code is supposed to write out the numbers 2, 4, 6, 8. What should go in the blanks?
+\begin{verbatim}
+public void even() {
+    int count;
+    count =  ____;  
+    while (count ____ 4) {
+        System.out.println(count);  
+        count = count + ____;  
+    }
+}
+\end{verbatim}
+\item The following code is supposed to calculate the product of consecutive integers up to 10. What should go in the blanks?
+\begin{verbatim}
+public void factorial() {
+    int fact = ____;    // current factorial value 
+    int count =  ____;  // loop control  
+    while (count ____ 10) {
+        fact = fact * ____; 
+        System.out.println(count +``! is '' + fact);  
+        count = count + ____; 
+    }
+}
+\end{verbatim}
+\item The following code accepts two integers, \verb!x! and \verb!y!, as arguments and returns the (inclusive) sum of integers between \verb!x! and \verb!y!. What should go in the blanks?
+\begin{verbatim}
+public void sumit(int x, int y) {
+    int sum = ____; // current sum 
+    int count = ____;  
+    while (count ____ y) {
+        sum = sum + ____; 
+        count = count + ____; 
+    }
+    System.out.println(``sum is:'' + sum);
+}
+\end{verbatim}
+\newpage
+
+\item Calculate the value of \verb!sum! below in terms of $n$.
+\begin{enumerate}
+\item
+\begin{verbatim}
+sum = 0;
+for ( i = 0; i <= n; i++ )
+    for ( j = 0; j <= 50; j++ )
+        sum++;
+
+
+
+
+
+
+\end{verbatim}
+\item
+\begin{verbatim}
+sum = 0;
+for ( i = 0; i <= n; i++ )
+    for ( j = 1; j <= n; j *= 2 )
+        sum++;
+
+
+
+
+
+\end{verbatim}
+\item
+\begin{verbatim}
+sum = 0;
+for ( i = 0; i <= n; i++ )
+    for ( j = n * n; j > 0; j-- )
+        sum++;
+
+
+
+
+
+\end{verbatim}
+\item
+\begin{verbatim}
+sum = 0;
+for ( i = 0; i <= n; i++ )
+    for ( j = 0; j < i; j++ )
+        sum++;
+
+
+
+\end{verbatim}
+\end{enumerate}
+\newpage
+
+\section{Coding}
+\subsection{Loops and arrays}
+\item Write a method named \verb!countOccurrence(int val, int[] list)! that accepts an integer and an Array of integers as its parameters and returns the number of times the integer \verb!val! can be found in \verb!list!, or -1 if it is not present.
+\newpage
+
+\item Write a method named \verb!isPalindrome(char[] word)! that accepts a \verb!char! Array as its parameter and returns whether the Array is a palindrome. A palindrome is a word, phrase, number, or other sequence that can be read the same way in either direction.
+
+\end{enumerate}
+\end{document} 

facilitator/tcss143/10wi/wk02.tex

+\documentclass[11pt]{article}
+\usepackage{amsmath}
+\usepackage{fancyhdr}
+\pagestyle{fancyplain}
+\lhead{TCSS 390A}
+\chead{Worksheet \#2}
+\rhead{January 11, 2010}
+
+\begin{document}
+\begin{enumerate}
+\section{Warm-up}
+\subsection{Combinatorics}
+\item A traveler having no money, but owning a gold chain having seven links, is accepted at an inn on the condition that he pay one link per day for his stay. If the traveler is to pay daily, but may take change in the form of links previously paid, and if he remains seven days, what is the least number of links that must be cut out of the chain?
+\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
+\item For the Fibonacci numbers, calculate the following infinite sum
+\begin{equation}
+S = \sum_{i=0}^{\infty}\dfrac{3^iF_i}{5^i}
+\end{equation}
+where $F_0 = 1, F_1 = 1, F_{i+1} = F_{i} + F_{i-1}$
+\newpage
+\section{Java}
+\subsection{Java Review}
+\item Answer the following questions below:
+\begin{enumerate}
+\item In Java, what restrictions on class filenames are there?
+\\\\
+\item What is encapsulation?
+\\\\\\
+\item What are the differences between arrays and array lists?
+\\\\\\
+\end{enumerate}
+\item Answer the following questions about methods below:
+\begin{enumerate}
+\item What is an instance method? A class method? What is the difference between them?
+\\\\\\\\
+\item Can a method have more than one return value? How about no return value?
+\\\\\\\\
+\item Can two methods within a class have the same name?
+\\\\\\\\
+\item Are there any restrictions for method names?
+\end{enumerate}
+\newpage
+\item Answer the following questions about constructors below:
+\begin{enumerate}
+\item Can a class have more than one constructor? 
+\\\\\\\\
+\item Are there any restrictions for constructors? 
+\\\\\\\\
+\item If one does not declare a constructor, what happens? 
+\\\\\\\\
+\end{enumerate}
+\section{Coding}
+\subsection{More Review - Dice}
+\item Write a class called \verb!Die! which has a public instance method \verb!roll! returning a random integer between 1 and 6.
+\newpage
+\item Modify your \verb!Die! class to take a positive integer \verb!n! on construction so that the instance method \verb!roll! will return a random integer between 1 and \verb!n!.
+\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
+\item Write a class called \verb!PairOfDice! which takes two positive integers in its constructor, and instantiates two private instance level \verb!Die!. Include a public instance method named \verb!roll! which returns the sum of the values returned by calling \verb!roll! on each \verb!Die! private instance.
+\newpage
+
+\item Write a class called \verb!Game! which takes a positive integer \verb!k! and a \verb!PairOfDice! in its contructor. The \verb!Game! class should have a public instance method \verb!play! which rolls the pair of dice \verb!k! times. It should somehow store the sum of all rolls in the last call to play for that instance of \verb!Game! protecting it from outside modification. It should somehow store the max value for a roll across all instances of \verb!Game! protecting it from outside modification.
+\newpage
+
+\item Add two methods to \verb!Game! which return the \verb!lastTotal! and \verb!maxRollEver! as integers.
+\\\\\\\\\\\\\\\\\\\\\\\\*
+\item Write a program with a \verb!main! method that plays 10 games, five games with two six-sided dice, five games with one four-sided die and one eight-sided die, printing to standard out the last total for each game and the max roll ever for the set of 10 games.
+\end{enumerate}
+\end{document} 

facilitator/tcss143/10wi/wk03.tex

+\documentclass[11pt]{article}
+\usepackage{amsmath}
+\usepackage{fancyhdr}
+\pagestyle{fancyplain}
+\lhead{TCSS 390A}
+\chead{Worksheet \#3}
+\rhead{January 25, 2010}
+
+\begin{document}
+\begin{enumerate}
+\section{Inheritance and Polymorphism}
+\subsection{The Basics}
+\item If a class is extending another, how does the extending class call the parent constructor? 
+\\\\\\\\\\\\\\\\\\*
+\item How does a parent class ``hide'' a constructor from an extending class?
+\\\\\\\\\\\\\\\\\\*
+\item What is inheritance? How is it used? Why is it useful?
+\\\\\\\\\\\\\\\\\\*
+\item What is polymorphism? How is it used? Why is it useful?
+\newpage
+\subsection{Inheritance}
+
+\subsection{Coding}
+\item For the following classes, use inheritance to reduce code duplication and increase code flexibility. 
+\begin{verbatim}
+public class EconomyCar {
+    private int speed;
+    private int fuelCapacity;
+    private int fuelEfficiency;
+    private String name;
+    
+    public EconomyCar() {
+        speed = 90;
+        fuelCapacity = 12;
+        fuelEfficiency = 50;
+        name = ``Economy Car'';
+    }
+
+    public int maxTravelDistance() {
+        return fuelCapacity * fuelEfficiency;
+    }
+
+    public int travelTime(int distance) {
+        return distance / speed;
+    }
+
+    public String toString() {
+        return name;
+    }
+}
+
+public class PerformanceCar {
+    private int speed;
+    private int fuelCapacity;
+    private int fuelEfficiency;
+    private String name;
+    
+    public PerformanceCar() {
+        speed = 180;
+        fuelCapacity = 16;
+        fuelEfficiency = 20;
+        name = ``Performance Car'';
+    }
+
+    public int maxTravelDistance() {
+        return fuelCapacity * fuelEfficiency;
+    }
+
+    public int travelTime(int distance) {
+        return distance / speed;
+    }
+
+    public String toString() {
+        return name;
+    }
+}
+
+public class Bicycle {
+    private int speed;
+    private boolean multispeed;
+    private String name;
+    
+    public Bicycle(boolean multispeed) {
+        speed = 40;
+        this.multispeed = multispeed;
+        name = ``Bicycle'';
+    }
+
+    public boolean isMultispeed() {
+        return multiSpeeed;
+    }
+
+    public int travelTime(int distance) {
+        return distance / speed;
+    }
+
+    public String toString() {
+        return name;
+    }
+}
+
+public class Skateboard {
+    private int speed;
+    private boolean isLongboard;
+    private String name;
+    
+    public Skateboard(boolean isLongboard) {
+        speed = 18;
+        this.isLongboard = isLongboard;
+        name = ``Skateboard'';
+    }
+
+    public boolean isLongboard() {
+        return isLongboard;
+    }
+
+    public int travelTime(int distance) {
+        return distance / speed;
+    }
+
+    public String toString() {
+        return name;
+    }
+}
+\end{verbatim}
+\newpage
+.
+\newpage
+.
+\newpage
+\item Go back and modify the method \verb!travelTime! to return a \verb!double!.
+\\\\*
+\item Create an instance method of \verb!Vehicle! called \verb!travelTime! that returns the travel time if the vehicle were to travel a certain distance, but only at a percentage of full speed.
+\\\\\\\\\\\\\\\\\\\\\\*
+\item Create a class method of \verb!Vehicle! method \verb!fastest(Vehicle[] vehicles)! that displays the name of the fastest Vehicle in the Array.
+\\\\\\\\\\\\\\\\\\\\\\*
+\item Create a class method of \verb!Vehicle! method \verb!average(Vehicle[] vehicles)! that displays the average value of \verb!travelTime! for the array of \verb!Vehicle! objects given an input of 360 for \verb!distance!.
+\newpage
+
+\subsection{Interfaces}
+\item Revisit your implementation of \verb!Vehicle!. If not already done so, include a second level of inheritance between \verb!Vehicle! and the four extending classes. This second level of inheritance will consist of \verb!MotorizedVehicle! and \verb!NonMotorizedVehicle!.
+\newpage
+
+\item Write an interface called \verb!IFuelable! and modify your existing code so that the two implementations of motorized vehicles will be forced to implement a \verb!refuel()! method.
+\\\\\\\\\\\\\\\\\\\\\\*
+\item In \verb!MotorizedVehicle!, include an encapsulated integer instance variable \verb!fuelLevel! that initially takes on the value of \verb!fuelCapacity!.
+\\\\\\\\\\\\\\\\\\\\\\*
+\item Write a method that accepts a \verb!MotorizedVehicle! array and calls the \verb!refuel()! method on the vehicles setting the \verb!fuelLevel! variable to that vehicle's initial value (of course assume \verb!fuelCapacity! and \verb!fuelLevel! are the same units - say liters).
+\newpage
+
+\item Write a method called \verb!travel(double time)! in \verb!Vehicle! that returns a double representing how far the vehicle traveled, if it travels for the given \verb!time! at the vehicle \verb!speed!. Assume the \verb!speed! is given in kilometers per hour and time is given in hours.
+\\\\\\\\\\\\\\\\\\\\\\*
+\item Implement a method for \verb!MotorizedVehicle! called \verb!travel(double time)! that takes into account fuel in the following ways:
+\begin{enumerate}
+\item Assume \verb!fuelEfficiency! is in kilometers per liter. Assume \verb!fuelLevel! is in liters. Lower the fuel level of the vehicle appropriately when the \verb!travel! method is called.
+\item Realistically model behavior of motorized vehicles when their fuel level becomes zero.
+\end{enumerate}
+
+\end{enumerate}
+\end{document} 

facilitator/tcss143/10wi/wk04.tex

+\documentclass[10pt]{article}
+\usepackage{amsmath}
+\usepackage{fancyhdr}
+\pagestyle{fancyplain}
+\lhead{TCSS 390A}
+\chead{Worksheet \#4}
+\rhead{Monday, February 1}
+
+\begin{document}
+\begin{enumerate}
+\section{Definitions and Concepts}
+\subsection{Constructors, Abstract Classes, Interfaces, Methods}
+\item Answer the questions about abstract classes below:
+\begin{enumerate}
+\item How is an abstract class declared?
+\\\\\\\\\\\\\\*
+\item How are they similar to concrete classes? 
+\\\\\\\\\\\\\\*
+\item How are they different from concrete classes?
+\\\\\\\\\\\\\\*
+\item In order to create a concrete class that extends an abstract class, what are the requirements?
+\\\\\\\\\\\\\\*
+\item Describe in simple terms what an abstract class is. Name some purposes of abstract classes.
+\end{enumerate}
+\newpage
+
+\item Answer the questions about interfaces below:
+\begin{enumerate}
+\item How is an interface declared?
+\\\\\\\\\\\\\\*
+\item How are they similar to/different from abstract classes?
+\\\\\\\\\\\\\\*
+\item In order to implement an interface in a concrete class, what are the requirements?
+\\\\\\\\\\\\\\*
+\item Are there any restrictions regarding the number of interfaces able to be implemented? Any other restrictions?
+\\\\\\\\\\\\\\*
+\item Describe in simple terms what an interface is. Name some purposes of interfaces. 
+\end{enumerate}
+\newpage
+
+\item Answer the questions about methods below:
+\begin{enumerate}
+\item What is method overloading? How is method overloading useful?
+\\\\\\\\\\*
+\item What is method overriding? How is method overriding useful?
+\\\\\\\\\\*
+\end{enumerate}
+\item Answer the questions about generic classes below:
+\begin{enumerate}
+\item What is a generic class? How are generic classes useful? 
+\\\\\\\\\\*
+\item Give some examples of generic classes that you have used.
+\\\\\\\\\\*
+\end{enumerate}
+\item The interface \verb!Comparable! guarantees an ordering for the objects of a class. Answer the questions about this interface below:
+\begin{enumerate}
+\item What method must be implemented by a class that adheres to the \verb!Comparable! interface?
+\\\\\\\\\\*
+\item What is the return type of this method? 
+\\\\\\\\\\*
+\item What common types in Java implement the \verb!Comparable! interface?  
+\end{enumerate}
+\newpage
+
+\section{Quantitative}