Learning Algorithms Through Programming and Puzzle Solving

1 Learning ALGORITHMSTHROUGHPROGRAMMING AND Puzzle SOLVINGIOLAGRHTMSby Alexander Kulikov and Pavel PevznerWelcome!Thank you for joining us! This book powers our popular Data Structuresand Algorithms online specialization on Coursera1and online MicroMas-ters program at edX2. We encourage you to sign up for a session and learnthis material while interacting with thousands of other talented studentsfrom around the world. As you explore this book, you will find a numberof active Learning components that help you study the material at yourown CHALLENGESask you to implement the algo-rithms that you will encounter in one of Programming languagesthat we support:C,C++,Java,JavaScript,Python,Sca la,C#,Haskell,Ruby, andRust(the last four Programming languages aresupported by Coursera only). These code challenges are embeddedin our Coursera and edX online puzzles provide you with a fun way to invent the key algorithmic ideas on your own!

2 Even if you fail to solve somepuzzles, the time will not be lost as you will better appreciate thebeauty and power of Algorithms . These puzzles are also embeddedin our Coursera and edX online BREAKS offer just in time assessments testing yourunderstanding of a topic before moving to the next and THINK questions invite you to slow down and contem-plate the current material before continuing to the next Algorithms Through Programmingand Puzzle SolvingAlexander S. Kulikov and Pavel PevznerActive Learning Technologies 2018 Copyright 2018 by Alexander S. Kulikov and Pavel Pevzner. All book or any portion thereof may not be reproduced or used in anymanner whatsoever without the express written permission of the pub-lisher except for the use of brief quotations in a book : 978-0-9996762-0-2 Active Learning TechnologiesAddress:3520 Lebon DriveSuite 5208 San Diego, CA 92122, USATo my parents.

3 My family. This BookixProgramming Challenges and Algorithmic PuzzlesxiiWhat Lies AheadxvMeet the AuthorsxviMeet Our Online Co-InstructorsxviiAcknowledgmentsxviii1 Algorithms and What Is an Algorithm? .. Pseudocode .. Problem Versus Problem Instance .. Correct Versus Incorrect Algorithms .. Fast Versus Slow Algorithms .. Big-O Notation ..62 Algorithm Design Exhaustive Search Algorithms .. Branch-and-Bound Algorithms .. Greedy Algorithms .. Dynamic Programming Algorithms .. Recursive Algorithms .. Divide-and-Conquer Algorithms .. Randomized Algorithms ..203 Programming Sum of Two Digits .. Maximum Pairwise Product .. Algorithm .. Algorithm .. and Debugging .. You Tell Me What Error Have I Made? .. Testing .. Faster Algorithm .. More Compact Algorithm .. Solving a Programming Challenge in Five Easy Steps.

4 Problem Statement .. an Algorithm .. an Algorithm .. and Debugging .. to the Grading System .. Good Programming Practices ..454 Algorithmic Warm Fibonacci Number .. Last Digit of Fibonacci Number .. Greatest Common Divisor .. Least Common Multiple .. Fibonacci Number Again .. Last Digit of the Sum of Fibonacci Numbers .. Last Digit of the Sum of Fibonacci Numbers Again ..635 Greedy Money Change .. Maximum Value of the Loot .. Maximum Advertisement Revenue .. Collecting Signatures .. Maximum Number of Prizes .. Maximum Salary ..776 Binary Search .. Majority Element .. ImprovingQuickSort.. Number of Inversions .. Organizing a Lottery .. Closest Points ..92 Contentsvii7 Dynamic Money Change Again .. Primitive Calculator .. Edit Distance .. Longest Common Subsequence of Two Sequences.

5 Longest Common Subsequence of Three Sequences .. Maximum Amount of Gold .. Partitioning Souvenirs .. Maximum Value of an Arithmetic Expression .. 111 Appendix113 Compiler Flags .. 113 Frequently Asked Questions .. 114viiiContentsAbout This BookI find that I don t understand things unless I try to program them. Donald E. Knuth,The Art of Computer Programming , Volume 4 There are many excellent books on Algorithms why in the world wewould 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 implementalgorithms, the crucial computer science goal is to develop anIntelligent Tutoring Systemfor Learning algo-rithms Through Programming that can compete with the best professors ina traditional classroom. ThisMOOC bookis the first step towards this goalwritten specifically for our Massive Open Online Courses (MOOCs) form-ing a specialization Algorithms and Data Structures on Coursera plat-form3and a microMasters program on edX platform4.

