Python Data Structures and Algorithms电子书

Title Page

Copyright

Credits

About the Author

About the Reviewer

www.PacktPub.com

Customer Feedback

Preface

What this book covers

What you need for this book

Who this book is for

Conventions

Reader feedback

Customer support

Downloading the example code

Errata

Piracy

Questions

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

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

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

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

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

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

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

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

Searching

Linear Search

Unordered linear search

Ordered linear search

Binary search

Interpolation search

Choosing a search algorithm

Summary

Sorting

Sorting algorithms

Bubble sort

Insertion sort

Selection sort

Quick sort

List partitioning

Pivot selection

Implementation

Heap sort

Summary

Selection Algorithms

Selection by sorting

Randomized selection

Quick select

Partition step

Deterministic selection

Pivot selection

Median of medians

Partitioning step

Summary

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

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