LEARNING ALGORITHMS THROUGH PROGRAMMING AND PUZZLE SOLVING I O H L R T M A G S by Alexander Kulikov and Pavel Pevzner Welcome! Thank you for joining us! This book powers our popular Data Structures and Algorithms online specialization on Coursera1 and online MicroMas- tersprogramatedX2.Weencourageyoutosignupforasessionandlearn this material while interacting with thousands of other talented students from around the world. As you explore this book, you will find a number of active learning components that help you study the material at your own pace. 1. PROGRAMMING CHALLENGES ask you to implement the algo- rithms that you will encounter in one of programming languages that we support: C, C++, Java, JavaScript, Python, Scala, C#, Haskell, Ruby, and Rust (the last four programming languages are supported by Coursera only). These code challenges are embedded in our Coursera and edX online courses. 2. ALGORITHMIC PUZZLES provide you with a fun way to “invent” thekeyalgorithmicideasonyourown! Evenifyoufailtosolvesome puzzles, the time will not be lost as you will better appreciate the beauty and power of algorithms. These puzzles are also embedded in our Coursera and edX online courses. 3. EXERCISE BREAKS offer “just in time” assessments testing your understanding of a topic before moving to the next one. 4. STOP and THINK questions invite you to slow down and contem- plate the current material before continuing to the next topic. 1www.coursera.org/specializations/data-structures-algorithms 2www.edx.org/micromasters/ucsandiegox-algorithms-and-data-structures Learning Algorithms Through Programming and Puzzle Solving Alexander S. Kulikov and Pavel Pevzner Active Learning Technologies ©2018 Copyright © 2018 by Alexander S. Kulikov and Pavel Pevzner. All rights reserved. This book or any portion thereof may not be reproduced or used in any manner whatsoever without the express written permission of the pub- lisher except for the use of brief quotations in a book review. ISBN: 978-0-9996762-0-2 Active Learning Technologies Address: 3520 Lebon Drive Suite 5208 San Diego, CA 92122, USA To my parents. — A.K. To my family. — P.P. Contents AboutThisBook ix ProgrammingChallengesandAlgorithmicPuzzles xii WhatLiesAhead xv MeettheAuthors xvi MeetOurOnlineCo-Instructors xvii Acknowledgments xviii 1 AlgorithmsandComplexity 1 1.1 What Is an Algorithm? . . . . . . . . . . . . . . . . . . . . . 1 1.2 Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.3 Problem Versus Problem Instance . . . . . . . . . . . . . . . 1 1.4 Correct Versus Incorrect Algorithms . . . . . . . . . . . . . 3 1.5 Fast Versus Slow Algorithms . . . . . . . . . . . . . . . . . . 4 1.6 Big-O Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2 AlgorithmDesignTechniques 7 2.1 Exhaustive Search Algorithms . . . . . . . . . . . . . . . . . 7 2.2 Branch-and-Bound Algorithms . . . . . . . . . . . . . . . . 8 2.3 Greedy Algorithms . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 Dynamic Programming Algorithms . . . . . . . . . . . . . . 8 2.5 Recursive Algorithms . . . . . . . . . . . . . . . . . . . . . . 12 2.6 Divide-and-Conquer Algorithms . . . . . . . . . . . . . . . 18 2.7 Randomized Algorithms . . . . . . . . . . . . . . . . . . . . 20 3 ProgrammingChallenges 25 3.1 Sum of Two Digits . . . . . . . . . . . . . . . . . . . . . . . . 26 3.2 Maximum Pairwise Product . . . . . . . . . . . . . . . . . . 29 3.2.1 Naive Algorithm . . . . . . . . . . . . . . . . . . . . . 30 3.2.2 Fast Algorithm . . . . . . . . . . . . . . . . . . . . . . 34 3.2.3 Testing and Debugging . . . . . . . . . . . . . . . . . 34 v vi Contents 3.2.4 Can You Tell Me What Error Have I Made? . . . . . . 36 3.2.5 Stress Testing . . . . . . . . . . . . . . . . . . . . . . 37 3.2.6 Even Faster Algorithm . . . . . . . . . . . . . . . . . 41 3.2.7 A More Compact Algorithm . . . . . . . . . . . . . . 42 3.3 Solving a Programming Challenge in Five Easy Steps . . . . 42 3.3.1 Reading Problem Statement . . . . . . . . . . . . . . 42 3.3.2 Designing an Algorithm . . . . . . . . . . . . . . . . 43 3.3.3 Implementing an Algorithm . . . . . . . . . . . . . . 43 3.3.4 Testing and Debugging . . . . . . . . . . . . . . . . . 44 3.3.5 Submitting to the Grading System . . . . . . . . . . 45 3.4 Good Programming Practices . . . . . . . . . . . . . . . . . 45 4 AlgorithmicWarmUp 53 4.1 Fibonacci Number . . . . . . . . . . . . . . . . . . . . . . . . 54 4.2 Last Digit of Fibonacci Number . . . . . . . . . . . . . . . . 56 4.3 Greatest Common Divisor . . . . . . . . . . . . . . . . . . . 58 4.4 Least Common Multiple . . . . . . . . . . . . . . . . . . . . 59 4.5 Fibonacci Number Again . . . . . . . . . . . . . . . . . . . . 60 4.6 Last Digit of the Sum of Fibonacci Numbers . . . . . . . . . 62 4.7 Last Digit of the Sum of Fibonacci Numbers Again . . . . . 63 5 GreedyAlgorithms 65 5.1 Money Change . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.2 Maximum Value of the Loot . . . . . . . . . . . . . . . . . . 69 5.3 Maximum Advertisement Revenue . . . . . . . . . . . . . . 71 5.4 Collecting Signatures . . . . . . . . . . . . . . . . . . . . . . 73 5.5 Maximum Number of Prizes . . . . . . . . . . . . . . . . . . 75 5.6 Maximum Salary . . . . . . . . . . . . . . . . . . . . . . . . . 77 6 Divide-and-Conquer 81 6.1 Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . 82 6.2 Majority Element . . . . . . . . . . . . . . . . . . . . . . . . 85 6.3 Improving QuickSort . . . . . . . . . . . . . . . . . . . . . . 87 6.4 Number of Inversions . . . . . . . . . . . . . . . . . . . . . . 88 6.5 Organizing a Lottery . . . . . . . . . . . . . . . . . . . . . . 90 6.6 Closest Points . . . . . . . . . . . . . . . . . . . . . . . . . . 92 Contents vii 7 DynamicProgramming 97 7.1 Money Change Again . . . . . . . . . . . . . . . . . . . . . . 98 7.2 Primitive Calculator . . . . . . . . . . . . . . . . . . . . . . . 99 7.3 Edit Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 7.4 Longest Common Subsequence of Two Sequences . . . . . . 103 7.5 Longest Common Subsequence of Three Sequences . . . . . 105 7.6 Maximum Amount of Gold . . . . . . . . . . . . . . . . . . . 107 7.7 Partitioning Souvenirs . . . . . . . . . . . . . . . . . . . . . 109 7.8 Maximum Value of an Arithmetic Expression . . . . . . . . 111 Appendix 113 Compiler Flags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 Frequently Asked Questions . . . . . . . . . . . . . . . . . . . . . 114 viii Contents About This Book IfindthatIdon’tunderstandthingsunlessItrytoprogramthem. —DonaldE.Knuth,TheArtofComputerProgramming,Volume4 TherearemanyexcellentbooksonAlgorithms—whyintheworldwe would write another one??? Because we feel that while these books excel in introducing algorith- mic ideas, they have not yet succeeded in teaching you how to implement algorithms, the crucial computer science skill. Our goal is to develop an Intelligent Tutoring System for learning algo- rithmsthroughprogrammingthatcancompetewiththebestprofessorsin atraditionalclassroom. ThisMOOCbookisthefirststeptowardsthisgoal writtenspecificallyforourMassiveOpenOnlineCourses(MOOCs)form- ing a specialization “Algorithms and Data Structures” on Coursera plat- form3 and a microMasters program on edX platform4. Since the launch of our MOOCs in 2016, hundreds of thousand students enrolled in this specializationandtriedtosolvemorethanhundredalgorithmicprogram- ff ming challenges to pass it. And some of them even got o ers from small companies like Google after completing our specialization! In the last few years, some professors expressed concerns about the pedagogicalqualityofMOOCsandevencalledthemthe“junkfoodofed- ucation.” In contrast, we are among the growing group of professors who believe that traditional classes, that pack hundreds of students in a single classroom, represent junk food of education. In a large classroom, once astudenttakesawrongturn,therearelimitedopportunitiestoaskaques- tion, resulting in a learning breakdown, or the inability to progress further withoutindividualguidance. Furthermore,themajorityoftimeastudent invests in an Algorithms course is spent completing assignments outside ffl theclassroom. Thatiswhywestoppedgivinglecturesinouro ineclasses (and we haven’t got fired yet :-). Instead, we give flipped classes where stu- dents watch our recorded lectures, solve algorithmic puzzles, complete programming challenges using our automated homework checking sys- tem before the class, and come to class prepared to discuss their learning 3www.coursera.org/specializations/data-structures-algorithms 4www.edx.org/micromasters/ucsandiegox-algorithms-and-data-structures ix