This book is the first in a four-volume series and is based on the author’s online algorithms course, which is rated 4.7 at Aia. The online course, which has been updated regularly since 2012, builds on an undergraduate course the author taught for many years at Stanford university. As you may have heard, this book is called “Algorithms in Detail (Volume 1) — Fundamentals of Algorithms”. If you prefer listening and watching, you can search for the book’s thematic lessons on YouTube to watch for free.
Asynchronous book public account background reply: “algorithm details”, obtain the video address.
Tim Roughgarden is a professor in the Computer Science Department at Stanford University, where he is a visiting professor of management science and Engineering. He has been teaching and researching algorithms since 2004. This is the first volume of his tetralogy, “The Details of Algorithms”.
This book explains the basics of algorithms in detail, show the essence of algorithms, is a comprehensive guide to the basic knowledge of algorithms. Set Stanford university professor years of teaching experience, simple, easy to understand.
Detailed Explanation of Algorithms (Volume 1) — Fundamentals of Algorithms
By Cory Althoff
Scan the QR code and buy with one click
The following four topics are introduced in this book.
Progressive analysis and large O notation
Progressive notation provides the basic terminology for discussing the design and analysis of algorithms. The key concept is the big O notation, a modeling choice for measuring the runtime granularity of an algorithm. As we will see, one of the advantages of a clean high-level algorithm design is that you can ignore constant factors and low-order terms and focus on the relationship between algorithm performance and input length.
Divide-and-conquer algorithm and master method
There is no universal shortcut in algorithm design, there is no one way to solve all computing problems. However, there are some general algorithm design techniques that can be applied to a range of different domains. In volume 1 of this series, we will discuss the “divide and conquer” technique. The idea of divide-and-conquer is to break a problem into smaller sub-problems, then recursively solve those sub-problems and quickly combine their solutions together to form a solution to the original problem. We will discuss fast divide-and-conquer algorithms for sorting, integer multiplication, matrix multiplication, and basic computational geometry problems. We’ll also discuss the master method, which is a powerful tool for analyzing the running time of divide-and-conquer algorithms.
Randomization algorithm
The randomization algorithm operates in the way of “coin toss”, and its behavior depends on the result of coin toss. Surprisingly, randomization often leads to simple, elegant, and practical algorithms. One classic example is the randomized QuickSort algorithm, which we’ll look at in detail and examine its running time. We will see further applications of randomization in volume 2 of the Algorithms in Detail series.
Sorting and selection
As an addition to the previous three topics, we’ll learn about several well-known sorting and selection algorithms, including MergeSort, quicksort, and linear time-level selection (both randomized and deterministic versions). These algorithms are so dizzyingly fast that they don’t run much longer than the time it takes to read the input. Create a set of “low-cost basic operations” like this, which can be used either directly to manipulate data or as a basic unit for solving more difficult problems.
For a more detailed introduction to the contents of this book, read the chapter Highlights, which summarize the content of each chapter, especially the important concepts.
Topics covered in other volumes of the Algorithm in Detail series
Algorithms in Detail (Volume 2) discusses data structures (heaps, balanced search trees, hash tables, Bloat filters), basic units of graphics (width and depth first search, connectivity, shortest paths), and their applications (from eliminating duplication to social network analysis). Volume 3 focuses on greedy algorithms (scheduling, minimum spanning tree, clustering, Huffman coding) and dynamic programming (knapsack, sequence alignment, shortest path, optimal search tree, etc.). Volume 4 introduces NP integrity and its significance to algorithm designers. It also discusses some strategies for solving difficult computational problems, including the analysis of heuristics and local search.
This book is often written with “Q.E.D”. It is short for quod erat demonstrandum. In mathematical works, it appears at the end of the proof process to indicate that the proof has been completed.
Mastering algorithms takes a lot of time and effort, so why learn algorithms?
Become a better programmer
Readers will learn about some mind-blowing high-speed subroutines for processing data and some useful data structures that organize data and can be deployed directly into their own programs. Implementing and using these algorithms will expand and improve your programming skills. Readers will also learn basic algorithm design paradigms that are closely related to different problems in many different domains and can be used as tools to predict algorithm performance. These “algorithm design patterns” help readers design new algorithms for their own problems.
Strengthen analytical skills
The reader will be given plenty of practice to describe and derive the algorithm. Through mathematical analysis, readers will gain a deep understanding of the specific algorithms and data structures covered in the Algorithms in Detail series. Readers will also learn some practical mathematical techniques that are widely used in algorithmic analysis.
Forming algorithmic thinking
After learning the algorithms, it’s hard to find a place where they’re not present. Whether it’s riding an elevator, watching a flock of birds, managing your own portfolio, or even observing a baby’s cognition, algorithmic thinking goes with it. Algorithmic thinking is increasingly useful in fields outside computer science, including biology, statistics and economics.
Blend in with computer scientists
Studying algorithms is like watching a highlight reel from the last 60 years of computer science. When a reader attends a computer science cocktail party and someone tells a joke about Dijkstra’s algorithm, you won’t feel left out of the loop. After reading this series, the reader will know a lot about this topic.
Stand out in technical interviews
Over the years, many students have told me how the Algorithm Books have helped them excel in technical interviews.
The Detailed Algorithms series is currently available on Coursera and Stanford Lagunita. There are also resources to help readers enhance the online experience according to their own wishes.
- Video. If you prefer listening and watching to reading, you can watch it on YouTube playlists. These videos cover all the topics in the Algorithm In Detail series. I hope they inspire a continuing enthusiasm for learning algorithms. Of course, they can’t replace books completely.
- Quiz. How do you know if you fully understand the concepts discussed in this book? Quizzes dotted throughout the book, with their answers and detailed explanations, do just that. When the reader gets to this point, it’s best to stop and think about it before moving on.
- Problem set at the end of chapter. At the end of each chapter are relatively simple questions designed to test the reader’s understanding of the chapter. There are also open-ended, more difficult challenges. The book does not contain the answers to the problem sets at the end of the chapter, but readers can communicate with me and other readers through the book’s forum (described later).
- Programming problem. Many of the chapters end with a suggested programming project that aims to develop a complete understanding of algorithms by creating their own working procedures for algorithms. Data sets, test cases, and their answers can be found at www.algorithmsi- lluminated.org.
- BBS. An important reason for the success of online courses is that they provide an opportunity for participants to help each other, through forums where readers can discuss course materials and debug procedures. Book series of the readers have the same chance, you can participate in the interaction through www.algorithmsilluminated.org.
Chapter 1 Introduction 1
1.1 Why learn Algorithm 1
1.2 Integer multiplication by 3
1.2.1 Problems and Solutions 3
Problem 3 of integer multiplication
1.2.3 Primary school Algorithm 4
1.2.4 Analysis of number of operations 5
1.2.5 Can WE do better
1.3 Karatsuba multiplication 6
1.3.1 A specific example 6
1.3.2 A recursive algorithm 7
1.3.3 Karatsuba multiplication 9
1.4 MergeSort algorithm 11
1.4.1 Impetus 11
1.4.2 ordering 12
1.4.3 An Example 13
1.4.4 pseudo-code 14
1.4.5 Merge subprogram 15
1.5 MergeSort algorithm analysis 16
1.5.1 Runtime of Merge 17
1.5.2 MergeSort run time 18
1.5.3 Proof of Theorem 1.2 19
1.5.4 Answers from Quizzes 1.1 to 1.2 23
1.6 Guidelines for Algorithm Analysis 23
1.6.1 Principle 1: Worst-case Analysis 24
1.6.2 Principle 2: Global analysis 25
1.6.3 Principle 3: Progressive analysis 26
1.6.4 What is the “Fast” algorithm 27
1.7 Point 28 of this chapter
1.8 problem sets 29
Challenge question 31
Programming question 31
Chapter 2 Progressive Representation 32
2.1 the gist of 32
2.1.1 Impetus 32
2.1.2 Advanced Thinking 33
2.1.3 4 Examples 34
2.1.4 Answers to quizzes 2.1 to 2.4 38
2.2 Big O representation 40
2.2.1 Text Definition 40
2.2.2 Graph Definition 40
2.2.3 Mathematical Definition 41
2.3 Two basic Examples 42
The polynomial of order K is O(NK) 42
The polynomial of order K is not O(NK-1) 43
2.4 large ω and large notation 44
2.4.1 Large ω representation 44
2.4.2 large notation 45
2.4.3 Small O notation 46
2.4.4 Sources of progressive representation 47
2.4.5 Answer to Quiz 2.5 48
2.5 Other Examples 48
2.5.1 Add a constant 48 to the index
2.5.2 Exponential times a constant 49
2.5.3 Maximum vs. 49
2.6 Point 50 of this chapter
2.7 problem sets 51
Chapter 3 Divide-and-conquer algorithm
3.1 Divide-and-conquer specification 53
3.2 Count in O(n log n) time reverse to 54
3.2.1 question 54
3.2.2 An example 54
3.2.3 Collaborative screening 55
3.2.4 Exhaustive search 55
3.2.5 Divide-and-conquer 56
3.2.6 Advanced Algorithms 57
3.2.7 Key idea: Stand on the shoulders of MergeSort 57
3.2.8 Review Merge 58
3.2.9 Merge and separation reverse order to 60
3.2.10 Merge_and_CountSplitInv 61
3.2.11 Correctness 61
3.2.12 Running time 62
3.2.13 Answers to quizzes 3.1 to 3.2 62
Strassen’s matrix multiplication algorithm 63
3.3.1 Matrix Multiplication 63
3.3.2 Example (n = 2) 64
3.3.3 Simple Algorithm 64
3.3.4 Divide-and-conquer 65
3.3.5 Save a recursive call 67
3.3.6 details 68
3.3.7 Answer 69 to Quiz 3.3
Closest Pair 70
3.4.1 track question 70
3.4.2 Warm-up: 1D condition 71
3.4.3 Pretreatment 71
3.4.4 A divide-and-conquer method 72
3.4.5 A Subtle change 74
3.4.6 ClosestSplitPair 74
3.4.7 Correctness 76
3.4.8 Proof of auxiliary conclusion 3.3 (a) 77
3.4.9 Auxiliary conclusion 3.3 (b) Proof 78
3.4.10 Answer 80 to quiz 3.4
3.5 Point 80 of this chapter
3.6 problem sets, 81
Challenge question 81
Programming problem 82
Chapter 4 Main method 83
4.1 Revisit integer multiplication 83
4.1.1 RecIntMult 84
4.1.2 Karatsuba algorithm 84
4.1.3 Comparative recursive process 85
4.2 Declaration of form 86
4.2.1 Standard Recursive procedure 86
4.2.2 Statement and Discussion of the master method 87
4.3 6 Examples 88
4.3.1 Review MergeSort 89
4.3.2 Binary Search 89
4.3.3 Recursive algorithm for integer multiplication 90
4.3.4 Karatsuba multiplication 90
4.3.5 Matrix multiplication 91
4.3.6 AN imaginary recursive procedure 92
4.3.7 Answers to quizzes 4.2 to 4.3 93
*4.4 Proof of master method 94
4.4.1 preface 94
4.4.2 Review recursion tree 95
4.4.3 Work completed by single layer 96
4.4.4 The total amount of each layer is 97
4.4.5 Good and Evil: 3 scenarios to consider 98
4.4.6 Advance running time upper bound 99
4.4.7 Final calculation: The first case 100
4.4.8 Detour: Geometry 101
4.4.9 Final Calculation: Case 2 and Case 3 102
4.4.10 Answers to quizzes 4.4 to 4.5 103
4.5 Point 103 of this chapter
4.6 problem sets, 104
Chapter 5 QuickSort 107
5.1 overview of 107
5.1.1 order 108
5.1.2 Division according to baseline elements
5.1.3 Advanced Description 110
5.1.4 Content Foresight 110
5.2 Partitioning around baseline Elements
5.2.1 Simple Method 111
5.2.2 Implementation in Place: Advanced Plan 112
Example 5.2.3 requires 113
5.2.4 Pseudocode 115 of the Partition subroutine
5.2.5 QuickSort pseudo-code 117
5.3 The importance of good baseline elements 117
5.3.1 ChoosePivot’s simple implementation 118
5.3.2 ChoosePivot’s over-realization 118
5.3.3 Answers to quizzes 5.1 to 5.2 119
5.4 Randomized QuickSort 121
5.4.1 Randomization of ChoosePivot 121
5.4.2 The running time of Randomizing QuickSort 122
5.4.3 Intuition: Why are random reference elements good 123
*5.5 Analysis of randomization QuickSort 124
5.5.1 Preparatory work 125
5.5.2 Decomposing blueprint 126
5.5.3 Application Blueprint 128
5.5.4 Calculate the probability of comparison 130
5.5.5 Final calculation 132
5.5.6 Answer 133 to Quiz 5.3
*5.6 Sorting requires (n log n) comparison 134
5.6.1 Sorting Algorithm based on comparison 134
5.6.2 Faster Sort with Stronger premises 135
5.6.3 Proof of Theorem 5.5 136
5.7 Point 138 of this chapter
5.8 problem sets, 139
Challenge question 140
Programming problem 141
Chapter 6 selection of Linear Time levels 142
6.1 RSelect Algorithm 143
6.1.1 Selection Question 143
6.1.2 Simplified to 144
6.1.3 Divide-and-conquer 145
6.1.4 RSelect pseudo-code 146
6.1.5 Running time of RSelect 147
6.1.6 Answers to quizzes 6.1 to 6.2 149
*6.2 Analysis of RSelect 150
6.2.1 Tracking progress by stage 150
6.2.2 Simplified to coin toss 151
6.2.3 Comprehensive Conclusion 153
*6.3 DSelect algorithm 154
6.3.1 Basic Idea: The middle element of the middle 154
6.3.2 Pseudocode 155 of DSelect
6.3.3 Understanding DSelect 156
6.3.4 Running time of DSelect 157
*6.4 Analysis of DSelect 159
6.4.1 Work done beyond recursive invocations 159
6.4.2 A rough recursive procedure 159
6.4.3 30-70 Auxiliary Conclusions 160
6.4.4 Parsing the recursive process 163
6.4.5 Guess first and posterior method 164
6.5 Point 166 of this chapter
6.6 Problem 166 in this chapter
Challenge question 167
Programming problem 168
Appendix A A quick review of mathematical induction 169
Appendix B a quick review of discrete probability 173
Fun learning algorithm
Author: Chen Xiaoyu
Scan the QR code and buy with one click
The “dumb way” to learn Python 3
By Zed A. Shaw
Scan the QR code and buy with one click
Data structures (Python)
Author: Kenneth A. Lambert
Scan the QR code and buy with one click
Python Core Programming (Version 3)
Author: Wesley Chun
Scan the QR code and buy with one click
Python programming goes from beginner to master
Author: Ye Weizhong
Scan the QR code and buy with one click
Python programming is taught without instruction
By Corey Orsoff
Scan the QR code and buy with one click
Click “Read the original text” to purchase “Detailed Algorithms: Volume 1 Fundamentals of Algorithms”
Read the original