Title: cps261F15 Learning Units
Course: CPS 261: Advanced Java Concepts ~ DL & MM MASTER

cps261F15 Learning Units
chasselb
 |  | Remove Objectives from Learning Units

Resources

JH1, JH2, ... JH7 Homework definition files
- This link provides you links to all of the Homework assignment files. Note that you can also get to these files through blackboard links.
Java 8 API
- This link is to the Java Application Interface (API) documentation. Understanding how to use this will become increasingly important as you learn Java. You will see this link accessed in the videos.
Topic Web Site
- This provides links to the same material found in the "Learning Units", however, in this page the links are ordered by logical topics. In addition to the links, this page provides a brief list of objectives covered in each topic.
- You can control whether the list of objectives shows up or not by clicking on a link near the top of the page.
Text Book Examples
Startup

Clem Hasselbach Introduction Page
Course Introduction
Syllabus (9 min)
- cps261 overview: textbook, relationship to other courses
- topics covered
Class Policy
- General goals of the class
- blackboard class structure: Assignments, Class Participation, Lectures, Getting Help, etc.
- Discussion of Grade issues: tests, Lateness Policy, grade composition
- Note a link named "JH... Homework ..." was added that isn't discussed in the video. This link was added after the video was made because it was discovered to be useful to have one page with all of the homework files in one place.
How to get a good Grade
- Grade calculation and MM-Bribe calculations(Incentives for showing up to Mixed Mode class sessions)
Video Features
- This link provides a slide to describe the Video Player characteristics
Discussion Board/Class Participation(15m)
- Discussion boards for questions/answers
- Discussion board for Sharings
- "Questions for Teacher" discussion board
Asignments
- Getting Started JH0 Quiz and first post on a discussion board
- How the JH1, JH2, ... JH7 assignments work.
You now know enough to do JH0
1 cps161 review: Interfaces, Polymorphism, Exceptions

Interfaces and Polymorphism (15 min)
- This is meant to be a quick review of the cps161 concepts of interfaces, abstract classes, and polymorphism.
- An example is worked with the Interface called "Life"
- Review of cps161 Zoo, Animal, Cow, Horse, Snake JH exercise.
The "Tools" folder at the bottom contains refresher information from cps161 on using Eclipse, Java and JING

The remainder of this section on Interfaces, Polymorphism, and Exceptions
are repeat notes/videos from cps161

