Data Structures and Information Retrieval in Python
Introduction — Data Structures and Information Retrieval in Python

Introduction#
Data Structures and Information Retrieval in Python is an introduction to data structures and algorithms using a web search engine as a motivating example.
It is based in part on Think Data Structures, which uses Java.
The elements of the search engine are:

The Crawler, which downloads web pages and follows links to other pages,
The Indexer, which builds a map from each search term to the pages where it appears, and
The Retriever, which looks up search terms and finds relevant, high-quality pages.

The index is stored in Redis, which is a data store that provides structures like sets, lists, and hashmaps. The book presents each data structure first in Python, then in Redis, which should help readers see which features are essential and which are implementation details.
As I did with Think Bayes, I wrote this book entirely in Jupyter notebooks, and used JupyterBook to translate them to HTML. The notebooks run on Colab, which is a service provided by Google that runs notebooks in a browser. So you can read the book, run the code, and work on exercises without installing anything.
This material is a work in progress, so your feedback is welcome.  The best way to provide that feedback is to click here and create an issue in this GitHub repository.
Overview slides

The notebooks#
Click on the links below to run the notebooks on Colab.

Algorithms: Day One activity checking for anagrams and finding anagram sets.
Notebook
Analysis: Introduction to the analysis of algorithms and Big O notation.
Slides
Notebook
Timing: Checking asymptotic behavior by measuring run time.
Notebook
Quiz 1
Notebook
Generator functions: Separate the iteration from the program logic
Slides
Notebook
Set: Using Python sets to cheat at word games.
Notebook
Recursion: Practice recursive functions.
Notebook
Quiz 2
Notebook
Depth First Search: Tree traversal in BeautifulSoup.
Slides
Notebook
Search: Linear search, bisection, and binary search trees.
Slides
Notebook
Hashmap: How the greatest of all data structures works.
Slides
Notebook
Quiz 3
Notebook
Heap: It’s an array, it’s a tree, it’s a PriorityQueue!
Slides
Notebook
Huffman Code: Use the structures we’ve learned to make an optimal prefix code.
Slides
Notebook
Getting to Philosophy: Follow Wikipedia links until you get to Philosophy.
Slides
Notebook
Quiz 4
Notebook
Redis: Introduction to the Redis data store.
Notebook
Linked List: Trees before lists? Strange but true.
Slides
Notebook
Indexer: Make a map of the internet for fast lookups.
Notebook
Quiz 5
Notebook
Deque: Like a linked list, but more so.
Notebook
Graphs: Representing graphs with NetworkX.
Notebook
Level Order Search: Use the os module to traverse a file system.
Slides
Notebook
Breadth-First Search: The foundation of graph algorithms.
Slides
Notebook
Quiz 6
Notebook
Crawler: Follow links and breadth-first search the internet.
Notebook
Mergesort: Divide, conquer, and merge in linearithmic time.
Slides
Notebook
Fast Fourier Transform: It’s like mergesort, but with complex numbers.
Slides
Notebook
Quiz 7
Notebook
PageRank: Random walks, adjacency matrices, and eigenvectors!
Slides
Notebook

Copyright 2021 Allen B. Downey
License: Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)


