Computer Science 501
Data Structures and Algorithm Analysis

Fall 2014, The College of Saint Rose

Home     Syllabus     Schedule     Style Guide

Agenda

• Announcements
• Lab 1: Conway's Day of the Week Calculator [HTML] [PDF] recap
• Lab 2: Practice with Vectors [HTML] [PDF] recap
• Those not familiar with generic data structures, please read the topic notes and Bailey Ch. 4. We will start using the generic versions of the data structures in the structure package, but this will not be a topic we cover in class.
• Costs of Vector operations
• Asymptotic analysis
  • finding trends
  • Big O
  • common orders of growth
  • best/worst/average cases
• Basic efficiency classes
• Lab 3: Timing Java [HTML] [PDF] out

Readings and References

• Bailey Ch. 5

Terminology

• time vs. space tradeoff
• computational cost
• space cost
• trends
• asymptotic analysis
• relative rates of growth of functions
• common orders of growth: constant, logarithmic, linear, quadratic, cubic, poynomial, exponential, factorial

Examples

• EfficiencyClasses