cs230 Lecture Notes
Week 7, Monday

Homework 5 is due Thursday.

Also, please read Chapter 16 and prepare for a quiz.

Topics left over from last time:

1) performance analysis of reverse

2) run time class vs. compile-time class


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

How does a stack help with checking balancing and nesting?



List processing patterns
------------------------

Eureka pattern:

1) do all the elements of the list have some property?

2) do any elements of the list have some property?

3) compare two lists elementwise.


Counting:

How many elements of the list have some property?


Processing:

1) apply some modification to each node in a list.

2) compute some function of the nodes in a list.


Filtering:

1) modify this list by removing elements with some property.

2) return a new list that has some of the elements from this list
   (or copies thereof).

   example: remove the null objects from an object list.

            modifier or function?
   

Merging/appending:

1) combine elements from two lists.


Options
-------

1) LinkedList class or Node class or both or helper/wrapper

2) modifier or function

3) object method or class method

4) recursive or iterative

   (in class exercise)

This is called interface design.


Lists vs. Arrays
----------------

Both have elements.

Both provide similar operations.

Fundamental difference is performance:

1) in an array, random access is constant time
   (for a list it's linear)

2) in a list, inserting and removing elements is constant time
   (for an array it's linear)

Lists often lend themselves to recursion, because it is easy
to split a list into head and tail.

With arrays, we usually end up passing around the array plus
indices.


Which would you prefer for bisection search?

Which would you prefer for mergeSort?