book

Learning Algorithms

by George Heineman

August 2021

Intermediate to advanced

280 pages

7h 10m

English

O'Reilly Media, Inc.

Book available

Read now

Unlock full access

Includes

Includes Quizzes

Who This Book Is ForAbout the CodeConventions Used in This BookO’Reilly Online LearningHow to Contact UsAcknowledgments
What Is an Algorithm?Finding the Largest Value in an Arbitrary ListCounting Key OperationsModels Can Predict Algorithm PerformanceFind Two Largest Values in an Arbitrary ListTournament AlgorithmTime Complexity and Space ComplexitySummaryChallenge Exercises
Using Empirical Models to Predict PerformanceMultiplication Can Be FasterPerformance ClassesAsymptotic AnalysisCounting All OperationsCounting All BytesWhen One Door Closes, Another One OpensBinary Array SearchAlmost as Easy as πTwo Birds with One StonePulling It All TogetherCurve Fitting Versus Lower and Upper BoundsSummaryChallenge Exercises
Associating Values with KeysHash Functions and Hash CodesA Hashtable Structure for (Key, Value) PairsDetecting and Resolving Collisions with Linear ProbingSeparate Chaining with Linked ListsRemoving an Entry from a Linked ListEvaluationGrowing HashtablesAnalyzing the Performance of Dynamic HashtablesPerfect HashingIterate Over (key, value) PairsSummaryChallenge Exercises
Max Binary HeapsInserting a (value, priority)Removing the Value with Highest PriorityRepresenting a Binary Heap in an ArrayImplementation of Swim and SinkSummaryChallenge Exercises
Sorting by SwappingSelection SortAnatomy of a Quadratic Sorting AlgorithmAnalyze Performance of Insertion Sort and Selection SortRecursion and Divide and ConquerMerge SortQuicksortHeap SortPerformance Comparison of O(N log N) AlgorithmsTim SortSummaryChallenge Exercises
Getting StartedBinary Search TreesSearching for Values in a Binary Search TreeRemoving Values from a Binary Search TreeTraversing a Binary TreeAnalyzing Performance of Binary Search TreesSelf-Balancing Binary TreesAnalyzing Performance of Self-Balancing TreesUsing Binary Tree as (key, value) Symbol TableUsing the Binary Tree as a Priority QueueSummaryChallenge Exercises
Graphs Efficiently Store Useful InformationUsing Depth First Search to Solve a MazeBreadth First Search Offers Different Searching StrategyDirected GraphsGraphs with Edge WeightsDijkstra’s AlgorithmAll-Pairs Shortest PathFloyd–Warshall AlgorithmSummaryChallenge Exercises
Python Built-in Data TypesImplementing Stack in PythonImplementing Queues in PythonHeap and Priority Queue ImplementationsFuture Exploration

Content preview from Learning Algorithms

Preface

Who This Book Is For

If you are reading this book, I assume you already have a working knowledge of a programming language, such as Python. If you have never programmed before, I encourage you to first learn a programming language and then come back! I use Python in this book because it is accessible to programmers and nonprogrammers alike.

Algorithms are designed to solve common problems that arise frequently in software applications. When teaching algorithms to undergraduate students, I try to bridge the gap between the students’ background knowledge and the algorithm concepts I’m teaching. Many textbooks have carefully written—but always too brief—explanations. Without having a guide to explain how to navigate this material, students are often unable to learn algorithms on their own.

In one paragraph and in Figure P-1, let me show you my goal for the book. I introduce a number of data structures that explain how to organize information using primitive fixed-size types, such as 32-bit integer values or 64-bit floating point values. Some algorithms, such as Binary Array Search, work directly on data structures. More complicated algorithms, especially graph algorithms, rely on a number of fundamental abstract data types, which I introduce as needed, such as stacks or priority queues. These data types provide fundamental operations that can be efficiently implemented by choosing the right data structure. By the end of this book, you will understand how the various algorithms ...