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

12 Selection Algorithms

One interesting set of algorithms related to finding elements in an unordered list of items is selection algorithms. Given a list of elements, selection algorithms are used to find the k^th smallest or largest element from the list. So given a list of data elements and a number (k), the aim is to find the k^th smallest or largest element. The simplest case of selection algorithms is to find the minimum or maximum data element from the list. However, sometimes, we may need to find the k^th smallest or largest element in the list. The simplest way is to first sort the list using any sorting algorithm, and then we can easily obtain the k^th smallest (or largest) element. However, when the list is very large, then it is not efficient ...