COSC 350: Data Structures
Feb. 9, 2009

Today we began by going over the homework recaping the code from last time.

Next we talked about the complexity of the (first two) algorithms from Chapter 1. This lead into a discussion of complexit in general including:

Best, average, and worst case analysis.

Finding a measurement of problem size.

Finally, we looked at the problem of testing for anagrams as an example of the complexity of different approaches to the same problem. We analyzed five methods informally:

exhaustive: O(n!)
check-off: O(n*n)
sorting: O(n log n)
counting: O(n)
signature: O(n)

Homework

Continue reading Chapter 2 . Be sure to reread the Anagram code to make certain you understand it.

Anagram Code

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