Python Data Structures and Algorithms

Description

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