Hands-On Data Structures and Algorithms with Python: Store, manipulate, and access data effectively, 3rd Edition

Description

Understand how implementing different data structures and algorithms intelligently can make your Python code and applications more maintainable and efficient Key Features Explore functional and reactive implementations of traditional and advanced data structures Apply a diverse range of algorithms in your Python code Implement the skills you have learned to maximize the performance of your applications Cover CopyRight Contributors Table of Contents Preface Chapter 1: Python Data Types and Structures Introducing Python 3.10 Installing Python Windows operating system Linux-based operating systems Mac operating system Setting up a Python development environment Setup via the command line Setup via Jupyter Notebook Overview of data types and objects Basic data types Numeric Boolean Sequences Strings Range Lists Membership, identity, and logical operations Membership operators Identity operators Logical operators Tuples Complex data types Dictionaries Sets Immutable sets Python’s collections module Named tuples Deque Ordered dictionaries Default dictionary ChainMap object Counter objects UserDict UserList UserString Summary Chapter 2: Introduction to Algorithm Design Introducing algorithms Performance analysis of an algorithm Time complexity Space complexity Asymptotic notation Theta notation Big O notation Omega notation Amortized analysis Composing complexity classes Computing the running time complexity of an algorithm Summary Exercises Chapter 3: Algorithm Design Techniques and Strategies Algorithm design techniques Recursion Divide and conquer Binary search Merge sort Dynamic programming Calculating the Fibonacci series Greedy algorithms Shortest path problem Summary Exercises Chapter 4: Linked Lists Arrays Introducing linked lists Nodes and pointers Singly linked lists Creating and traversing Improving list creation and traversal Appending items Appending items to the end of a list Appending items at intermediate positions Querying a list Searching an element in a list Getting the size of the list Deleting items Deleting the node at the beginning of the singly linked list Deleting the node at the end in the singly linked list Deleting any intermediate node in a singly linked list Clearing a list Doubly linked lists Creating and traversing Appending items Inserting a node at beginning of the list Inserting a node at the end of the list Inserting a node at an intermediate position in the list Querying a list Deleting items Circular lists Creating and traversing Appending items Querying a list Deleting an element in a circular list Practical applications of linked lists Summary Exercise Chapter 5: Stacks and Queues Stacks Stack implementation using arrays Stack implementation using linked lists Push operation Pop operation Peek operation Applications of stacks Queues Python’s list-based queues The enqueue operation The dequeue operation Linked list based queues The enqueue operation The dequeue operation Stack-based queues Approach 1: When the dequeue operation is costly Approach 2: When the enqueue operation is costly Enqueue operation Dequeue operation Applications of queues Summary Exercises Chapter 6: Trees Terminology Binary trees Implementation of tree nodes Tree traversal In-order traversal Pre-order traversal Post-order traversal Level-order traversal Expression trees Parsing a reverse Polish expression Binary search trees Binary search tree operations Inserting nodes Searching the tree Deleting nodes Finding the minimum and maximum nodes Benefits of a binary search tree Summary Exercises Chapter 7: Heaps and Priority Queues Heaps Insert operation Delete operation Deleting an element at a specific location from a heap Heap sort Priority queues Summary Exercises Chapter 8: Hash Tables Introducing hash tables Hashing functions Perfect hashing functions Resolving collisions Open addressing Linear probing Implementing hash tables Storing elements in a hash table Growing a hash table Retrieving elements from the hash table Testing the hash table Implementing a hash table as a dictionary Quadratic probing Double hashing Separate chaining Symbol tables Summary Exercise Chapter 9: Graphs and Algorithms Graphs Directed and undirected graphs Directed acyclic graphs Weighted graphs Bipartite graphs Graph representations Adjacency lists Adjacency matrix Graph traversals Breadth-first traversal Depth-first search Other useful graph methods Minimum Spanning Tree Kruskal’s Minimum Spanning Tree algorithm Prim’s Minimum Spanning Tree algorithm Summary Exercises Chapter 10: Searching Introduction to searching Linear search Unordered linear search Ordered linear search Jump search Binary search Interpolation search Exponential search Choosing a search algorithm Summary Exercise Chapter 11: Sorting Technical requirements Sorting algorithms Bubble sort algorithms Insertion sort algorithm Selection sort algorithm Quicksort algorithm Implementation of quicksort Timsort algorithm Summary Exercise Chapter 12: Selection Algorithms Technical requirements Selection by sorting Randomized selection Quickselect Deterministic selection Implementation of the deterministic selection algorithm Summary Exercise Chapter 13: String Matching Algorithms Technical requirements String notations and concepts Pattern matching algorithms The brute force algorithm The Rabin-Karp algorithm Implementing the Rabin-Karp algorithm The Knuth-Morris-Pratt algorithm The prefix function Understanding the KMP algorithm Implementing the KMP algorithm The Boyer-Moore algorithm Understanding the Boyer-Moore algorithm Bad character heuristic Good suffix heuristic Implementing the Boyer-Moore algorithm Summary Exercise Appendix Chapter 2: Introduction to Algorithm Design Chapter 3: Algorithm Design Techniques and Strategies Chapter 4: Linked Lists Chapter 5: Stacks and Queues Chapter 6: Trees Chapter 7: Heaps and Priority Queues Chapter 8: Hash Tables Chapter 9: Graphs and Algorithms Chapter 10: Searching Chapter 11: Sorting Chapter 12: Selection Algorithm Chapter 13: String Matching Algorithms PacktPage Other Books You May Enjoy Index