Computer Science 210
Data Structures

Fall 2016, Siena College

Home     Syllabus     Schedule     Examples     Style Guide

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

Lecture 11 Assignment

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.

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

• EfficiencyClasses