Book Image

Hands-On Data Structures and Algorithms with Python - Third Edition

By : Dr. Basant Agarwal
Book Image

Hands-On Data Structures and Algorithms with Python - Third Edition

By: Dr. Basant Agarwal

Overview of this book

Choosing the right data structure is pivotal to optimizing the performance and scalability of applications. This new edition of Hands-On Data Structures and Algorithms with Python will expand your understanding of key structures, including stacks, queues, and lists, and also show you how to apply priority queues and heaps in applications. You’ll learn how to analyze and compare Python algorithms, and understand which algorithms should be used for a problem based on running time and computational complexity. You will also become confident organizing your code in a manageable, consistent, and scalable way, which will boost your productivity as a Python developer. By the end of this Python book, you’ll be able to manipulate the most important data structures and algorithms to more efficiently store, organize, and access data in your applications.

Related Content you might be interested in

Current Title:

Small book image
Hands-On Data Structures and Algorithms with Python - Third Edition
Dr. Basant Agarwal
Jul, 2022 | 496 pages
Small book image
Beginning Java Data Structures and Algorithms
James Cutajar
Jul, 2018 | 202 pages
Small book image
PHP 7 Data Structures and Algorithms
Mizanur Rahman
May, 2017 | 340 pages
Small book image
Java 9 Data Structures and Algorithms
Debasish Ray Chawdhuri
Apr, 2017 | 340 pages
Table of Contents (17 chapters)
Preface
Preface
Who this book is for
What this book covers
To get the most out of this book
Get in touch
Free Chapter
1
Python Data Types and Structures
Python Data Types and Structures
Introducing Python 3.10
Installing Python
Setting up a Python development environment
Overview of data types and objects
Basic data types
Complex data types
Python’s collections module
Summary
2
Introduction to Algorithm Design
Introduction to Algorithm Design
Introducing algorithms
Performance analysis of an algorithm
Asymptotic notation
Amortized analysis
Composing complexity classes
Computing the running time complexity of an algorithm
Summary
Exercises
3
Algorithm Design Techniques and Strategies
Algorithm Design Techniques and Strategies
Algorithm design techniques
Recursion
Divide and conquer
Dynamic programming
Greedy algorithms
Summary
Exercises
4
Linked Lists
Linked Lists
Arrays
Introducing linked lists
Singly linked lists
Doubly linked lists
Circular lists
Practical applications of linked lists
Summary
Exercise
5
Stacks and Queues
Stacks and Queues
Stacks
Queues
Summary
Exercises
6
Trees
Trees
Terminology
Binary trees
Binary search trees
Summary
Exercises
7
Heaps and Priority Queues
Heaps and Priority Queues
Heaps
Priority queues
Summary
Exercises
8
Hash Tables
Hash Tables
Introducing hash tables
Resolving collisions
Implementing hash tables
Symbol tables
Summary
Exercise
9
Graphs and Algorithms
Graphs and Algorithms
Graphs
Graph representations
Graph traversals
Other useful graph methods
Summary
Exercises
10
Searching
Searching
Introduction to searching
Linear search
Jump search
Binary search
Interpolation search
Exponential search
Choosing a search algorithm
Summary
Exercise
11
Sorting
Sorting
Technical requirements
Sorting algorithms
Bubble sort algorithms
Insertion sort algorithm
Selection sort algorithm
Quicksort algorithm
Implementation of quicksort
Timsort algorithm
Summary
Exercise
12
Selection Algorithms
Selection Algorithms
Technical requirements
Selection by sorting
Randomized selection
Deterministic selection
Summary
Exercise
13
String Matching Algorithms
String Matching Algorithms
Technical requirements
String notations and concepts
Pattern matching algorithms
The brute force algorithm
The Rabin-Karp algorithm
The Knuth-Morris-Pratt algorithm
The Boyer-Moore algorithm
Summary
Exercise
14
Other Books You May Enjoy
Other Books You May Enjoy
15
Index
Index
Appendix: Answers to the Questions
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

The Rabin-Karp algorithm

The Rabin-Karp pattern matching algorithm is an improved version of the brute force approach to find the location of the given pattern in the text string. The performance of the Rabin-Karp algorithm is improved by reducing the number of comparisons with the help of hashing. We discussed the concept of hashing in Chapter 8, Hash Tables. The hashing function returns a unique numeric value for a given string.

This algorithm is faster than the brute force approach as it avoids unnecessary comparisons. In this algorithm, we compare the hash value of the pattern with the hash value of the substring of the text string. If the hash values are not matched, the pattern is shifted forward one position. This is a better algorithm as compared to the brute-force algorithm since there is no need to compare all the characters of the pattern one by one.

This algorithm is based on the concept that if the hash values of the two strings are equal, then it is assumed...

Previous Section
End of Section 6
Next Section