Python Data Structures and Algorithms

Cover
Title Page
Copyright
Credits
About the Author
About the Reviewer
www.PacktPub.com
Customer Feedback
Table of Contents
Preface
Chapter 1: Python Objects, Types, and Expressions
Understanding data structures and algorithms
Python for data
The Python environment
Variables and expressions
Variable scope
Flow control and iteration
Overview of data types and objects
Strings
Lists
Functions as first class objects
Higher order functions
Recursive functions
Generators and co-routines
Classes and object programming
Special methods
Inheritance
Data encapsulation and properties
Summary
Chapter 2: Python Data Types and Structures
Operations and expressions
Boolean operations
Comparison and Arithmetic operators
Membership, identity, and logical operations
Built-in data types
None type
Numeric Types
Representation error
Sequences
Tuples
Dictionaries
Sorting dictionaries
Dictionaries for text analysis
Sets
Immutable sets
Modules for data structures and algorithms
Collections
Deques
ChainMaps
Counter objects
Ordered dictionaries
defaultdict
Named tuples
Arrays
Summary
Chapter 3: Principles of Algorithm Design
Algorithm design paradigms
Recursion and backtracking
Backtracking
Divide and conquer - long multiplication
Can we do better? A recursive approach
Runtime analysis
Asymptotic analysis
Big O notation
Composing complexity classes
Omega notation (Ω)
Theta notation (ϴ)
Amortized analysis
Summary
Chapter 4: Lists and Pointer Structures
Arrays
Pointer structures
Nodes
Finding endpoints
Node
Other node types
Singly linked lists
Singly linked list class
Append operation
A faster append operation
Getting the size of the list
Improving list traversal
Deleting nodes
List search
Clearing a list
Doubly linked lists
A doubly linked list node
Doubly linked list
Append operation
Delete operation
List search
Circular lists
Appending elements
Deleting an element
Iterating through a circular list
Summary
Chapter 5: Stacks and Queues
Stacks
Stack implementation
Push operation
Pop operation
Peek
Bracket-matching application
Queues
List-based queue
Enqueue operation
Dequeue operation
Stack-based queue
Enqueue operation
Dequeue operation
Node-based queue
Queue class
Enqueue operation
Dequeue operation
Application of queues
Media player queue
Summary
Chapter 6: Trees
Terminology
Tree nodes
Binary trees
Binary search trees
Binary search tree implementation
Binary search tree operations
Finding the minimum and maximum nodes
Inserting nodes
Deleting nodes
Searching the tree
Tree traversal
Depth-first traversal
In-order traversal and infix notation
Pre-order traversal and prefix notation
Post-order traversal and postfix notation.
Breadth-first traversal
Benefits of a binary search tree
Expression trees
Parsing a reverse Polish expression
Balancing trees
Heaps
Summary
Chapter 7: Hashing and Symbol Tables
Hashing
Perfect hashing functions
Hash table
Putting elements
Getting elements
Testing the hash table
Using [] with the hash table
Non-string keys
Growing a hash table
Open addressing
Chaining
Symbol tables
Summary
Chapter 8: Graphs and Other Algorithms
Graphs
Directed and undirected graphs
Weighted graphs
Graph representation
Adjacency list
Adjacency matrix
Graph traversal
Breadth-first search
Depth-first search
Other useful graph methods
Priority queues and heaps
Inserting
Pop
Testing the heap
Selection algorithms
Summary
Chapter 9: Searching
Linear Search
Unordered linear search
Ordered linear search
Binary search
Interpolation search
Choosing a search algorithm
Summary
Chapter 10: Sorting
Sorting algorithms
Bubble sort
Insertion sort
Selection sort
Quick sort
List partitioning
Pivot selection
Implementation
Heap sort
Summary
Chapter 11: Selection Algorithms
Selection by sorting
Randomized selection
Quick select
Partition step
Deterministic selection
Pivot selection
Median of medians
Partitioning step
Summary
Chapter 12: Design Techniques and Strategies
Classification of algorithms
Classification by implementation
Recursion
Logical
Serial or parallel
Deterministic versus nondeterministic algorithms
Classification by complexity
Complexity curves
Classification by design
Divide and conquer
Dynamic programming
Greedy algorithms
Technical implementation
Dynamic programming
Memoization
Tabulation
The Fibonacci series
The Memoization technique
The tabulation technique
Divide and conquer
Divide
Conquer
Merge
Merge sort
Greedy algorithms
Coin-counting problem
Dijkstra's shortest path algorithm
Complexity classes
P versus NP
NP-Hard
NP-Complete
Summary
Chapter 13: Implementations, Applications, and Tools
Tools of the trade
Data preprocessing
Why process raw data?
Missing data
Feature scaling
Min-max scalar
Standard scalar
Binarizing data
Machine learning
Types of machine learning
Hello classifier
A supervised learning example
Gathering data
Bag of words
Prediction
An unsupervised learning example
K-means algorithm
Prediction
Data visualization
Bar chart
Multiple bar charts
Box plot
Pie chart
Bubble chart
Summary
Index