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

Content preview from Hands-On Data Structures and Algorithms with Python - Third Edition

13 String Matching Algorithms

There are many popular string matching algorithms. String matching algorithms have very important applications, such as searching for an element in a text document, plagiarism detection, text editing programs, and so on. In this chapter, we will study the pattern matching algorithms that find the locations of a given pattern or substring in any given text. We will discuss the brute force algorithm, along with the Rabin-Karp, Knuth-Morris-Pratt (KMP), and Boyer-Moore pattern matching algorithms. This chapter aims to discuss algorithms that are related to strings. The following topics will be covered in this chapter: