book

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

by Dr. Basant Agarwal

July 2022

Intermediate to advanced

496 pages

11h 18m

English

Packt Publishing

Read now

Unlock full access

Who this book is forWhat this book coversTo get the most out of this bookGet in touch
Introducing Python 3.10Installing PythonWindows operating systemLinux-based operating systemsMac operating systemSetting up a Python development environmentSetup via the command lineSetup via Jupyter NotebookOverview of data types and objectsBasic data typesNumericBooleanSequencesStringsRangeListsMembership, identity, and logical operationsMembership operatorsIdentity operatorsLogical operatorsTuplesComplex data typesDictionariesSetsImmutable setsPython’s collections moduleNamed tuplesDequeOrdered dictionariesDefault dictionaryChainMap objectCounter objectsUserDictUserListUserStringSummary
Introducing algorithmsPerformance analysis of an algorithmTime complexitySpace complexityAsymptotic notationTheta notationBig O notationOmega notationAmortized analysisComposing complexity classesComputing the running time complexity of an algorithmSummaryExercises
Algorithm design techniquesRecursionDivide and conquerBinary searchMerge sortDynamic programmingCalculating the Fibonacci seriesGreedy algorithmsShortest path problemSummaryExercises
ArraysIntroducing linked listsNodes and pointersSingly linked listsCreating and traversingImproving list creation and traversalAppending itemsAppending items to the end of a listAppending items at intermediate positionsQuerying a listSearching an element in a listGetting the size of the listDeleting itemsDeleting the node at the beginning of the singly linked listDeleting the node at the end in the singly linked listDeleting any intermediate node in a singly linked listClearing a listDoubly linked listsCreating and traversingAppending itemsInserting a node at beginning of the listInserting a node at the end of the listInserting a node at an intermediate position in the listQuerying a listDeleting itemsCircular listsCreating and traversingAppending itemsQuerying a listDeleting an element in a circular listPractical applications of linked listsSummaryExercise
StacksStack implementation using arraysStack implementation using linked listsPush operationPop operationPeek operationApplications of stacksQueuesPython’s list-based queuesThe enqueue operationThe dequeue operationLinked list based queuesThe enqueue operationThe dequeue operationStack-based queuesApproach 1: When the dequeue operation is costlyApproach 2: When the enqueue operation is costlyEnqueue operationDequeue operationApplications of queuesSummaryExercises
TerminologyBinary treesImplementation of tree nodesTree traversalIn-order traversalPre-order traversalPost-order traversalLevel-order traversalExpression treesParsing a reverse Polish expressionBinary search treesBinary search tree operationsInserting nodesSearching the treeDeleting nodesFinding the minimum and maximum nodesBenefits of a binary search treeSummaryExercises
HeapsInsert operationDelete operationDeleting an element at a specific location from a heapHeap sortPriority queuesSummaryExercises
Introducing hash tablesHashing functionsPerfect hashing functionsResolving collisionsOpen addressingLinear probingImplementing hash tablesStoring elements in a hash tableGrowing a hash tableRetrieving elements from the hash tableTesting the hash tableImplementing a hash table as a dictionaryQuadratic probingDouble hashingSeparate chainingSymbol tablesSummaryExercise
GraphsDirected and undirected graphsDirected acyclic graphsWeighted graphsBipartite graphsGraph representationsAdjacency listsAdjacency matrixGraph traversalsBreadth-first traversalDepth-first searchOther useful graph methodsMinimum Spanning TreeKruskal’s Minimum Spanning Tree algorithmPrim’s Minimum Spanning Tree algorithmSummaryExercises

Introduction to searchingLinear searchUnordered linear searchOrdered linear searchJump searchBinary searchInterpolation searchExponential searchChoosing a search algorithmSummaryExercise
Technical requirementsSorting algorithmsBubble sort algorithmsInsertion sort algorithmSelection sort algorithmQuicksort algorithmImplementation of quicksortTimsort algorithmSummaryExercise
Technical requirementsSelection by sortingRandomized selectionQuickselectDeterministic selectionImplementation of the deterministic selection algorithmSummaryExercise
Technical requirementsString notations and conceptsPattern matching algorithmsThe brute force algorithmThe Rabin-Karp algorithmImplementing the Rabin-Karp algorithmThe Knuth-Morris-Pratt algorithmThe prefix functionUnderstanding the KMP algorithmImplementing the KMP algorithmThe Boyer-Moore algorithmUnderstanding the Boyer-Moore algorithmBad character heuristicGood suffix heuristicImplementing the Boyer-Moore algorithmSummaryExercise
Chapter 2: Introduction to Algorithm DesignChapter 3: Algorithm Design Techniques and StrategiesChapter 4: Linked ListsChapter 5: Stacks and QueuesChapter 6: TreesChapter 7: Heaps and Priority QueuesChapter 8: Hash TablesChapter 9: Graphs and AlgorithmsChapter 10: SearchingChapter 11: SortingChapter 12: Selection AlgorithmChapter 13: String Matching Algorithms

Overview

This book provides a practical and in-depth look at the core issues surrounding data structures and algorithms in Python. By reading it, you'll understand how to effectively implement and utilize various data structures, analyze algorithm efficiency, and enhance the performance of your Python applications.

What this Book will help me do

Understand the use and implementation of stacks, queues, lists, and other essential data structures.
Analyze the performance of algorithms in terms of computational complexity.
Learn dynamic programming techniques and algorithmic paradigms to solve problems efficiently.
Effectively use complex structures like heaps and priority queues in Python.
Apply various algorithms, from sorting to string-matching, in real-world scenarios.

Author(s)

Dr. Basant Agarwal is an experienced author and computer science educator with a background in teaching and a passion for making technical topics accessible. His expertise in Python and algorithms makes this book a valuable resource for learners.

Who is it for?

This book is ideal for developers and programmers with a basic understanding of Python. If you're looking to deepen your knowledge in data structures and algorithms, this book provides the practical steps needed. Whether you're building foundational skills or advancing your technical abilities, this book is tailored to help you. It's perfect for anyone looking to write high-performance Python applications with efficient algorithms.