Java and Object-Oriented Programming (OOP)

• arrays
  • random access
  • contiguous
• public vs protected vs private variables, classes, methods
• objects vs instances
• instance, local, and parameter variables (and criteria for determining when you should use each type of variable)
• messages
• instance methods, constructors (and how to write them)
• prototypes, signatures, access modifiers, return types
• getters and setters
• writing your own classes
• primitive types vs. object types
• inheritance, polymorphism, overridden vs. overloaded methods
• pass-by-value mechanism of parameter passing
• this
• linked lists
• explicit and implicit casting
• short-circuiting
• Javadocs (how to write, how to read)
• interfaces, implementations of interfaces
• abstract classes, methods
• primitive casting and object casting (both implicitly and explicitly)

Good Program Design (OO goals)

• coherency
• reusability
• modularity
• efficiency
• understandability
• robustness
• encapsulation
• data abstraction
• information hiding
• debugging techniques
• testing techniques
• top-down design
• memory diagrams (how to read, how to draw)

Time Complexity

• Determing exact running time and Big-O running time for
  • an algorithm
  • an implementation
  • a set of runtime data
• Where Big-O comes from and why we use it

ADTs

• Bag
• Priority Queue
• Stack
• Queue
• Tree
  • general trees, complete trees, full trees
  • binary trees
    • tree traversals
  • expression trees
  • decision trees
  • binary search trees
  • dynamic search trees
    • 2-3 trees
  • heaps
• Table (especially hash tables - covered on Monday)
• array or linked list (or other?) implementations for any of the above

Recursion

• numerical vs. structural recursion
• identifying base and general cases
• identifying recursive ADT structure
• writing recursive code

Searching

• Linear search
• Binary search
• Searching with different ADTs (table, tree, etc.)

1. Write a method called binSearch() that performs a recursive binary search on an array of ints. The prototype will be:

   public int binSearch(int[] A, int key)
   

   where A is a sorted array of ints and key is what you are searching for.

   Your method will return the index of the found key or -1 if the key was not found.

   You should be able to solve this with just the above, but if you get stuck, here's a hint to help you.

2. Suppose you wrote a Stack class with the following methods:

   public void push(String x)
   public String pop()
   public String top()
   public int size()
   public boolean isEmpty()
   

   and a Queue class with the following methods:

   public void insert(Object x)
   public Object remove()
   public int size()
   public boolean isEmpty()
   

   Write the following method in the Stack class:

   public void reverse()
   

   that reverses the elements in the stack. So whatever was at the top of the stack will now be at the bottom. This method is destructive by nature. You must write your code using only the behavior indicated above, without relying on any specific implementation. You may assume that default constructors exist in both classes.

3. Which of the following are heaps? For those that are not, why not?

4. Assume we have the following LinkedList and ListNode classes:

   public class LinkedList                 public class ListNode
   {                                       {
      private ListNode firstNode;              public int data;
      private int length;                      public ListNode next;
   
      public LinkedList {                      public ListNode {
        firstNode = null;                        data = null;
        length = 0;                              next = null;
      }                                        }
   }                                       }
   

   Suppose this represented a circular linked list (where the last node points back to the first node). Write the following method in the LinkedList class:

   public void linearize()
   

   which turns the circular linked list back into a linear one (where the last node points to null). Remember, in a 1-node circular list, the node points back to itself.

5. In a BinarySearchTree class, write the following recursive method:

   public int leafCount()
   

   which returns the number of leaves in the tree. You may assume the existence of the standard BSTnode class that we've seen before.

6. Using h(k)=k%M as a hash function, show the final state of the hash table after the following keys have been inserted:

   62, 73, 19, 32, 66, 54

   Use linear probing to resolve collisions where the probe will move toward higher indices in the table. The table size, M, is 11.

7. Redo the problem above except use double hashing to resolve collisions. p(k)=max(1,(k/M)%M)

8. Draw the expression tree for a*((b+c)*(d*e+f)). Then draw the expression tree for a*(b+c)*(d*e+f). Why are they different?

9. Insert the following values into a maxheap. After each insertion, show the state of the heap in both tree form and array form.

   44, 66, 33, 88, 77, 55, 22.