Topic 4. Algorithm and Abstraction

Lectures

  • Lecture 11. Big-O Notation

    Big-O notation is a powerful tool for reasoning about relative growth rates. This lecture explores how to use big-O notation to quantify growth rates and reason about how fast various algorithms work.

  • Lecture 12. Searching and Sorting, Part I

    Searching for an item in a data set is a very common operation, and sorting that data makes this a lot faster and easier. This lecture explores algorithms for doing these searches and start our exploration of how to sort a list of values.

    • Readings: Chapter 10.1 - 10.2

  • Lecture 13. Searching and Sorting, Part II

    This lecture explores the mergesort algorithm, hybrid sorting algorithms, and binary search.

    • Readings: Chapter 10.3 - 10.5

  • Lecture 14. Designing Abstractions

    Abstractions like lists, sets, and maps are key building blocks in complex software systems. This lecture explores how to invent and design your own.

  • Lecture 15. Implementing Abstractions, Part I

    The Vector, Map, Stack, and other related container types use a language feature called dynamic memory allocation to store their elements. This lecture explores how this is done, introducing pointers, constructors, and destructors in the process.

  • Lecture 16. Implementing Abstractions, Part II

    This lecture explores tradeoffs in how we allocate memory for a custom Stack type, concluding with an approach that’s widely used in practice.

Sections

Assignments