6 Since the launchof our MOOCs in 2016, hundreds of thousand students enrolled in thisspecialization and tried to solve more than hundred algorithmic program-ming challenges to pass it. And some of them even got offers from smallcompanies like Google after completing our specialization!In the last few years, some professors expressed concerns about thepedagogical quality of MOOCs and even called them the junk food of ed-ucation. In contrast, we are among the growing group of professors whobelieve that traditional classes, that pack hundreds of students in a singleclassroom, represent junk food of education. In a large classroom, oncea student takes a wrong turn, there are limited opportunities to ask a ques-tion, resulting in alearning breakdown, or the inability to progress furtherwithout individual guidance. Furthermore, the majority of time a studentinvests in an Algorithms course is spent completing assignments outsidethe classroom.

7 That is why we stopped giving lectures in our offline classes(and we haven t got fired yet :-). Instead, we giveflipped classeswhere stu-dents watch our recorded lectures, solve algorithmic puzzles , completeprogramming challenges using our automated homework checking sys-tem before the class, and come to class prepared to discuss their This Bookbreakdowns with a student suffers a Learning breakdown, that student needs im-mediate help in order to proceed. Traditional textbooks do not providesuch help, but our automated grading system described in this MOOC book does! Algorithms is a unique discipline in that students ability toprogram provides the opportunity to automatically check their knowl-edge Through coding challenges. These coding challenges are far superiorto traditional quizzes that barely check whether a student fell asleep. In-deed, to implement a complex algorithm, the student must possess a deepunderstanding of its underlying algorithmic believe that a large portion of grading in thousands of Algorithmscourses taught at various universities each year can be consolidated intoa single automated system available at all universities.

8 It did not escapeour attention that many professors teaching Algorithms have implementedtheir own custom-made systems for grading student programs, an illus-tration of academic inefficiency and lack of cooperation between variousinstructors. Our goal is to build a repository of algorithmic programmingchallenges, thus allowing professors to focus on teaching. We have alreadyinvested thousands of hours into building such a system and thousandsstudents in our MOOCs tested it. Below we briefly describe how it you face a Programming challenge, your goal is to implementa fast and memory-efficient algorithm for its solution. Solving program-ming challenges will help you better understand various Algorithms andmay even land you a job since many high-tech companies ask applicantsto solve Programming challenges during the interviews. Your implemen-tation will be checked automatically against many carefully selected teststo verify that it always produces a correct answer and fits into the timeand memory constrains.

9 Our system will teach you to write programs thatwork correctly on all of our test datasets rather than on some of them. Thisis an important skill since failing to thoroughly test your programs leadsto undetected bugs that frustrate your boss, your colleagues, and, mostimportantly, users of your maybe wondering why it took thousands of hours to develop sucha system. First, we had to build a Compendium of Learning Breakdownsfor each Programming challenge, 10 15 most frequent errors that stu-dents make while Solving it. Afterwards, we had to develop test casesfor each Learning breakdown in each Programming challenge, over 20 000test cases for just 100 Programming challenges in our This BookxiWe encourage you to sign up for ourAlgorithms and Data Structuresspecialization on Coursera or MicroMasters program on edX and start in-teracting with thousands of talented students from around the world whoare Learning Algorithms .

10 Thank you for joining us!xiiProgramming Challenges and Algorithmic PuzzlesProgramming Challenges and AlgorithmicPuzzlesThis edition introduces basic algorithmic techniques using 29 program-ming challenges represented as icons below:Sum of Two Digits2 + 3 = 5 MaximumPairwise Product562745301035206301242242101274735 42142842024828 Fibonacci Number11235 Last Digitof FibonacciNumberF170= 150 804 340 016807 970 735 635273 952 047 185 GreatestCommon Divisor1026 Least Com-mon Multiple3023561510 FibonacciNumber AgainFnmod 300111122305282131 Sum ofFibonacci Numbers1 + 1 + 2 + 3 + 5 + 8 = 20 Partial Sum ofFibonacci Numbers2 + 3 + 5 + 8 + 13 = 31 Money Change 1 5 10 Maximum Valueof the LootMaximumAdvertisementRevenueclickspri ces302010532 CollectingSignaturesMaximumNumber of Prizes8125 Maximum SalaryResumeBinary Search137891215137891215137891215 Majority ElementImprovingQuickSortNumber ofInversion32594 Organizinga Lottery1021 Closest PointsMoneyChange Again 1 3 4 Primitive Calculator1+1 2 3 Edit DistanceshorthortportportsLongest CommonSubsequence ofTwo Sequences72931594281397 Longest CommonSubsequence ofThree