Complexity and Performance

Lecture Slides Lecture Slides (pdf) Lecture Slides (ipynb)

Tutorial Exercise Tutorial Exercise (pdf) Tutorial Exercise (ipynb)

Getting the correct result and having well-structured and documented code are only two aspects of a good program. We also want our code to execute fast and, in some cases, for it to finish running in a moment, hour, day, year, lifetime… In this week we more formally discuss algorithmic complexity and performance. In addition to theoretical considerations we look into measuring execution time and benchmarking specific operations.

Required Readings

  • Guttag Chs 11: A Simplistic Introduction to Algorithmic Complexity, 12: Some Simple Algorithms and Data Structures;

Additional Readings

Tutorial

  • Benchmarking and measuring performance.