cs230 Lecture Notes
Week 2, Friday

For today you should have read Chapters 4 and 5 and started
homework 1.

For next time you should continue with Homework 1.


Performance analysis review
---------------------------

How long does it take to do a linear search?

How long does it take to do a bisection search?

Which is bigger, n/2 or log2 n?

What about (n/2) and (100000 * log2 n)?



Shuffling
---------

Algorithm

The way humans do things is often dictated by real-world factors
that do not apply to programs.

Beware misleading analogies.

How can we express algorithms?  One option, pseudocode:

    for (int i=0; i<deck.cards.length; i++) {
      // choose a random number between i and deck.cards.length
      // swap the ith card and the randomly-chosen card
    }


Development

1) pseudocode

2) helper methods -- test independently

3) assemble


Implementation details

1) Aliasing and cards

   Mutable or no?

2) Swap just the references to the cards or the contents of the cards.

   Does it matter which one you choose?  Which is faster?


Sorting
-------

Algorithm

Development: take advantage of symmetries!

Implementation details



    for (int i=0; i<deck.cards.length; i++) {
      // find the lowest card at or to the right of i
      // swap the ith card and the lowest card
    }



Mergesort
---------

Algorithm

1) divide

2) conquer

3) merge


Development

Incremental development of recursive method

1) write and test the helper methods independently

   (subdeck and merge)

2) make one recursive step and then use sortDeck to
   solve the subproblem

3) write the fully recursive version


Performance analysis part two
-----------------------------

What operations should we count?

How long does selection sort take?

How long does mergesort take?