Complexity

In this assignment you’ll learn all about efficient code and how to make your own code more efficient. Specifically we’ll introduce the big O notation, which can be used to describe how efficient some piece of code is, and we’ll cover some Python data structures that’ll help make your code more efficient.

These data structures, like dictionaries and sets, can be very useful when writing code in general, but they really shine when making code more efficient. To highlight this, we’ll also show an example of how code can be made more efficient using these structures.

For the assignment, you’ll have to write an indexing system that can search through book texts to find specific words. This program will have to search through large collections of text fast, so it should also be efficient.

Part 1: Learn about computational complexity

  1. Learn about efficient code: efficiency

  2. Assignment Get started with Jupyter notebooks: notebook

Part 2: Data structures and their efficiency

  1. Learn about dictionaries: dictionaries

  2. Learn about tuples: tuples

  3. Learn about sets: sets

  4. Learn about list slicing and indexing: slicing

Part 3: How to write efficient code

  1. Apply big O in your own code: application

  2. Improving the count_occurrence() function: example

Part 4: Write your own efficient code

  1. Assignment Indexing words (assignment): word-index

  2. Assignment Indexing pairs (assignment): pair-index

Submitting

Submit your code.