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

Chapter 9: Graphs and Algorithms

Question 1

What is the maximum number of edges (without self-loops) possible in an undirected simple graph with five nodes?

Solution

Each node can be connected to every other node in the graph. So, the first node can be connected to n-1 nodes, the second node can be connected to n-2 nodes, the third node can be connected to n-3 nodes, and so on. The total number of nodes will be:

[(n-1)+(n-2)+ … +3+2+1] = n(n-1)/2.

Question 2

What do we call a graph in which all the nodes have an equal degree?

Solution

A complete graph.

Question 3

Explain what cut vertices are and identify the cut vertices in the given graph?

Figure A.10: Sample graph

Solution

Cut vertices also known as articulation points. These are the vertices in the graph, after removal of which, the graph splits in two disconnected components. In the given graph, the vertices B, and C are cut vertices since after removal of node B...

Previous Section
End of Section
Next Section