COSC 350: Data Structures
Feb. 13, 2009

Analysis of Algorithms Con't

Basic Recurences Relations

Look over these. They should give you some guidance in what to look for and what complexity is exhibited by different coding constructs.

Examples: search.py

Sequential search with unsorted data
Sequential search with sorted data
Binary search with sorted data

The three examples for the text are core algorithms that you should know. Be sure you know both the algorihms and there complexity.

Guarantees, Predictions, and Limitations

Know the differences and limitations associated with average-case and worse-case analysis.

Timing code using Python

For our first pass at emperical analysis of performace, we are using the time module. For example, to time spam(n) use something like:

import time
t1 = time.time()
spam(n)
t2 = time.time()
return t2 - t1

(Windows users may want to use time.clock() rather than time.time(). Feel free to experiment or look for more information on the Internet.) You'll probably want to run this several times and calculate the average.

Homework

Use time.time() from the module time to time both binary and sequential search for different size arrays of random numbers. For each size you select, make three runs and calculate the average. Use your numbers and plot the results. Email your code as an attachment and turn in your plot in class.

This page was created by Joe Sloan.
It was last modified around: 13 February 2009
Send mail to: sloanjd@wofford.edu