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

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