J. Correia Lopes

FEUP/DEI & INESC TEC

User Tools

Site Tools


teach:fpro:lectures:16

T: 22/11/2018

Master in Informatics and Computing Engineering
Programming Fundamentals
Instance: 2018/2019


Lecture #16 :: 22/11/2018

Goals

By the end of this class, the student should be able to:

  • Describe why algorithm analysis is important
  • Use “Big-O” to describe execution time
  • Describe the “Big-O” execution time of common operations on Python lists and dictionaries

Content

  • What is Algorithm analysis.
    • Order of growth.
    • Big-O notation.
  • Performance of Python data structures
    • Lists
    • Dictionaries.

Bibliography

  • Allen Downey, Think Python — How to Think Like a Computer Scientist, 2nd Edition, Version 2.2.23, Green Tea Press, 2015 (Annex B) HTML or PDF

Materials

  • J. Correia Lopes, Script and illustrations, 16-analysis.pdf
  • FPRO, 2018/19, Python code, Lecture's on GitHub
  • Brad Miller and David Ranum, Problem Solving with Algorithms and Data Structures using Python (Section 5.3, Section 5.4) HTML
  • Brad Miller and David Ranum, Problem Solving with Algorithms and Data Structures using Python (Chapter 2) HTML

Summary

  • What is Algorithm analysis. Order of growth. Big-O notation. Performance of Python data structures: Lists, Dictionaries.

FPRO, 2018/19

« Previous | Index | Next »

teach/fpro/lectures/16.txt · Last modified: 21/11/2018 23:03 by Correia Lopes