Learning Algorithms Through Programming and Puzzle Solving.

This book powers our popular Data Structures and Algorithms online specialization on Coursera and the online MicroMasters program on edX. Since the launch of our online courses in 2016, more than 450K learners tried to solve many programming challenges and algorithmic puzzles described in this book. We invite you to join them! About This Book 7 Programming Challenges 8 Interactive Algorithmic Puzzles 8 What Lies Ahead 8 Meet the Authors 8 Meet Our Online Co-Instructors 8 Acknowledgments 8 Algorithms and Complexity 25 What Is an Algorithm? 25 Pseudocode 25 Problem Versus Problem Instance 25 Correct Versus Incorrect Algorithms 27 Fast Versus Slow Algorithms 29 Big-O Notation 31 Advantages and Disadvantages 35 Five Common Rules 36 Visualizing Common Rules 37 Frequently Arising Running Times 41 Algorithm Design Techniques 43 Exhaustive Search Algorithms 43 Branch-and-Bound Algorithms 44 Greedy Algorithms 44 Dynamic Programming Algorithms 47 Recursive Algorithms 50 Divide-and-Conquer Algorithms 56 Randomized Algorithms 60 Programming Challenges 65 Sum of Two Digits 66 Maximum Pairwise Product 69 Naive Algorithm 70 Fast Algorithm 74 Testing and Debugging 75 Can You Tell Me What Error Have I Made? 77 Stress Testing 77 Even Faster Algorithm 82 A More Compact Algorithm 82 Solving a Programming Challenge in Five Easy Steps 82 Reading Problem Statement 83 Designing an Algorithm 83 Implementing an Algorithm 83 Testing and Debugging 84 Submitting to the Grading System 85 Algorithmic Warm Up 87 Programming Challenges 89 Fibonacci Number 89 Last Digit of Fibonacci Number 95 Huge Fibonacci Number 98 Last Digit of the Sum of Fibonacci Numbers 105 Last Digit of the Partial Sum of Fibonacci Numbers 109 Last Digit of the Sum of Squares of Fibonacci Numbers 111 Greatest Common Divisor 114 Least Common Multiple 118 Summary of Algorithmic Ideas 120 Greedy Algorithms 121 The Main Idea 124 Examples 124 Proving Correctness of Greedy Algorithms 125 Implementation 126 Programming Challenges 127 Money Change 127 Maximum Value of the Loot 131 Car Fueling 136 Maximum Advertisement Revenue 141 Collecting Signatures 146 Maximum Number of Prizes 152 Maximum Salary 155 Divide-and-Conquer 159 The Main Idea 161 Guess a Number 161 Searching Sorted Data 165 Finding a White-Black Pair 167 Finding a Peak 169 Multiplying Integers 170 The Master Theorem 174 Programming Challenges 181 Binary Search 181 Binary Search with Duplicates 185 Majority Element 190 Speeding-up RandomizedQuickSort 194 Number of Inversions 197 Organizing a Lottery 203 Closest Points 209 Dynamic Programming 215 The Main Idea 218 Number of Paths 218 Dynamic Programming 220 Shortest Path in Directed Acyclic Graph 221 Programming Challenges 223 Money Change Again 224 Primitive Calculator 229 Edit Distance 234 Longest Common Subsequence of Two Sequences 244 Longest Common Subsequence of Three Sequences 248 Maximum Amount of Gold 251 Splitting the Pirate Loot 260 Maximum Value of an Arithmetic Expression 264 Designing Dynamic Programming Algorithms 271 Best Programming Practices (Optional) 273 Language Independent 273 Code Format 273 Code Structure 273 Names and Comments 275 Debugging 276 Integers and Floating Point Numbers 278 Strings 279 Ranges 280 C++ Specific 282 Code Format 282 Code Structure 282 Types and Constants 284 Classes 286 Containers 288 Integers and Floating Point Numbers 289 Python Specific 290 General 290 Code Structure 293 Functions 295 Strings 296 Classes 297 Exceptions 298 Appendix 301 Compiler Flags 301 Frequently Asked Questions 301 algorithms,programming,computer science,testing,debugging,complexity,running time,data structures,greedy algorithms,dynamic programming,divide-and-conquer Computer Science