Computer Science 210

Data Structures

Fall 2017, Siena College

Agenda

- Announcements
- reminder about lecture assignment grading criteria: full credit awarded does not necessarily mean completely correct responses

- Lab 3:
`ArrayList`Practice due Wednesday morning - Programming Project 2: Working with Highway Data, due a week from today.
- Exam 1 during labs Wednesday
- sample exam solutions are posted outside my door
- review session, Tuesday 10/3, 7:30-8:30 in RB 302
- 10% or 15% of course grade, depending on scores on subsequent exams

- Considering the costs of some
`Vector`/`ArrayList`methods - Complexity and asymptotic analysis

Due at the start of class, Friday, October 6.

Please submit answers to these questions in Blackboard under "Lecture 12 Assignment" by the start of class. We will discuss these questions at the start of class, so no late submissions can be accepted.

- Bailey Problem 5.2, p. 112. See the implementation of
this method in the
`Vector`class in structure5. (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