CS151 lecture notes, Fall 1999
Week 14, Friday

Last lecture!!!

Review of analysis
------------------

Define problem size:  n  (size of the array)

Define the operations you are interested in: comparisons

Find the number of operations as a function of n.


Analysis of sort algorithms
---------------------------

How many comparisons do you have to do using the
simple sort algorithm?

       Have to traverse the array (n-1 comparisons).

       At each iteration we have to find the largest
       among n-i elements (where i is the iteration number).

       Total comparisons =

       n + (n-1) + (n-2) + ... + 1

       Draw a triangle diagram to motivate the solution n/2 (n-1)

       The leading order term is n^2, which means that as n
       gets big, the behavior of this curve is like n^2.


How many comparisons do you have to do in a mergesort?

    At each level of recursion, the number of comparisons is n-1.

    How many levels of recursion are there?




Yes, but what about overhead?

     Mergesort has to create a lot of little arrays.

     That takes time, and wastes some space.

     Which means that the constant factor is probably large.


Which is better,  2 n^2  or  1000 n log n?

For large n, eventually, n log n wins.


EXAM REVIEW
-----------

Emphasis on 9-13, although everything is fair game.


Some state diagramming:

     including all kinds: object (box and arrow)
     iteration tables, stack diagrams, arrays

Some algorithm design:

     use abstract building blocks and pseudocode to
     describe algorithms at the high level without
     getting bogged down in details

Some programming:

     bring lots of code samples so you can copy code
     fragments and avoid syntax errors.

Some vocabulary:

     review class notes as well as glossaries

Some debugging:

     Sharpen those red pencil eyes.


So what have we learned?
------------------------

1) abstraction:  extending the existing language by
   defining new methods and then using those new methods
   as abstract tools for solving bigger problems

   (toolkit building)

2) problem recognition: toolkit using

3) debugging: the skills we practiced for tracking down
   errors are applicable in a wide range of situations

4) algorithm design and analysis: algorithms, as general
   problem-solving patterns, are useful in many areas outside
   programming, like telling other people what to do.