Computer Science 210

Data Structures

Fall 2016, Siena College

Agenda

- Announcements
- Exam 1 next Wednesday
- during lab sessions
- sample exam solutions will be posted outside my door
- review session, Tuesday 10/4, 7:30-9:00 in RB 340

- Lab 4:
`ArrayList`Practice continues - Lecture 09 assignment recap discussion
- Considering the costs of some
`Vector`/`ArrayList`methods - Complexity and asymptotic analysis

Due at the start of class, Monday, October 3.

Please submit answers to these questions in Blackboard under "Lecture 11 Assignment" by the start of class. We will discuss these questions at the start of class, so no late submissions can be accepted. Mostly, you want to be working on the practice exam and wrapping up the lab. But here are a couple questions to get you going on our current topic.

- Bailey Problem 5.2, p. 112. (4 points)
- Bailey Problem 5.5, p. 112. (3 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

Examples