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, hundreds of thousands students tried to solve many programming challenges and algorithmic puzzles described in this book. We invite you to join them! About This Book 10 Programming Challenges and Algorithmic Puzzles 10 What Lies Ahead 10 Meet the Authors 10 Meet Our Online Co-Instructors 10 Acknowledgments 10 Algorithms and Complexity 20 What Is an Algorithm? 20 Pseudocode 20 Problem Versus Problem Instance 20 Correct Versus Incorrect Algorithms 22 Fast Versus Slow Algorithms 23 Big-O Notation 25 Algorithm Design Techniques 26 Exhaustive Search Algorithms 26 Branch-and-Bound Algorithms 27 Greedy Algorithms 27 Dynamic Programming Algorithms 27 Recursive Algorithms 31 Divide-and-Conquer Algorithms 37 Randomized Algorithms 39 Programming Challenges 44 Sum of Two Digits 45 Maximum Pairwise Product 48 Naive Algorithm 49 Fast Algorithm 53 Testing and Debugging 53 Can You Tell Me What Error Have I Made? 55 Stress Testing 56 Even Faster Algorithm 60 A More Compact Algorithm 61 Solving a Programming Challenge in Five Easy Steps 61 Reading Problem Statement 61 Designing an Algorithm 62 Implementing an Algorithm 62 Testing and Debugging 63 Submitting to the Grading System 64 Good Programming Practices 64 Algorithmic Warm Up 72 Fibonacci Number 73 Last Digit of Fibonacci Number 75 Greatest Common Divisor 77 Least Common Multiple 78 Fibonacci Number Again 79 Last Digit of the Sum of Fibonacci Numbers 81 Last Digit of the Sum of Fibonacci Numbers Again 82 Greedy Algorithms 84 Money Change 85 Maximum Value of the Loot 88 Maximum Advertisement Revenue 90 Collecting Signatures 92 Maximum Number of Prizes 94 Maximum Salary 96 Divide-and-Conquer 100 Binary Search 101 Majority Element 104 Improving QuickSort 106 Number of Inversions 107 Organizing a Lottery 109 Closest Points 111 Dynamic Programming 116 Money Change Again 117 Primitive Calculator 118 Edit Distance 120 Longest Common Subsequence of Two Sequences 122 Longest Common Subsequence of Three Sequences 124 Maximum Amount of Gold 126 Partitioning Souvenirs 128 Maximum Value of an Arithmetic Expression 130 Appendix 132 Compiler Flags 132 Frequently Asked Questions 133 algorithms,programming,computer science,testing,debugging,complexity,running time,data structures,greedy algorithms,dynamic programming,divide-and-conquer Computer Science Acknowledgments......Page 10 Problem Versus Problem Instance......Page 20 Correct Versus Incorrect Algorithms......Page 22 Fast Versus Slow Algorithms......Page 23 Big-O Notation......Page 25 Exhaustive Search Algorithms......Page 26 Dynamic Programming Algorithms......Page 27 Recursive Algorithms......Page 31 Divide-and-Conquer Algorithms......Page 37 Randomized Algorithms......Page 39 Programming Challenges......Page 44 Sum of Two Digits......Page 45 Maximum Pairwise Product......Page 48 Naive Algorithm......Page 49 Testing and Debugging......Page 53 Can You Tell Me What Error Have I Made?......Page 55 Stress Testing......Page 56 Even Faster Algorithm......Page 60 Reading Problem Statement......Page 61 Implementing an Algorithm......Page 62 Testing and Debugging......Page 63 Good Programming Practices......Page 64 Algorithmic Warm Up......Page 72 Fibonacci Number......Page 73 Last Digit of Fibonacci Number......Page 75 Greatest Common Divisor......Page 77 Least Common Multiple......Page 78 Fibonacci Number Again......Page 79 Last Digit of the Sum of Fibonacci Numbers......Page 81 Last Digit of the Sum of Fibonacci Numbers Again......Page 82 Greedy Algorithms......Page 84 Money Change......Page 85 Maximum Value of the Loot......Page 88 Maximum Advertisement Revenue......Page 90 Collecting Signatures......Page 92 Maximum Number of Prizes......Page 94 Maximum Salary......Page 96 Divide-and-Conquer......Page 100 Binary Search......Page 101 Majority Element......Page 104 Improving QuickSort......Page 106 Number of Inversions......Page 107 Organizing a Lottery......Page 109 Closest Points......Page 111 Dynamic Programming......Page 116 Money Change Again......Page 117 Primitive Calculator......Page 118 Edit Distance......Page 120 Longest Common Subsequence of Two Sequences......Page 122 Longest Common Subsequence of Three Sequences......Page 124 Maximum Amount of Gold......Page 126 Partitioning Souvenirs......Page 128 Maximum Value of an Arithmetic Expression......Page 130 Compiler Flags......Page 132 Frequently Asked Questions......Page 133