CPSC 225, Spring 2010
Information About the Final Exam

The Final Exam for this course is scheduled for Sunday, May 9, from 1:30 to 4:30, in our regular classroom. The exam will be in the same general format as the in-class tests, but will be six pages long instead of four. It will cover material from the entire semester.

On the last day of class, Monday, May 3, you can show your final project, but you can continue working on it after that if it is not completely finished. The deadline for turning in your project is 9:00 AM on Monday, May 10. At that time, your project should be copied into your homework folder in /classes/s10/cs225/.

During the week leading up to the exam, I expect to have office hours as follows:

          Sunday, May 2        11:00 -- 4:00
          Monday, May 3        11:00 -- 12:10
          Tuesday, May 4       10:00 -- 11:00
          Wednesday, May 5     11:00 -- 4:00
          Thursday, May 6      11:00 -- 5:00
          Saturday, May 8      11:00 -- 4:00
          Sunday, May 9        12:00 -- 1:20

Here are some of the major themes of the course. You should understand them in depth. You should be able to write about them and apply them to programming.

• Efficiency and the run-time analysis of algorithms. You should understand "Big-Theta" and "Big-Oh" notation. You should be able to analyze code segments and you should be familiar with the run-time characteristics of important algorithms and data structures.
• Error handling. You should understand the use of try..catch..finally to organize error handling and improve the robustness of your programs.
• Multiprocessing. You should know the basics of using Threads in Java, the reasons for doing so, and the problems involved in sharing resources between threads.
• Recursion. You should be able to create and understand recursive algorithms, and you should know about some of the common applications of recursion.
• Linked Data Structures. You should be able to work with linked data structures, including linked representations of lists, queues, stacks, and binary trees.
• Generic programming and parameterized types. You should understand what generic programming is, why it is useful, and how Java implements generic programming using parameterized types. You should know how to use important parameterized types in the Java Collection Framework, including lists, sets, and maps.
• Java's input/output framework. You should be able to work with Files, Sockets, and Streams. You should understand the difference between binary streams and character streams, and you should be able to use PrintWriters and Scanners. You should know what it means to design a file format or network protocol.
• Events and state machines. You should know what it means to say that GUI programs are state machines in which the effect of an event depends on the current state and can change that state.
• Model/View/Controller. You should understand the MVC pattern: what it means to say that it is a design pattern, how it can be applied, and what its advantages are.
• Class Design. You should understand important considerations in the design of classes and class hierarchies, such as encapsulation, separation of responsibilities, and expressing common properties of classes in a common superclass.
• Abstraction. You should understand the fundamental importance of abstraction in computer science, including its application in abstract data types, abstract classes, and class hierarchies in general, as well as specific examples such as Streams, Iterators, and the Java Collection Framework.

Here are some things that we have covered since the second test:

client/server model for network communication
sockets
network hosts and port numbers

the Socket class:  
       Socket s = new Socket( host, portNumber );
       methods:  s.getInputStream(), s.getOutputStream(), s.close();

the ServerSocket class:   
       ServerSocket s = new ServerSocket( portNumber )
       Socket c = s.accept();

the HTTP protocol:  a request/response protocol
       basic request format:    GET filepath HTTP/1.1
       basic response format:   HTTP/1.1 200 OK, HTTP/1.1 404 Not Found
       mime types and the Content-Type header
       common mime types:  text/plain, text/html, image/png, image/jpeg

GUI programming
state machines
events and event listeners

resources
resource URLs:  
       ClassLoader cl = getClass().getClassLoader();
       URL resourceURL = cl.getResource( pathToResource );
       BufferedImage img = ImageIO.read(resourceURL);  // (for example)
       ImageIcon icon = new ImageIcon(resourceURL);  // (for example)
                
using icons on JButtons and in JMenuItems

Actions and AbstractAction
using Actions to create buttons and menu items

design patterns
Model/View/Controller pattern
how the model, the views, the controller interact
how JList uses the MVC pattern:  ListModels and DefaultListModel

