Computer Science 431

Algorithms

Spring 2015, The College of Saint Rose

Agenda

- Announcements
- those who do not have accounts on
`mogul.strose.edu`should get one today - class code examples will be on
`mogul.strose.edu`in`/home/cs431/examples` - please be careful about which assignment name you choose when submitting items in submission box

- those who do not have accounts on
- Problem Set 1: Data Structures [HTML] [PDF] continues
- Lecture 2 assignment recap
- Fundamental data structures wrapup
- a bit about maps and dictionaries
- a look through the structure package structures

- Asymptotic analysis (some should be review)
- basic complexity ideas
- basic efficiency classes
- Big
*O* - Analyzing non-recursive algorithms

Due at the start of class, Monday, January 26.

Please submit answers to these questions in Submission Box under "LA3" or in hard copy by the start of our next class. We will discuss these questions at the start of class, so no late submissions are accepted. Please be sure that your name is clearly indicated in all submissions.

- Levitin Exercise 1.4.4, p. 37 (4 points).
- Levitin Exercise 2.1.1, p. 50 (6 points).
- Levitin Exercise 2.1.4, p. 51 (4 points).

Terminology

- time
*vs.*space tradeoff - computational cost
- basic operation
- space cost
- trends
- asymptotic analysis
- Big O
- relative rates of growth
- order of growth/complexity
- constant, logarithmic, linear, quadratic, cubic, polynomial, exponential, factorial
- best/worst/average case complexity
- basic efficiency classes

Examples

- EfficiencyClasses