Computer Science 501
Data Structures and Algorithm Analysis

Fall 2015, The College of Saint Rose

Home     Syllabus     Schedule     Style Guide

Agenda

• Announcements
  • We are putting aside Submission Box as our submission mechnism for now and will use email for all submissions
• Lab 1: Java Refresher [HTML] [PDF] recap
• Lab 2: Practice with Vectors [HTML] [PDF] initial recap
• 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
• best/worst/average case complexity
• basic efficiency classes
• Big Ω, Big Θ

Examples

• EfficiencyClasses