Class 39: Analyzing Procedures

Back to Trees. On to Testing Your Procedures.

This outline is also available in PDF.

Held: Tuesday, 10 November 2009

Summary: We consider techniques for analyzing the number of calls made in evaluating procedures, particularly recursive procedures.

Related Pages:

Notes:

Reading for tomorrow: Testing Your Procedures.
Are there questions on Assignment 7?

Overview:

Comparing algorithms.
Two related metrics: Time and Number of steps.
Counting procedure calls by printing.
Tools for analysis.

Overview

When comparing algorithms, we often care which one is faster.
We can analyze by hand.
We can analyze by using a library written at Grinnell.
We can carefully study the code and predict (covered in future CS courses)

Steps in Automating Analysis

Replace define with define$.
Type (analyze exp procedure)
Alternately, type (analyze exp).

Lab

Do the lab.

Back to Trees. On to Testing Your Procedures.

[Skip to Body]
Primary: [Front Door] [Schedule] - [Academic Honesty] [Instructions]
Current: [Outline] [EBoard] [Reading] [Lab] - [Assignment]
Groupings: [Assignments] [EBoards] [Examples] [Exams] [Handouts] [Labs] [Outlines] [Projects] [Readings]
References: [A-Z] [By Topic] - [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [CSC151.02 2009S (Weinman)] [CSC151.02 2009S (Davis)] [CSC151 2008S (Rebelsky)]
Misc: [SamR] [MediaScript] [GIMP]

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Fri Dec 11 09:38:48 2009.
The source to the document was last modified on Fri Aug 21 17:03:06 2009.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2009F/Outlines/outline.39.html.

You may wish to validate this document's HTML ; ;

Samuel A. Rebelsky, rebelsky@grinnell.edu

Copyright © 2007-9 Janet Davis, Matthew Kluber, Samuel A. Rebelsky, and Jerod Weinman. (Selected materials copyright by John David Stone and Henry Walker and used by permission.) This material is based upon work partially supported by the National Science Foundation under Grant No. CCLI-0633090. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. This work is licensed under a Creative Commons Attribution-NonCommercial 2.5 License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc/2.5/ or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.