Here are the more important topics from the review sheet for the first test:

exceptions
handling exceptions: the try..catch statement
the finally clause in a try statement, and why it might be used

questions of efficiency of a program
run-time analysis of algorithms
worst-case analysis and average case analysis
log2(n) and how it arises in analysis of some algorithms
"Big Theta" and "Big Oh" notation ( Θ(f(n)) and O(f(n)) )
comparing Θ(n) to Θ(log(n)), or Θ(n2) to Θ(n*log(n))

recursion
recursive methods
base case of a recursion
maze-solving and similar recursions
infinite recursion, and why "marking" locations as already visited is important
the QuickSort recursive algorithm
the idea of QuickSortStep (but not the detailed code)
the general idea of why QuickSort has average case run time Θ(n*log(n))
the worst case run time of QuickSort
the recursive nature of grammar rules for Java and for English

linked data structures
understanding names such as "employee.boss.name" and "node.next.next"
simple linked lists
the head of a list; why you always need to keep a pointer to the head
traversing a linked list; using a "runner" to move down the list
basic linked list processing, such as searching, or adding up items in a list
the meaning of "while (runner != null)" and "runner = runner.next"
adding a node to the head of a list
why working at the head of a list is often a special case
inserting and deleting nodes in a list
using a "tail" pointer in a list; adding a node a the end of a list
doubly-linked lists

Abstract Data Types (ADTs)
alternative implementations of ADTs
relation of ADTs to interfaces and abstract classes
the "Queue" ADT
queue operations: enqueue, dequeue, isEmpty
how to implement a queue as a linked list with tail pointer
the "Stack" ADT
stack operations: push, pop, isEmpty

binary trees
recursive traversal of a tree
inorder, preorder, and postorder traversals
binary sort tree
inserting items into a binary sort tree
searching for an item in a binary sort tree
balanced binary tree
inserting/searching in a balanced binary sort tree has run time Θ(log(n))

Here are the more important topics from the review sheet for the second test:

multi-processor computers and why parallel processing is necessary
threads
the Thread class
writing subclasses of Thread
the run() method in a thread
starting a thread, running a thread in parallel with other threads
race conditions; what can happen when two threads both use a shared resource
what it means for a thread to block
why threads are often used in network programming
ArrayBlockingQueue<T> and LinkedBlockingQueue<T>
the put() and take() methods in a BlockingQueue (and why they can block)

generic programming
what problem does generic programming try to solve?
parameterized types; for example, ArrayList<T>
wrapper classes; Integer, Double, Character, etc.
using wrapper classes with parameterized types; for example, ArrayList<Integer>
iterators
"for-each" loops; for example:   for ( String str : strList )...
using a for-each loop to traverse a collection
the JCF (Java Collection Framework)
collections, lists, and sets
run-time performance of various operations on lists and sets
ArrayLists versus LinkedLists [differences; when to use]
HashSets versus TreeSets [differences; when to use]
maps
keys and values in maps
hash tables
HashMaps versus TreeMaps  [differences; when to use]
uses of lists, sets, and maps

Generic interfaces and classes in the Java Collection Framework:

    Collection<T>; methods:  add(x), remove(x), size(), clear(), isEmpty()
       List<T>; methods:  get(index), set(index,x), remove(index)
          ArrayList<T>
          LinkedList<T>
       Set<T>
          HashSet<T>
          TreeSet<T>
        
    Map<K,V>; methods: put(k,v), get(k), containsKey(k), keySet()
       HashMap<K,V>
       TreeMap<K,V>  
       
streams for input and output
files
how streams and files are abstractions and why that is important
binary streams versus character streams
InputStream and OutputStream
Reader and Writer
IOExceptions
Scanner
PrintStream
files, directories, and file paths
the File class; the exists() method
FileInputStream and FileOutputStream
using a Scanner to read from a file
using a PrintWriter to write to a file
saving data in a file
choosing a format for a data file
why use human readable (character) files?