33,59 €
Mehr erfahren.
- Herausgeber: Packt Publishing
- Kategorie: Fachliteratur
- Sprache: Englisch
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.
Das E-Book können Sie in Legimi-Apps oder einer beliebigen App lesen, die das folgende Format unterstützen:
Seitenzahl: 605
Veröffentlichungsjahr: 2022
Ähnliche
Hands-On Data Structures and Algorithms with Python
Third Edition
Store, manipulate, and access data effectively and boost the performance of your applications
Dr. Basant Agarwal
BIRMINGHAM—MUMBAI
“Python” and the Python Logo are trademarks of the Python Software Foundation.
Hands-On Data Structures and Algorithms with Python
Third Edition
Copyright © 2022 Packt Publishing
All rights reserved. No part of this book may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, without the prior written permission of the publisher, except in the case of brief quotations embedded in critical articles or reviews.
Every effort has been made in the preparation of this book to ensure the accuracy of the information presented. However, the information contained in this book is sold without warranty, either express or implied. Neither the author nor Packt Publishing or its dealers and distributors, will be held liable for any damages caused or alleged to have been caused directly or indirectly by this book.
Packt Publishing has endeavored to provide trademark information about all of the companies and products mentioned in this book by the appropriate use of capitals. However, Packt Publishing cannot guarantee the accuracy of this information.
Senior Publishing Product Manager: Denim Pinto
Acquisition Editor – Technical Reviews: Saby Dsilva
Project Editor: Rianna Rodrigues
Content Development Editor: Rebecca Robinson
Copy Editor: Safis Editing
Technical Editor: Karan Sonawane
Proofreader: Safis Editing
Indexer: Tejal Daruwale Soni
Presentation Designer: Ganesh Bhadwalkar
First published: May 2017
Second edition: October 2018
Third edition: July 2022
Production reference: 1150722
Published by Packt Publishing Ltd.
Livery Place
35 Livery Street
Birmingham
B3 2PB, UK.
ISBN 978-1-80107-344-8
www.packt.com
Contributors
About the author
Dr. Basant Agarwal is working as an Assistant Professor at the Department of Computer Science and Engineering, Indian Institute of Information Technology Kota (IIIT-Kota), India, which is an Institute of National Importance. He holds a Ph.D. and M.Tech. from the Department of Computer Science and Engineering, Malaviya National Institute of Technology Jaipur, India. He has more than 9 years of experience in research and teaching. He has worked as a Postdoc Research Fellow at the Norwegian University of Science and Technology (NTNU), Norway, under the prestigious European Research Consortium for Informatics and Mathematics (ERCIM) fellowship in 2016. He has also worked as a Research Scientist at Temasek Laboratories, National University of Singapore (NUS), Singapore. His research interests are in artificial intelligence, cyber-physical systems, text mining, natural language processing, machine learning, deep learning, intelligent systems, expert systems, and related areas.
This book is dedicated to my family, and friends.
Thank you to Benjamin Baka for his hard work in the first edition.
– Dr. Basant Agarwal
About the reviewers
Patrick Arminio is a software engineer based in London. He’s currently the chair of Python Italia, an association that organizes Python events in Italy.
He’s been working with Python for more than 10 years, focusing on web development using Django. He’s also the maintainer of Strawberry GraphQL, an open source Python library for creating GraphQL APIs.
Dong-hee Na is a software engineer and an open-source enthusiast. He works at Line Corporation as a backend engineer. He has professional experience in machine learning projects based on Python and C++. As for his open-source works, he focuses on the compiler and interpreter area, especially for Python-related projects. He has been a CPython core developer since 2020.
Join our community on Discord
Join our community’s Discord space for discussions with the author and other readers: https://packt.link/MEvK4
Contents
Preface
Who this book is for
What this book covers
To get the most out of this book
Get in touch
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
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
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
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
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
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
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
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
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
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
Sorting
Technical requirements
Sorting algorithms
Bubble sort algorithms
Insertion sort algorithm
Selection sort algorithm
Quicksort algorithm
Implementation of quicksort
Timsort algorithm
Summary
Exercise
Selection Algorithms
Technical requirements
Selection by sorting
Randomized selection
Quickselect
Deterministic selection
Implementation of the deterministic selection algorithm
Summary
Exercise
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: 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
Other Books You May Enjoy
Index
Landmarks
Cover
Index
Share your thoughts
Once you’ve read Hands-On Data Structures and Algorithms with Python - Third Edition, we’d love to hear your thoughts! Please clickheretogostraighttotheAmazonreviewpage for this book and share your feedback.
Your review is important to us and the tech community and will help us make sure we’re delivering excellent quality content.