The following Chess video is a nice example of polymorphism. However, if you already understand polymorphism,
this video doesnt really cover anything new and it is a bit long.
Chess Polymorphism (45 min)
- The following Chess video is a nice example of polymorphism. However, if you already understand polymorphism, this video doesnt really cover anything new and it is a bit long.
- Example Dumb Chess game: A more realistic example of polymorphsim. In this example, a generic piece class and a generic board class is constructed. Then the generic classes get extended with more specific classes like Rook, Queen, Bishop, etc. There are no new concepts here, but the example provides a better picture of how class inheritance and polymorphism can provide a more intuitive solution.
Exceptions Basics (49.5 min)
- Programming without Exceptions (in languages that don't have exceptions like C)
- Demonstrating the occurence of an ArithmeticException (Divide by 0), and catching it
- Demonstrating getting an exception from bad user inputs to the Scanner nextInt method. Also showing how to use the exception to recover from the problem by letting the user enter the number in again.
- Exceptions can be caught locally or globally.
- Comparing exception handling strategies: "readCarefully", or "readAtYourRisk" and catch the errors globally.
Exception Heirarchy and Strategy (47.5 min)
- Class Heirarchy: Throwable, Exception, RuntimeException, etc.
- Unchecked Exceptions (those derived from RuntimeException), versus Checked Exception (not derived from RuntimeException).
- Example to demonstrate 3 Exception handling philosophies (there are other approaches as well)
  - "Evel Knievel" programming style (ignore Exceptions)
  - Global Handling of Exceptions
  - Local Handling of Exceptions to collect more information, but pass the error on to more global routines
  - Local Handling of Exceptions to try to recover from the error locally in order to continue excecuting
- Methods available in the Throwable class (and availabe to all Exceptions classes)
  - getMessage, toString - to print out the error
  - printStackTrace(), printStackTrace(System.out) - to dump the program locations to the standard error stream or the standard system out stream
Checked Exceptions (37 min)
- Using the Scanner class to read a file using FileInputStream ( it's similar to reading from the keyboard).
- Using the PrintStream class to produce output using FileOutputStream( it's similar to writing to System.out).
- Checked exceptions occur with most file input/output. Checked exceptions need to be caught or else a compiler occurs.
- Instead of catching an exception, you can "pass the buck" and pass the exception back to the caller with a statement like: throws FileNotFoundException
- The "finally" clause can be used to make sure that something happens before exitting a "try" block.
- Writing code that throws an Exception to prevent user's from improperly using your program. This is demonstrated in the Game-of-Life program. Note that the type of exception you choose can be checked or not-checked. You can even create and throw your own unique Exception class in order to store extra information.
Java Exceptions Optional Learning Unit
- If Exceptions still seem like a blur to you, consider going through this Optional Learning Unit that gives you another way to understand the concepts covered in the above videos on exceptions.
2 ArrayList/Generics (beginning Data Structures), Input/Output

Beginning ArrayList Concepts (16.5 min)
- This is an introduction to the Arraylist data structure. Note that the ArrayList implements the List interface and there are other implementations of the List interface such as the LinkedList class.
- In this set of notes we are only going to use a small subset of the ArrayList methods: size, get, add.
- Most newer programs will use Generics when using ArrayList. Before generics was added to Java, the ArrayList class was defined to use the Object class.
- In the simple programs demo'ed we illustrate ArrayList with generics and without generics. We also show an ArrayList of Strings as well as an ArrayList of a class we create (Person class).
ArrayList Intro & MyArrayList(40m)
- ArrayLists give us a more flexible data structure than a normal array. Arrays have the downside that their size is fixed.
- In this lecture, you will be introduced to a few more ArrayList features: ArrayList constructor with a size parameter, add routine with an index, set method, indexOf, remove, toString.
- A sample program is provided to illustrate these new features.
- In order to provide understanding of how ArrayList functions, we have provided a MyArrayList class which provides many of the features that we have been discussing. This is done to give you insite into how ArrayList works. This version does not use Java generics.
Generics(30m)
- Generics was added to Java in order to allow Java classes to be more flexible. Generics is similar to C++ templates.
- The basic idea is to have 1 ormore data types be parameters for a given class. For example, a sort routine could sort an array of any kind of class because the type of the class sorted would be a parameter. Most of the data structure classes in Java make use of generics. See the textbook examples: Sample.java, Pair.java, UnorderedPair.java, TwoTypePair.java, and Pair2.java.
- AnimalCollection.java - This is a rework of the cps161 assignment where we had Animal, Cow, Horse, Snake and Zoo classes. Note that by using generics we can control the nature of the AnimalCollection ... dairy, snakePit, zoo
- The MyArrayList.java class from the previous lecture which was based on a list of Objects is updated to use generics.
PrintStream Scanner Examples - basics
- System.out is a PrintStream , System.in is an InputStream ... Now we will look at output to Files.
- We should be using the Scanner class methods hasNextLine and hasNext when we call nextLine, and next.
- Comparing reading a file with reading from the keyboard
PrintStream Scanner Constructors
- Over all approach to opening a Scanner and PrintStream connected to files. Catching the necessary exceptions and a finally clause to close the Scanner and PrintStream. We start out using FileInputStream and FileOutputStream.
- Rework the previous example using the File class.
- PrintStream has a constructor that takes a String, but the Scanner class constructor that takes a String does not do what you might expect.
More complicated Scanner data
- Reading integers with nextInt and the possible exceptions. Guarding against these errors by catching the exception or by using hasNextInt.
- Reading data with mixed data types(double, int, String) : nextDouble, nextInt, next.
- Guarding against possible exceptions and other techniques for avoiding errors.
Buffering Performance (10.5 min)
- Buffering classes: BufferedInputStream and BufferedOutputStream
- Reason why buffering is good and some actual timings using the Timer.java class.
You now know enough to do JH1
3 Input/Output continued

ObjectOutputStream / ObjectInputStream (26 min)
- Binary Input/Output usning the ObjectInputStream and ObjectOutputStream classes.
- Classes read and written need to be Serializable.
- Note the methods in ObjectOutputStream of writeByte, writeInt, writeLong, writeDouble writeUTF(for Strings), writeObject and matching methods for reading these entities back in with the ObjectInputStream class.
- Example of Dumping and Restoring a Zoo (from our cps161 homework).
Pausable Tic Tac Toe using Serializable
- Reworking the published answer to the cps161 Tic-Tac-Toe game to make it "Pausable" using ObjectOutputStream and ObjectInputStream. With this change, we can "Pause" our game and come back and resume it later byte writing out the whole TicTacToe class to a file and reading it back in.
File Class
- This video covers the File class and many of its useful methods: delete, renameTo, list, mkdir, lastModified, isDirectory, size, etc. This class provides us a way to work with your File System.
Recursion using File class
- In this video we create a program which will recursively walk through a directory and count the number of files and the total number of bytes associated with the directory.
- Not only is this a good way to see the File class in action, but this is also a good example of using Recursive programming in Java. In certain circumstances recursive programming can provide a powerful way to solve a problem.
Alternative to Recursion: Stack Approach
- If you didn't know how to write a recursive algorithm, you could use a Stack to solve the same problem. In this example, we solve the previous problem again using a Stack. Sometimes it is easier to see the solution when using the "Stack Algorithm" approach and sometimes it is easier to see the solution when using the "Recursive Algorithm" approach.
RandomAccessFile class (26 min)
- Most Java Input/Output files tend to do either input or output in a sequential manner. The RandomAccessFile class allows you to open a file for both input and output at the same time. The RandomAccessFile class also provides binary options as well as the ability to move randomly around in the file using a "seek" method.
- Many of the methods of RandomAccessFile remind us of ObjectInputStream and ObjectOutputStream. However, the additional methods seek, and getFilePointer are useful to move around within the file in a non-sequential fashion.
- An example (RandomPeople.java) is worked to demonstrate the usefulness of RandomAccessFile. This example is patterned on some work that once read and wrote PDF files.
Character Stream Classes (16 min)
- Internationalization issues and the character based classes
- Important classes: Reader, Writer, FileReader, FileWriter, PrintWriter, etc.
- Examples of simple copy routines using Reader/Writer based classes
- Note that without the Scanner class there is a need for a conversion from InputStream to the Reader class. See the MyInput class.
System Properties
- Obtaining system properties: java.version, os.name, user.name, user.home, line.separator, file.separator, user.dir
You now know enough to do all of JH2
4 Drawing Basics

Drawing Basics(45m)
- Overriding the paint method and using the Graphics class to do basic drawing.
- Fundmentals of coordinate system and using the Color class change the color of the drawing object.
- Demonstrating many of the Graphics methods: drawRect, drawOval, fillRect, fillOval, drawLine, drawString, drawRoundRect, draw3DRect, drawArc, drawPolygon, etc.
- Using the Font class and discovering the Fonts supported
Drawing Sizing(49m)
- Taking into account drawing borders with Insets
- Resizing by finding out the size of the screen with getSize
- Placing an object at the screen: center, lower right, upper right.
- Scaling a Polygon (Forida.java example)
- Working with Font sizes: getFontMetrics, and its associated methods to perfectly place text
- GraphBeginnings.java - A resizeable Graph of data
Drawing Images(52m)
- Loading an image and obtaining it's dimensions
- The many variations of the drawImage Graphics method
- Drawing checkers on a checker board with the image centered in their respective squares
- Loading chess piece images and drawing a chess board
You now know enough to the first 2 problems in JH3
5 User Inputs and Animation

User Input Mechanisms(48m)
- Basic Mouse Motion is demonstrated using the MouseMotion inteface. Several examples are created: Spots.java, SpotsSave.java.
- To detect Mouse Motion and dragging, we add one more interface called MouseMotionListener to create the example SpotsArt.java
- A program can access key strokes by implementing the KeyListener interface.
- Using inner classes to implement interfaces such as the MouseListener interface.
- Using adapter classes: An inner class extending the MouseAdapter class to accomplish the same result as the previous example.
- Converting the previous example to an anonymous class.
Animation and Simple Threads(38m)
- Extending the Thread class to create a thread.
- Creating a thread by having a class implement the Runnable interface.
- Using a thread to update the time on a screen: Timer.java
- Using a thread to create a simple animation that successively loads images.
- Eliminating screen flicker by creating a memory screen image that gets updated and then copied to the real screen.
- Simple one person Pong game that uses the concepts in this set of notes.
Shape Drawing(50m)
- MVC: Model View Controller approach
- Starter code to a simple drawing program(used in one of the JH assignments):
- abstract Shape, Rectangle, Scribble classes
- Drawing.java - has the concept of a drawing program
- DrawingProgram.java - actually contains the JFrame and associated paint routine and Mouse interface routines. Actual work is delegated to the Drawing.java code.
GUI Component High Level(27m)
- AWT (Abstract Windowing Toolkit) versus Swing packages of Components
- JFrame fundamentals versus JApplet fundamentals.
- Note that Applets used to be more prevalent than now. Applets have had some security issues, so getting applet code to work in your browser requires being more lax on your browser security settings.
- Creating a program that can be an applet and a window application (BasicBoth.java).
You now know enough to do all of JH3
6 Gui Components

Gui Component Basics(44m)
- JTextArea, JTextField and the useful associated methods: setText, append, getText, getSelectedText, ...
- Other components: JLabel and JButton
- How to connect up an ActionListener interface to find out when a JButton is clicked or when someone hits the Enter key in JTextField
- Using the methods getSource() and getActionCommand() to determine which Button was clicked
- Using inner classes and anonymous classes
GUI LayoutManagers(24m)
- FlowLayout demo
- GridLayout demo
- BorderLayout demo
- Using JPanel to construct useful GUI layouts. JPanel works especially well with BorderLayout
GUI Menus(14m)
- JMenuItem works similar to JButton and can take an ActionListener interface
- JMenu and JMenuBar containers for JMenuItem
- Nested Menus
GUI More Book Examples(27m)
- WindowListener example
- ImageIcon and adding images to JLabel or to JButton
- Providing Scrolling capabilities. The primary component thatneeds this is JTextArea, but JScrollPane can be used for other GUI components as well.
- Using the setVisible method to make GUI objects disappear and then reappear.
- JColorChooser class
Gui Additional Examples(33m)
- Check.java example using JCheckBox, JRadioButton, and ButtonGroup
- Selection.java example using JList and JScrollPane
- GridBagLayout manager example
- CardLayout manager example
- Null Layout Manager example
- Creating your own button class similar to JButton
- Creating your own Layout manager (CustomLayout.java)
You now know enough to do all of JH4
Midterm Procedures and Hints
- Procedures for taking the midterm
- Hints about what you need to know for the midterm
Please take the Midterm ... See the schedule in Blackboard
Advanced Web Features - Very Useful, but Optional video
- The Learning Units web site has search capabilities that are demonstrated in this video. The Learning Units is organized by the order the videos should be watched. There is a companion web site that is organized by Topics which has more search capabilities.
7 Threads & Networking

How to be a good programmer
- Quick video to encourage you to:
  - Programming Philosopy: Practice, Pay attention to Code readability style issues
  - Tracking down why your program doesn't work: Print statements, Debugger
  - Get to the bottom of your real problem and avoid kludges to cover up symptoms
  - Robust style issues
  - Using the Compiler to assist you
Thread Fundamentals(22m)
- Examples of where Threads are used.
- Creating a thread by extending the Thread class
- Creating a thread by creating a class which implements the Runnable interface
- Managing threads using the interrupt, isAlive methods. Note that the actual thread will experience an InterruptedException.
Thread Synchronization(26m)
- Synchronization issues when multiple threads access common data. Bank.java illustrates the problem that can occur.
- Using the keyword " synchronized " to fix the problem. You can also use "synchronized" to mark a block of code that needs to be protected. Java enforces the rule: only one thread can be in any synchronized section of an object instance at any one time .
- Deadlocks - Deadlock.java is an example (simple but contrived) of a deadlock that can occur when synchronized regions are not properly handled.
Thread Wait Notify capabilities(40.5m)
- BusyLoop.java example: Busy loop approaches to working with synchronized objects is wasteful on resources.
- WaitNotify.java example: Using wait, notify, and notifyall (all methods found in the Object class), you can produce a more efficient approach.
- WaitNofity2.java - A circular queue of buckets using wait, notify, and notifyall to produce an even better approach. Parallel_IO.java is a more practical example of the same technique. This is something I found very useful to know about in industry.
- Optional Extra (and fun) examples: Dining Philosopher problem, Color Boxes example, and the Pizza store problem.
Networking: TCP/IP and Basic Sockets
- Networking layered architecture:
  - Protocols like Http, Ftp, SMTP, IMAP, POP, Telnet sit on top of TCP/IP
  - TCP/IP (Transmission Control Protocol and Internet Protocol) layer
  - Hardware Layer: Ethernet, Wireless, Twisted Pair, etc.
- Socket Programming gives us an API to reliably send and receive packets of data from the TCP/IP layer. All of the protocols(Http, Ftp, etc.) make use of the this layer.
- EchoServerSingleThreaded.java example: Single Threaded Echo Server. Server waits on an "accept" call until a connection request comes in. A Socket data structure is returned from the "accept" call and it can be turned into an InputStream and OutputStream which then allows us to use our Scanner and PrintStream classes.
- EchoClient.java example: This class does a "connect" to some Server and also receives a Socket data structure. Again the client can convert the Socket into an InputStream or an OutputStream and use the Scanner and PrintStream classes to simplify communication.
Networking: Better Server Model
- In the previous video/notes we went over the basics of Sockets. However, the Server code example had many deficiencies. In this video/notes we create a better Server Architecture with the following advantages:
  - We can handle more than one conversation simultaneously
  - We can terminate threads more cleanly with the 2 classes: MotherServer.java and EchoServer.java
  - We can reuse the EchoServer logic by extending EchoServer to create other protocols: Rock-Paper-Scissors, Http Server, File Server
Networking: Sample Protocol Handlers
- By Extending EchoServer.java, you can then create new protocols: RPS_Server.java for Rock Paper Scissors.
- HttpServer.java - creating a minimal Http Web Server by extending EchoServer.java.
- You should now be able to put together your File Server for JH5.
JH5 Help(12m)
- In this video you will see some help on the networked File processor (JH5)
You now know enough to do the File Server question in JH5
8: Networking continued & Networked Games

Networking Extra Odds and Ends(33m)
- This video/notes has some miscellaneous extra concepts for completeness.
  - Sending and receiving objects across TCP/IP using ObjectInputStream and ObjectOutputStream. To do this we have EchoObjectClient.java extending the EchoClient, and EchoObjectServer extending EchoServer. The ability to send and receive objects across a socket is important for our Networking Game Project.
  - GetUrl.java examample: using Sockets to create a primitive browser functionality.
  - URLReader.java example: demonstrates using the URL class to download a file.
  - Snoop.java example: a program that I used to use in industry to analyze protocols.
  - ShowDocument.java - contains an applet to demonstrate browser functionality. You will see an error on displaying this page because of the applet that is part of this example.
MVC, gameNet High Level(40m)
- Model View Controller (MVC) approach
- gameNet package - provided code that has the classes:
  - MyGame - Your Model class
  - MyGameInput - A class you define which contains the user inputs to be sent to the Game.
  - MyGameOutput - A class you define which contains the information sent from the Game for the User Interface to present to the user.
  - MyUserInterface - This class will contain the MVC "User Inputs Controller" and "Update View" code
  - MyMain - this class contains "main" and is responsible for connecting up all of the pieces.
- gameNet Architecture Chart views - block diagram and a Process and socket diagram view
gameNet interfaces(26.5m)
- In this set of notes, we present some code sketches of the MyGame, MyGameInput, MyGameOutput, MyUserInterface, and MyMain classes. We use a chat program as an example, because it is the simplest example we can do.
- MyGameInput and MyGameOutput can have almost anything, but must implement Serializeable.
- MyGame class must extend GameNet_CoreGame and will need to implement the "process" method. The process method will receive a MyGameInput parameter and must return a MyGameOutput object. It often will need to implement Serializeable (depending on the game design). This class contains the game logic.
- MyMain - contains main and starts the whole networked game up. MyMain must extend GameCreator and provide the method createGame(). Normally you don't need to do anything here, but copy a MyMain.java from some other Networked Game.
- MyUserInterface - This class contains your user interface. This class must implement GameNet_UserInterface which requires your class to have 2 methods:
  - startUserInterface - This method is called at the very beginning and passes in the "GamePlayer" object which is used for communicating with your networked game.
  - receivedMessage - This method is called to hand of a MyGameOutput object to the user interface. Typically this object contains information that needs to be drawn to the screen.
Tic Tac Toe(31m)
- This is the first of a series of examples using gameNet. The other examples can be found below. It is recommended that you pick the example that seems to most closely resemble the project that you wish to do and use it as a template.
- In particular, Tic Tac Toe has the following features:
  - It restricts the game to exactly 2 players
  - players alternate taking turns
  - An attempt was made to make the Tic-Tac-Toe specific logic reside in a separate module called TttLogic.java. The MyGame class mainly focussed on the gameNet issues and the generic idea of a game where we restricted to 2 players and the players need to alternate turns.
Zip of Networked Game Collection
- This zip file contains a project that contains all of the code to gameNet and all of the previously described networked games. Each game is in a separate package. The gameNet logic itself is also in a separate package. DO NOT USE gameNet_cloneable unless you discuss the ramifications of this with your instructor. In the "Networked Game/JH7" description you will find more words about when to consider gameNet_cloneable.
gameNet java documentation (using javaDoc)
Optional Maize and Shoot (improved) zip file
You now know enough to do all of the questions in JH5.
The last question in JH5 asks you to discuss your plans for the JH7 project.
At this point you have covered the theory. In the following section (9),
you will see several sample programs that give you more examples.
Focus on the one that seems closest to what you want to accomplish.
9: Networked Games

Rock, Paper, Scissors(26.5m)
- Rock Paper Scissors is the second example using gameNet. In this example we are restricted to 2 users, but the inputs can be received from the 2 users in any order. Once both users have made their input, we complete a "game round".
Chess with no brains(38.5m)
- This networked game gives you the starting point for a chess game. The code provided merely sets the board up and lets multiple players drag the pieces around. To make a better chess game, one could consider adding:
  - Restrict the game to 2 players
  - Have the players take turns
  - Restrict the pieces to legal chess moves ... the current code allows pieces to be moved anywhere
  - Provide capture logic
  - There are many other chess things that could be added to this game. A list of things can be found at the bottom of the lecture notes
- A technique called "Generic coordinates" is used to allow the chess boards to be different sizes on each user's screen
Quick Click - Threaded game(26m)
- In this game we start out with 20 disks bouncing around within your window. When a user clicks on a disk, he gets a point and the disk goes away. Once all of the disks have been clicked, we can see who clicked on the most disks. Then a "Restart" button can be clicked to start up a new game. This is the first example where we have objects moving on their own.
- In this game we can have any number of players. Players can join or leave the game whenever they wish.
- This program uses "generic coordinates" to allow users to have different sizes of screens.
- If your networked game will have things moving around on their own, Quick Click will show you how this can be done:
  - You will need to override the startGame method in GameNet_CoreGame in order to obtain your GameControl object and start any threads needed by your game.
  - Your overall MyGame class will likely implement Serializeable, but GameControl needs to be marked as "transient" which means that it shouldn't be sent across the network.
  - Your MyGame probably then needs to implement Runnable to provide a running thread. This thread can be the logic that can for example move "bouncing disks" around.
  - The GameControl method putMsgs can be called to send MyGameOutput objects to the user interface as needed.
Pong(28m)
- This networked game uses gameNet to create a 2 person Pong game. Like the Quick Click game above, this game demonstrates how to create games that have threads to support having objects moving around on their own.
- This game uses generic coordinates and restricts the number of users to no more than 2 players.
Networked Drawing Program(31m)
- This networked program is based on the Drawing program we developed in the Gui section of this class. However, in this program the drawing can show up on any number of users screens.
- Scribbling is very demanding on the Sockets and at some point too much scribbling will likely put gameNet into an overrload problem. I haven't had the time to track down the nature of the overload and how to avoid it.
- This example uses the "generic coordinate" approach so every user can have a different size screen.
10: Data Structures: Generics, Collection, List

Since we will be covering data structures, it would be helpful to
review the material in Section 2 on ArrayLists and Generics.
Optional Video: java.util.Array.java(42m) - skip on your first reading (i.e. won't be on the final) and is here for completeness
- This video is for completeness and isn't needed to succed in cps261 (not on the final or in any homework).
- Although an ArrayList is more flexible, real arrays can be more efficient if you don't need the flexibility of dynamic sizes.
- Note that Arrays can directly work with primitives which is unlike ArrayLists which have to convert the primitive to the appropriate Wrapper class. For example, an int is converted to an Integer class. This gives Arrays an efficiency gain.
- The java.util.Array class provides many built in methods: sort, binarySearch, fill, copy routines, and others.
- The TryOutArrays.java class demonstrates using some of these methods with an array of ints, array of Strings and an array of Dog classes (Dog is a class we write).
Collection and List Interfaces(53m)
- This lecture discusses the Java data structure interfaces Collection, List. Set, and SortedSet. The classes which implement these interfaces are also discussed: ArrayList, Vector, LinkedList, HashSet, TreeSet.
- The Collection interface is the most generic interface and makes very few assumptions of your data structure. Here are a few of the expected methods you must provide if you implement the Collection interface: add, contains, iterator, remove, size, clear, etc. Note that the method contains will only work if you have a proper "equals" method implemented for the elements stored in the Collection.
- The List interface extends the Collection interface and adds the notion of an ordering to the Collection. In otherwords, we can talk about what position an object has within the collection (i.e. first, second, ... last). ArrayList and LinkedList implement the List interface.
- The Set interface extends the Collection interface and adds the notion of uniqueness. A Set is not allowed to have 2 objects with the same value (as defined by the equals method) in the same Collection. HashSet is an implementation of the Set interface and using a technique called Hashing to implement the Set. Note that a Set has no special ordering of the objects within the Set.
- The SortedSet interface extends the Set interface and adds the notion of ordering to a Set. TreeSet is an implementation of a SortedSet. In addition to each object being unique within the Collection, we will know that with a SortedSet that when we list the elements we will get them sorted based on their natural ordering as defined by the Comparable interface. This means that all objects in the SortedSet will need to implement the Comparable interface.
- Iterators are a must in data structures and they are required of classes which implement the Collection interface.
- The Collections class (bad name ... probably should have been Algorithms) contains a bunch of useful static methods: binarySearch, sort, shuffle, etc.
Performance: List Interface(21m)
- In this lecture we execute a number of functions on a LinkedList and an ArrayList. We then compare and contrast the timings of these functions for a LinkedList and an ArrayList.
- Functions timed for both LinkedList and ArrayList: iterate, for loop, adding elements to the end, adding elements to the beginning, adding elements to the middle.
- Discussion of why the timings are so different between ArrayList and LinkedList. Bottom line is that every data structure will have its strengths and weeknesses. You must be smart enough to pick the data structure that is the best fit for the job you are trying to accomplish.
Performance: Algorithms(25m)
- In this lecture we introduce the concept of "big-O" notation.
- Sort algorithms are used to demonstrate the concept. We compare the algorithms: SelectionSort, QuickSort, and whatever algorithm Java uses in Collections.sort.
- In the analysis we discover that in "big-O" notation that SelectionSort goes as N*N while the other 2 sort algorithms go as N*Log(N) which is good for a sort routine. According to "big-O" notation QuickSort and the Collections.sort routine are similar, however, the Collections.sort routine is actually much faster. See the spreadsheet for the details.
- Another area that gets analyzed from a "big-O" point of view is Collections.shuffle and Collections.binarySearch.
LinkedList Implementations(49m)
- A LinkedList is a good data structure if you have to access or update either the front of the list or the end of the list. LinkedLists are often used when we have a Queue of things we need to store.
- Because a LinkedList implements the List interface, it has all of the methods of the List interface. To facilitate the things that a LinkedList does well, the following additional methods are available: addFirst, addLast, getFirst, getLast, removeFirst, and removeLast.
- In the Lecture we create MySingleLinkedList.java which is an implementation of a Linked List with only one link between nodes. The limitations to this implementation are discussed.
- Note the technique used to create an Iterator withan inner class. This is a common technique for iterators.
- More often we want a doubly linked list to allow easy manipulation of either end of the list. A data structure to implement this approach is described and MyLinkedListFirst.java provides a first cut at this approach.
- A more complete version of this is provided in MyLinkedList.java which actually implements the List interface.
11 - Data Structures: Performance, LinkedList, Set

Set Basics(36.5m)
- The Set interface extends the Collection interface but doesn't add any new methods. However, a Set must guarantee uniquess of all of its elements based on the "equals" method. Sets are not ordered and they do allow one null entry.
- All classes which implement the Set interface should be fast at identifing whether an object is already present within the Set. The class HashSet implements the Set interface and uses a "hashing" technique for finding elements in the Set. This implies that each of the elements in the set has an "equals" method and overrides the method "hashCode" (defined in the Object class).
- When you iterate through a HashSet, the elements often come out in a somewhat random order. The LinkedHashSet provides an improvement to the HashSet by remembering the order that the elements were added. So iterating through a LinkedHashSet, you get the elements coming out in the order they were inserted.
- The SortedSet interface extends the Set interface. It adds the notion that the elements are maintained in a sorted order. So if you iterate through a SortedSet interface, you will get the elements listed in their natural (increasing) order.
- Additional methods of the SortedSet allow you to grab subsets of the SortedSet with the methods: first, headSet, last, subSet, tailSet.
- TreeSet is a class that implements SortedSet and it uses a binary tree to store the data.
- Because there needs to be a way to compare each element to other elements in the SortedSet, each element in the SortedSet must implement the Comparable interface.
Set Examples(21m)
- In this lecture, some performance measurements are made on HashSet, LinkedHashSet, and TreeSet.
- An example is created called MathSet which extends HashSet. In the MathSet class we add 2 new methods for union and intersection which are common operations desired in a Math set environment.
MyHashSet(34m)
- In this lecture we create a class called MyHashSet.java which is an attempt to demonstrate what a class like HashSet is likely to look like if you could see it's code. The MyHashSet class implements the Set interface. From going through this lecture, it is hoped that you gain the following:
  - An understanding of what a hashing method is responsible for
  - An understanding how a hashTable could be structured and how inner classes like Node and Iterators would work.
  - How one would iterate through a hashTable
  - The concept of loadFactor and default size and how it could impact performance
Stack Parenthesis Checker - Help for MP6 (16.5 min)
- The concept of a Stack is discussed. Stacks are an amazing simple data structure and yet quite powerful for solving many problems.
- The class ParenthesisChecker.java solves a problem of checking to see if a program's parenthesis match. In this program we are actually looking at all occurrences of ( [ { and expecting them to be balanced with }]) .
- The approach taken uses a Stack and it is hoped that seeing this lecture will provide some help in solving the homework dealing with code indentation.
You now know enough to do JH6
12 - Data Structures: HashSet, Maps, Summary

MyTreeSet Data Structure (37.5 min)
- In this lecture we create a class called MyTreeSet which is an attempt to demonstrate what a class like TreeSet could look like if you could see its code.
- The theory of binary trees is discussed and the concept of unbalanced trees is discussed.
- In MyTreeSet a simple data structure is created for adding nodes to a binary tree.
- Iteration through the tree is discussed as it is somewhat tricky. Because we want to keep the MyTreeSet reasonable simple, a few issues are not addressed in this code. For example:
  - Keeping the tree balanced
  - Removing elements from the tree
More Tree Theory (39.5 min)
- Recursion is often useful when working with tree structures. For example determining the depth of a tree can be done quite nicely with the demonstrated recursive depth method.
- Sometimes we want to iterate through a tree is some order other than the "sorted iterator" approach done in the previous lecture. In this lecture we demonstrate a few other choices:
  - inorder (left subtree, node, right subtree)
  - postorder (left subtree, right subtree, node) - This approach is demoed in evaluating mathematical expressions in PostOrderEvaluation.java.
  - levelorder
- Generalized Tree Data Structure - the idea of having trees that are not binary, but are more general to represent something like generations of people. No code is provided here, but the idea is sketched. This can be a fun exercise for anyone who wants to have fun being creative with data structures.
Map - SortedMap Interfaces(52m)
- The Map interface is used for data structures where we need fast lookup of data objects based on some Key. The Map interface does not extend the Collection interface and it has the following characteristics:
  - Each entry consists of a Value and a Key.
  - The method put(Key, Value) is used for adding a new entry to the Map interface. Keys may not be duplicated, but the same Value entry can inserted more than once with different Keys.
  - The get(Key) method returns the entry associated with the parameter Key.
  - The Map interface has a method called containsKey to find out if a particular Key exists. The method keySet returns a "Set" of all of the Keys. The returned Set can then be iterated through using the concepts we have already covered with the "Set" interface.
  - The Map interface has a method called containsValue to find out if a particular Value can be found in the Map. If you call the "values" method, you will get a "Collection" of all of the Values in the Map. This "Collection" can then be iterated through using the concepts we have already covered with the "Collection" interface.
  - The HashMap, and LinkedHashMap classes implement the Map interface.
- Dogs.java example: A Dogs class is discussed to illustrate a class based on the Map interface and it demonstrates the methods: put, containsValue, containsKey, get, keySet, values, and entrySet.
- Statistics.java example: A Statistics class is presented to also demonstrate using the Map interface.
- StudentRecords.java example: A more complicated example is presented where the Key is more complicated than a simple String or integer. In this example, the Key is a Student class. If we are using HashMap or LinkedHashMap classes, then the Student class will need to implement the methods "equals" and "hashCode" to properly work in the required hashing approach. Note that there are many ways to create a hashCode method, but in this example we see at least one approach for our Student class.
- The SortedMap interface extends the Map interface. A SortedMap interface implies that the Keys are stored in a sorted fashion. Similar to the SortedSet interface, the SortedMap interface has a few extra methods available because of the sorted property: firstKey, headMap, lastKey, subMap, tailMap.
- The one class provided that implements the SortedMap interface is the TreeMap class. Like the TreeSet class, we find that the keys stored in a TreeMap must implement the Comparable interface. This is necessary to maintain a binary tree of keys which allows us to easily provide a sorted list of keys.
- All of our examples can be updated to work with TreeMap. For example in the Dogs.java example the main change needed here is that Dog must implement the Comparable interface. Also instead of constructing HashMap, we construct TreeMap.
Cross Reference Program (12 min)
- In this lecture, we create a simple cross reference program using a TreeMap. The declaration type is:
  - TreeMap<String, LinkedList>wordInfoTree;
- Note that the Key is a String which contains a word found. Because we are using TreeMap, the words will come out in alphabetical order when we iterate through them.
- Note that the objects stored with each word are LinkedLists of all of the line numbers where the word was found.
Data Structure Summary(8m)
- In this lecture we do a quick summary of the properties of all of the interfaces discussed: Collection, List, Set, SortedSet, Map and SortedMap.
- The properties noted are "Duplicates Allowed", Indexing, Sorted, "Implementing Class", and special Comments.
- Note that all elements stored in a data structure should implement the "equals" method. Elements should implement Comparable if we are storing in a TreeSet, or the Element is a key in the TreeMap class. Elements should implement "hashCode" if we are storing in HashSet, or the Element is a key in the HashMap class.
Final Hints
Please take the Final
13 - Fun Things, Extra Content (these extras are not on the final)

Running Java Programs outside of Eclipse
- In this set of notes we look at ways to run your program without the assistance of Eclipse. We are only making use of the Java platform.
Playing Sounds in Java
- This section covers a rudimentary program for playing Sound in Java. It works with ".wav" files, but we discuss how to convert any other format (like .mp3) to .wav using another application like "Audacity".
- A trivial sound player is shown that has a lot of limitations.
- A more functional sound player is created using concepts already covered in the course. This enhanced sound player can play a list of sounds, loop and be controlled to skip or stop the sound playing on demand.
JUnit Testing - Basics
- In this lecture, we take the Fraction assignment covered in cps161 and show how you could systematically test this code using an industry favorite testing tool called JUnit. JUnit is built into Eclipse.
JUnit Testing - Extras
- This lecture continues the JUnit lecture concepts. In addition to looking at additional JUnit features, we demonstrate an Eclipse pluggin which allows us to see which lines of our code have been tested: "coverage analysis"
Regular Expressions - String methods
- In this set of notes we introduce the concept of regular expressions and some of the useful methods in the String class that uses them: replaceAll and split .
Regular Expressions - Matching
- This set of notes adds some more Regular Expression capabilities and uses it to demonstrate more of the power built into this concept.
- The matches String method is used. Also the classes which really do the work ( Pattern and Matcher ) are introduced.
Regular Expressions - Substrings
- More capabilities of the Matcher and Pattern class are demonstrated. Also we introduce more Regular Expression capabilites. In this set of notes we are matching substrings of a bigger string of text. This is the underlying functionality of the split and replaceAll methods described in a in the "Regular Expressions - String methods" lecture.
Recursion and Stacks basics(48.5m)
- In this lecture we discuss recursion and the alternatives to recursion (often the alternative is using a stack).
- We start out with Factorial and Fibonacci problems. Using recursion with Fibonacci has a performance flaw that is demonstrated. In the lecture we show you how to compensate for the performance flaw in the recursive Fibonacci solution.
- The Knapsack problem is solved using recursion and using a stack.
Recursion: Towers of Hanoi
- In this video we demonstrate solving the Towers of Hanoi with recursion. I consider this an excellent example of where recursion is a great choice!! In general this a tough problem to solve, but recursion makes the solution deceptively simple.
N-Queens Recursion vs. Stack Algorithm(32m)
- The N-Queens problem can be defined as having N queens on a board (like a chessboard) which has N rows and N columns. Note that N can be 4, 5, ....8, 9, 10, ....Our job is to place the N queens on the board such that none of the queens can be attacked by any of the other queens.
- In this lecture, we demonstrate 2 ways to solve the problem. One is with recursion and the other is with a stack.
- To demonstrate the algorithm we connect our problem solver to some additional code which draws the board and slows down the solver so that you can see the algorithm in action (we slow it down to have a second between each new step).
- To make all of this happen we make use of earlier concepts discussed in this course including: Threads, sleep, wait, notify, etc.
Maize Stack Algorithm(40.5m)
- In this lecture we take a look at finding a path through a Maize.
- The solution demonstrated in this lecture uses a Stack approach.
- Because the number of combinations you would encounter using a Stack is staggering, we provide some heuristics to provide some intelligence to the Maize stacking algorithm.
- We also demonstrate the algorithm by drawing it in action on the screen using a similar techniques as we used in the N-Queens problem above that uses Threads to slow down the problem solver.
- Further more, if you can solve a Maize then in this lecture we demonstrate that you can create a Maize. The idea is that you start out with a Maize that has few options and ask the solver to try to find a path. When the solver comes back with a failure indication, we then randomly "punch" an additional hole in the Maize and try again. If we punch enough holes in the Maize then eventually our Solver will come up with its first solution. At this point we stop and save the Maize created knowing there is at least one path through the Maize.
- I might point out that similar thinking to the Maize problem can be used for solving other puzzles. For example, I have created Sudoku problem solvers. Additionally by using a created Sudoku problem solver I can create Sudoku puzzles.
14 - Graphics2D Fun Things, Extra Content (these extras are not on the final)

Zip Project containing all of the Graphics2D programs
- This whole section presents additional capabilites that are provided with the Graphics2D class which extends the basic Graphics class. This link downloads an executable project with all of the examples in it.
BasicStroke class
- In this set of notes we explore the ramafications of creating a wider line(or Stroke) than the default 1 pixel stroke. We also look at the effect of " Rendering Hints ". The BasicStroke manages the issues:
  - Join : How to draw the bend where 2 lines come together.
  - Cap - How to draw the end of a line
Animation techniques
- In this set of notes we first review Animation techniques where we explicitly create a Thread to call repaint in order to create an animation.
- Secondly we demonstrate a new class: javax.swing.Timer which simplifies the Animation process.
Dashes
- How to create a Dashing pattern
- How to use the dashPhase to create a moving dash appearance.
Shape Concepts
- The concept of the Shape interface and some examples: Ellipse2D.Double, RoundRectangle2D.Double.
- GeneralPath Shape to draw arbitrary shapes.
- Area class to combine shapes together.
Shape Fill Options
- Gradient Fills
- TextureFills - Wall papering an image
Transformations using AffineTransforms
- AffineTransform concept and doing a Translation
- Other operations: rotations, scaling shearing
- Donut transformation example
Composition
- AlphaComposite class - composite rules and transparency options
- Sun fade out example against the clouds using AlphaComposite rules
More Composition Examples
- Using a BufferedImage with AlphaComposite concepts
- Spotlight example using AlphaComposite concepts
- Animated Waiting example: uses Transformations and AlphaComposite concepts
Clipping
- Simple clipping example on an image
- Rotating Shape Clip area example.
Demo approaches: Moving Star
- Using Translation, Rotation, and Scaling to create a fast moving star that has lots of flicker
- Using a JPanel to get rid of the flicker in the previous example
More Demos -- mostly a review
- Moving Scaling object using a new interface: WheelListener
- More examples for review purposes: Bubbles Demo, "Puffer" Demo, Resizing Rectangle
Tools

Jing
- When you want to describe a problem that you are having, you will find JING is a valuable tool to show your problem. With JING you will get a URL to any video you create and this URL can be placed on the discussion board to assist you in creating a Question, or an Answer to a Question.
- The associated video discusses JING installation and demos creating a video.
Development Environment
- Installing Java
- Installing Eclipse and the fundamentals of using Eclipse
Eclipse Goodies - Eclipse features that will be useful to you
- Indentation: Eclipse will indent your code automatically
- Refactoring: If you want to rename a variable, Eclipse will automatically update all instances where the variable.
- Packages: Using packages is like having folders to organize your Java code into modules.
Eclipse Debugger - Become friends with the Debugger if you have had trouble getting programs to work
- Debugger basic features: Break Points, Single Step, Resume, Step Into, Step Return, Terminate
- Additional information in windows: Variables, Break points
- Step Filters need to be set to avoid the Deadly Eclipse "Source Not Found Error"
Optional Video: Command Line Java Development Environment
- This is an optional video that demonstrates how to do Java work outside of Eclipse using javac and java programs from the command line.
- There is also a fun little game demo'ed in this video called "planetoid".