cs230 Lecture Notes
Spring 2002
Week 14, Monday

General patterns
----------------

1) traversal (iterative and recursive)

2) accumulator (sum, product, maximum, etc.)

3) eureka



Traversals
----------

We have idioms for traversing

Strings, StringTokenizers,
arrays, LinkedLists, Vectors,
Stacks, Queues, PriorityQueues,
Hashtables (using an Enumeration)

Use simple idioms

1) for Strings, use charAt (no need to make a char array)

2) for Vectors, use get (no need to make an Enumeration)



List patterns
-------------

Functions that return primitives

1) sum, product, maximum, minimum

2) search

3) count number of nodes, leaves, cargo, cargo with some property


Modifiers

1) add elements

2) remove elements

3) change cargo



Functions that return lists

1) filter

   evens: return a new list with all elements that are even integers

2) running sum

   run: return a new list where each element contains the sum of
        its predecessors

	1 2 3 4 => 1 3 6 10

   backRun: each element contains the sum of its successors

        1 2 3 4 => 10 9 7 4

   
Functions on two lists

1) append

2) merge, interleave

3) elementwise comparison, BigInteger addition



Tree patterns
-------------

Functions that return primitives

1) sum, product, maximum, minimum

2) search

3) count number of nodes, leaves, cargo, cargo with some property

4) check properties

   height: return the height of a tree

   isHeap: check whether a tree is a Heap


Modifiers

1) add/remove subtrees (not all that common)

2) change cargo

   example: heap insert and remove shuffle lots of cargo


Functions that return trees

1) filter

2) running sum

Given a tree of Integer objects, build a new tree that is the same
shape as the original tree, but in which each node contains the
sum of all the nodes in the corresponding subtree.


Functions on two trees

1) append (where?)

2) merge?  interleave?

3) comapare shapes?



Algorithm design
----------------

Look for intermediate data structures that perform useful
operations using standard idioms

0) histograms are often good for pattern-matching, comparison
   of compound objects, statistical description

1) Stacks are often good for reversing the order of things

2) PriorityQueues often good for sorting

3) Hashtables are good for checking set membership

4) Hashtables are good as a generalization of an array
   (index can be any type)

5) Hashtables are a good way to implement a histogram