CPSC 225, Spring 2019
Information About the Second Test

The second test will be given in class on Monday, April 15. It covers Section 9.4, Sections 10.1 through 10.4, and Sections 11.1 through 11.3. Note that sections 9.5 and 10.5 are not included. There will be no questions on JavaFX or GUI programming. There will be no questions that are specifically about earlier material; however, you should know that material and you might need to know it for some questions. (In particular, questions about the classes in the JFC might require some knowlege of the actual data structures that they use internally, which were covered in Chapter 9. Also, there could be questions about run time efficiency that use what you learned about that topic back in Chapter 8. And of course you need to know everything that you learned in CS 124.)

The format will be similar to the first test: There will be some definitions and essay-type questions. Some questions will ask you to write code segments or methods or possibly even complete classes. There might also be some questions that ask you to read some code and figure out what it does.

Here are some terms and ideas that you should be familiar with:

binary trees
tree node:  contains left and right child pointers
root of a binary tree; leaf in a binary tree
recursive structure of a binary tree:
     a tree is empty or consists of a root and two subtrees
recursive processing of a binary tree
traversals of a binary tree: preorder, postorder, and inorder traversal
BST (Binary Sort Tree):  inorder traversal visits nodes in increasing order
inserting an item into a BST; searching for an item in a BST

generic programming
what problem is solved by generic programming?
parameterized classes in Java, such as ArrayList<T> and HashMap<K,V>
type parameters in parameterized classes
the Java Collection Framework (JCF)
working with generic lists, sets, and maps

the JFC does not work with primitive types
wrapper classes for primitive types: Integer, Double, Boolean, Character
using wrapper classes with the JFC
the class Object, the superclass for all classes
methods in class Object that are often overridden: toString(), equals(x), hashCode()
the interface Comparable<T> and its method compareTo(x)

Collections: Lists and Sets
using a "for-each loop";  example:  for ( String str : strList )...
using sets to store collections with no duplicates
using TreeSet to store sets in increasing order, based on the compareTo() method
implementing mathematical set operations with addAll(), removeAll, retainAll()
using maps to associate values to keys
hash tables and hash codes
the structure of a hash table: an array of linked lists
how hash codes are used
run-time efficiencies of various operations
comparing run times for operations on ArrayList and LinkedList
find, insert, remove operations on TreeSets/TreeMaps run in time Θ(n*log(n))
find, insert, remove operations on HashSets/HashMops run in average time Θ(1)

parameterized interfaces and classes in the JFC
    Collection<T>; methods: 
               add(x), remove(x), contains(x), size(), clear(), isEmpty(), iterator(),
               addAll(collection), removeAll(collection), retainAll(collection)
       List<T>; extra 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>
       
the stream API
using lambda expressions with the stream API
creating streams:  collection.stream(), Arrays.stream(array), IntStream.range(n,m)
intermediate operations:  filter(p), map(f), mapToInt(f), mapToDouble(f)
terminal operation: forEach(action), count(), sum()

I/O streams for input and output
files
how I/O streams and files are abstractions and why that is important
binary I/O streams versus character I/O streams
character sets and character encoding; for example, ISO-8859-1, UTF-8, UTF-16
InputStream and OutputStream
Reader and Writer
IOExceptions
PrintWriter:  the methods print(), println(), printf(), checkError()
files, directories, and file paths
the File class; methods:  exists(), length(), canRead(), canWrite(), isDirectory()
FileReader and FileWriter; FileInputStream and FileOutputStream
using a Scanner to read from a text file
using a PrintWriter to write to a text file
designing a format for a data file
why use human readable (character) files?

Some Sample Questions from Old Tests...

1. (a) Suppose that the letters in the tree on the left below are printed out using a in-order traversal. List the letters in the order in which they are printed. (b) Place the letters A through K into the tree on the right below so that when the letters are printed by a post-order traversal of the tree the letters will be printed out in the order A B C D E F G H I J K

2. Suppose that binary trees of integers are implemented using the TreeNode data type shown below. Write a recursive method with a parameter of type TreeNode that returns the number of times that the number 17 occurs in the tree.

                  class TreeNode {
                      int item;
                      TreeNode left;
                      TreeNode right;
                  }

3. There are two Set classes in Java, TreeSet and HashSet. What's the difference? How do the run times of their operations compare? Why might you choose to use one rather than the other?

4. The Java Collection Framework uses parameterized types such as ArrayList<T> and TreeMap<K,V>. Discuss parameterized types: What can you do with them, and why do they exist in the Java langauge? What do parameters like the "T", "K", and "V" represent?

5. Suppose that a variable named words is of type TreeSet<String>.
(a) Write a code segment that uses a "for-each" loop to print out all the words in this set.
(b)The set is represented as a TreeSet rather than a HashSet. What consequence does this have for the output in part (a)?
(c) Under what circumstances might you prefer to use a HashSet rather than a TreeSet? Why?

6. Suppose that a variable named symTab is of type HashMap<String,Double>, and that symTab is used to represent a symbol table that associates values to "variable" names.
(a) Write a Java statement that will associate the value 3.14 to a variable named pi.
(b) Write a Java statement that will print out the value associated to the variable named foo.
(c) Suppose that you want to add 1 to the value associated with the variable named count. Write one or more Java statements that will do this. (You want to change the value that is stored in the symbol table, not just compute the answer!)

7. A file named "data.dat" contains integers. Write a program that will read the integers from this file and create a new file named "result.dat" that contains the same integers, but sorted and with duplicates removed. You can do this using only the classes listed in the import statements shown below. You can use one big try..catch to handle errors.

   import java.util.Scanner;
   import java.util.TreeSet;
   import java.io.File;
   import java.io.PrintWriter;
   
   public class Uniq {
      public static void main(String[] args) {
      

8. Write a Java code segment that will create a HashSet<Integer> that contains exactly 10 different numbers chosen at random from the range 0 t0 99. (Hint: In the end, the size of the set must be 10.)

9. Suppose that dictionary is a variable of type HashMap<String,String> in which the keys are words and the values are the definitions of the words. (a) The definition of the word "eschew" is "avoid rigorously." Write a Java statement that will add this definition to dictionary. (b) Write a code segment that will determine whether the word "obfuscation" has a definition in dictionary. If it does, the code segment should print the definition; if not, it should print out a message saying so.

10. Suppose that A and B are variables of type i>HashSet<Integer>. Write a code segment to find and print out how many integers are in the intersection of A and B.

11. Suppose that the variable grades is of type ArrayList<Student>, where Student is the class shown here:

             class Student {
                 String name;
                 int homework;
                 int midterm;
                 int final;
             }

The following code segment was used to print the contents of the ArrayList, grades, to a file named "grades.dat":

            try {
               PrintWriter out = new PrintWriter(new File("grades.dat));
               out.println(grades.size());
               for (int i = 0; i < grades.size(); i++) {
                  Student std = grades.get(i);
                  out.print(std.midterm + " ");
                  out.print(std.final + " ");
                  out.print(std.homework + " ");
                  out.println(std.name);
               }
               out.flush();
               out.close();
            }
            catch (IOException e) {
               System.out.println(
                     "Sorry, an error occurred while trying to write the file.");
            }

12. Java has four basic abstract "I/O stream" classes that are used for input/output: InputStream, OutputStream, Reader, and Writer. State briefly what each of these clases is for. Then explain what it means that they are abstract classes and why it is so useful to have abstractions to represent I/O streams.