Test 3 Study Guide

- Know the linear search algorithm, when it
is appropriate to use, and its relative efficiency (big-O notation).
- Know the binary search algorithm, when it
is appropriate to use, and its relative efficiency.
- Know algorithms (not the code, just how
they work) for selection sort, bubble sort, heap sort, quick sort.
- Know the time efficiency of each sorting
algorithm (big-O notation for selection sort, bubble sort, insertion sort,
heap sort, and quick sort).
- Know logs of numbers in base 2.
- Be able to explain the advantages of
generic classes.
- Be able to implement a generic class.

·
Know the basic operations on a stack.

·
Know the basic operations on a queue.

·
Know how to use a stack and a queue

·
Be able to hand-execute binary tree traversals: pre-order,
in-order, and post-order.

·
Understand how a binary search tree is organized.

·
Understand how trees are used to represent arithmetic
expressions.

·
Know the definition of a graph.

·
Know how to do a depth-first traversal of a graph.

·
Know how to do a breadth-first traversal of a graph.

·
Know how to do a topological sort of a directed graph.

·
Know how to implement a graph.

·
Be familiar enough with the Java collections
that are in the textbook that you can __write your own code__ using them.
Note that all of these are *generic*
classes.

·
Use both 1-dimensional arrays and 2-dimensional arrays of
either primitives or objects in a program.

·
Pass arrays as parameters.

·
Return arrays from functions.

- Know how to read data from a file using a
*Scanner*object; know how to use the*Scanner*functions.

- Create classes, write
accessor (get) and mutator (set) methods, override methods.

- Definition of recursion.
- Understand how activation records go on the stack.
- Hand-execute a recursive subprogram.
- Know advantages and disadvantages of recursion vs. iteration.

·
Understand how an array is implemented in memory.

·
Understand the difference between a direct access data structure
and a sequential access data structure.

·
Know when a linked data structure is appropriate and when
another type of list structure is appropriate.

· Know what hashing is used for.

· Know in general how hashing works.

· Know advantages and disadvantages of hashing.

·
Be able to use a generic class in a program.

·
Be able to create your own generic class.