CSC151 2010S, Class 42: Analyzing Procedures, Continued

Overview:
* Comparing algorithms.
* Two related metrics: Time and Number of procedure calls.
* Tools for time analysis.
* Looking at reverse, revisited.
* Lab.
* Reflection.

Admin:
* Reading for Wednesday: Association Lists.
* Are there final questions on the project proposals?
* You might enjoy the cartoon linked from today's outline.
* EC for Thursday's Thursday Extra on Media Computation 
  (Thursday, 4:30, Science 3821).
* EC for cultural evening friday sponsored by ISO.
* EC for Chamber Concert Saturday at 3:15 in S-L.
* EC for Multicultural open house on Thursday.  (Food!) (Eat responsibly.)

Given multiple algorithms that solve the same problem, what criteria might you use in choosing one over another?
* The "most efficient" one
  * The fastest one
  * The least number of procedure calls
  * Most concise
  * Uses the least memory
  * Programmer time in writing the procedure
  * Note: Its efficiency may depend on the inputs
* The one that's cleanest
* Easiest to read / laid out logically
* Versatility: How many different problems can I solve with the same procedure?
* Easiest for the client programmer to understand
* Most correct
* Most elegant / beautiful
* Most in-line with policies

We need ways to analyze the "average" speed of
a procedure on a certain input size
* Time it.
* Count the number of procedure calls.
* Use combinatorics ideas.
* For each of these, we can try to look at the pattern of "time" (wall time, proc calls) vs. input size.
* Why count rather than time?
  * Lots of variables that may not be significant (e.g., gathering inputs)
  * Time is not necessarily consistent: If you're running other programs, or if the server is insane, time can change significantly