Computer Science 385
Design and Analysis of Algorithms

Spring 2017, Siena College

Home     Syllabus     Schedule

Agenda

• Announcements
  • If your group did not complete Lab 2: Introduction to METAL Graph Data, you may submit until the start of your lab meeting on January 31
  • Notice: the topic notes on the schedule page
• Lab 1 back
• Homework Set 1: [HTML] [PDF] out
• Asymptotic analysis (some should be review)
  • basic complexity ideas
  • basic efficiency classes
  • Big O, Big Ω, Big Θ

Terminology

• time vs. space tradeoff
• computational cost
• basic operation
• space cost
• trends
• asymptotic analysis
• Big O Big Ω, Big Θ
• relative rates of growth
• order of growth/complexity
• constant, logarithmic, linear, quadratic, cubic, polynomial, exponential, factorial
• best/worst/average case complexity
• basic efficiency classes