Data Structures and Algorithms in Python

Python Primer

• Python Overview
• Objects in Python
• Expressions, Operators, and Precedence
• Control Flow
• Functions
• Simple Input and Output
• Exception Handling
• Iterators and Generators
• Additional Python Conveniences
• Scopes and Namespaces
• Modules and the Import Statement
• Exercises

Object-Oriented Programming

• Goals, Principles, and Patterns
• Software Development
• Class Definitions
• Inheritance
• Namespaces and Object-Orientation
• Shallow and Deep Copying
• Exercises

Algorithm Analysis

• Experimental Studies
• The Seven Functions Used in This Course
• Asymptotic Analysis
• Simple Justification Techniques
• Exercises

Recursion

• Illustrative Examples
• Analyzing Recursive Algorithms
• Recursion Run Amok
• Further Examples of Recursion
• Designing Recursive Algorithms
• Eliminating Tail Recursion
• Exercises

Array-Based Sequences

• Python's Sequence Types
• Low-Level Arrays
• Dynamic Arrays and Amortization
• Efficiency of Python's Sequence Types
• Using Array-Based Sequences
• Multidimensional Data Sets
• Exercises

Stacks, Queues, and Deques

• Stacks
• Queues
• Double-Ended Queues
• Exercises

Linked Lists

• Singly Linked Lists
• Circularly Linked Lists
• Doubly Linked Lists
• The Positional List ADT
• Sorting a Positional List
• Case Study: Maintaining Access Frequencies
• Link-Based vs. Array-Based Sequences
• Exercises

Trees

• General Trees
• Binary Trees
• Implementing Trees
• Tree Traversal Algorithms
• Case Study: An Expression Tree
• Exercises

Priority Queues

• The Priority Queue Abstract Data Type
• Implementing a Priority Queue
• Heaps
• Sorting with a Priority Queue
• Adaptable Priority Queues
• Exercises

Maps, Hash Tables, and Skip Lists

• Maps and Dictionaries
• Hash Tables
• Sorted Maps
• Skip Lists
• Sets, Multisets, and Multimaps
• Exercises

Search Trees

• Binary Search Trees
• Balanced Search Trees
• AVL Trees
• Splay Trees
• (2,4) Trees
• Red-Black Trees
• Exercises

Sorting and Selection

• Why Study Sorting Algorithms?
• Merge-Sort
• Quick-Sort
• Studying Sorting through an Algorithmic Lens
• Comparing Sorting Algorithms
• Python's Built-In Sorting Functions
• Selection
• Exercises

Text Processing

• Abundance of Digitized Text
• Pattern-Matching Algorithms
• Dynamic Programming
• Text Compression and the Greedy Method
• Tries
• Exercises

Graph Algorithms

• Graphs
• Data Structures for Graphs
• Graph Traversals
• Transitive Closure
• Directed Acyclic Graphs
• Shortest Paths
• Minimum Spanning Trees
• Exercises

Memory Management and B-Trees

• Memory Management
• Memory Hierarchies and Caching
• External Searching and B-Trees
• External-Memory Sorting
• Exercises

Appendix A: Character Strings in Python

Appendix B: Useful Mathematical Facts