Runtime Analysis

Characterize Performance with Experiments

Exploration

• Read chapter 5 of A First Course on Data Structures in Python
• Experimentally evaluate performance of algorithms, data structures, and systems in the ds2 package of donsheehy/datastructures
• Note that next week’s focus will also be on running time analysis!

Activities

• Monday and Wednesday: Empirical Evaluation
  • Understand why program performance is critically important
  • Characterize performance patterns in Python programs
  • Use experimentation to characterize performance trade-offs
  • Prepare for using asymptotic analysis to characterize performance
  • Examine source code segments to illustrate key points
• Thursday: Continue algorithm engineering project
• Friday: Presentations during algorithm all-hands session

Project

Goal

To build and use a Python program, called objectprocessing, that runs benchmarks to study the performance of storing and searching for objects using three different ways for determining whether or not a search term matches the value in an object’s attributes.

Steps

• Use Object Processing as your template repository
• Install the project’s dependencies using devenv
• Follow the instructions to complete the project:
  • Week 1: Implement all of the modules in objectprocessing
  • Week 2: Design and conduct experiments and document experimental results
• Schedule office hours if you have questions

Slides

Full Screen: Week Five: Runtime Analysis through Experimental Evaluation