ebook img

Learning Algorithms Through Programming and Puzzle Solving PDF

195 Pages·2018·5.821 MB·English
Save to my drive
Quick download
Download
Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.

Preview Learning Algorithms Through Programming and Puzzle Solving

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- ters program at edX2. See http://learningalgorithms.tilda.ws/ for more information about these online courses. We encourage you to sign up for a session and learn this material while interacting with thousands of other talented students from around the world. As you explore this book,youwillfindanumberofactivelearningcomponentsthathelpyou 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, Kotlin, Ruby, and Rust (the last five programming lan- guages 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. We encourage you to try ourpuzzlesbeforeattemptingtosolvetheprogrammingchallenges. 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 ActiveLearningTechnologies ©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-9857312-0-5 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 ProgrammingChallenges xii InteractiveAlgorithmicPuzzles xix WhatLiesAhead xxii MeettheAuthors xxiii MeetOurOnlineCo-Instructors xxiv Acknowledgments xxv 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 9 2.1 Exhaustive Search Algorithms . . . . . . . . . . . . . . . . . 9 2.2 Branch-and-Bound Algorithms . . . . . . . . . . . . . . . . 10 2.3 Greedy Algorithms . . . . . . . . . . . . . . . . . . . . . . . 10 2.4 Dynamic Programming Algorithms . . . . . . . . . . . . . . 10 2.5 Recursive Algorithms . . . . . . . . . . . . . . . . . . . . . . 14 2.6 Divide-and-Conquer Algorithms . . . . . . . . . . . . . . . 20 2.7 Randomized Algorithms . . . . . . . . . . . . . . . . . . . . 22 3 ProgrammingChallenges 27 3.1 Sum of Two Digits . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2 Maximum Pairwise Product . . . . . . . . . . . . . . . . . . 31 3.2.1 Naive Algorithm . . . . . . . . . . . . . . . . . . . . . 32 3.2.2 Fast Algorithm . . . . . . . . . . . . . . . . . . . . . . 36 v 3.2.3 Testing and Debugging . . . . . . . . . . . . . . . . . 37 3.2.4 Can You Tell Me What Error Have I Made? . . . . . . 39 3.2.5 Stress Testing . . . . . . . . . . . . . . . . . . . . . . 39 3.2.6 Even Faster Algorithm . . . . . . . . . . . . . . . . . 43 3.2.7 A More Compact Algorithm . . . . . . . . . . . . . . 44 3.3 Solving a Programming Challenge in Five Easy Steps . . . . 44 3.3.1 Reading Problem Statement . . . . . . . . . . . . . . 44 3.3.2 Designing an Algorithm . . . . . . . . . . . . . . . . 45 3.3.3 Implementing an Algorithm . . . . . . . . . . . . . . 45 3.3.4 Testing and Debugging . . . . . . . . . . . . . . . . . 46 3.3.5 Submitting to the Grading System . . . . . . . . . . 47 4 GoodProgrammingPractices 49 4.1 Language Independent . . . . . . . . . . . . . . . . . . . . . 49 4.1.1 Code Format . . . . . . . . . . . . . . . . . . . . . . . 49 4.1.2 Code Structure . . . . . . . . . . . . . . . . . . . . . 49 4.1.3 Names and Comments . . . . . . . . . . . . . . . . . 51 4.1.4 Debugging . . . . . . . . . . . . . . . . . . . . . . . . 52 4.1.5 Integers and Floating Point Numbers . . . . . . . . . 54 4.1.6 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.1.7 Ranges . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.2 C++ Specific . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.2.1 Code Format . . . . . . . . . . . . . . . . . . . . . . . 58 4.2.2 Code Structure . . . . . . . . . . . . . . . . . . . . . 58 4.2.3 Types and Constants . . . . . . . . . . . . . . . . . . 61 4.2.4 Classes . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.2.5 Containers . . . . . . . . . . . . . . . . . . . . . . . . 64 4.2.6 Integers and Floating Point Numbers . . . . . . . . . 65 4.3 Python Specific . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.3.1 General . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.3.2 Code Structure . . . . . . . . . . . . . . . . . . . . . 68 4.3.3 Functions . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.3.4 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.3.5 Classes . . . . . . . . . . . . . . . . . . . . . . . . . . 72 4.3.6 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . 73 vi 5 AlgorithmicWarmUp 75 5.1 Fibonacci Number . . . . . . . . . . . . . . . . . . . . . . . . 77 5.2 Last Digit of Fibonacci Number . . . . . . . . . . . . . . . . 79 5.3 Greatest Common Divisor . . . . . . . . . . . . . . . . . . . 81 5.4 Least Common Multiple . . . . . . . . . . . . . . . . . . . . 82 5.5 Fibonacci Number Again . . . . . . . . . . . . . . . . . . . . 83 5.6 Last Digit of the Sum of Fibonacci Numbers . . . . . . . . . 85 Solution 1: Pisano Period . . . . . . . . . . . . . . . . . . . . 86 Solution 2: Fast Matrix Exponentiation . . . . . . . . . . . . 89 Python Code . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 5.7 Last Digit of the Sum of Fibonacci Numbers Again . . . . . 93 5.8 Last Digit of the Sum of Squares of Fibonacci Numbers . . . 94 6 GreedyAlgorithms 97 6.1 Money Change . . . . . . . . . . . . . . . . . . . . . . . . . . 99 Solution: Use Largest Denomination First . . . . . . . . . . 100 Python Code . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 6.2 Maximum Value of the Loot . . . . . . . . . . . . . . . . . . 103 6.3 Car Fueling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 6.4 Maximum Advertisement Revenue . . . . . . . . . . . . . . 107 6.5 Collecting Signatures . . . . . . . . . . . . . . . . . . . . . . 109 Solution: Cover Segments with Minimum Right End First . 110 Python Code . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 6.6 Maximum Number of Prizes . . . . . . . . . . . . . . . . . . 114 6.7 Maximum Salary . . . . . . . . . . . . . . . . . . . . . . . . . 116 7 Divide-and-Conquer 119 7.1 Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . 121 7.2 Majority Element . . . . . . . . . . . . . . . . . . . . . . . . 124 7.3 Improving QuickSort . . . . . . . . . . . . . . . . . . . . . . 126 7.4 Number of Inversions . . . . . . . . . . . . . . . . . . . . . . 127 7.5 Organizing a Lottery . . . . . . . . . . . . . . . . . . . . . . 129 Solution 1: Sorting All Points . . . . . . . . . . . . . . . . . 130 Solution 2: Binary Search . . . . . . . . . . . . . . . . . . . . 132 Python Code . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 7.6 Closest Points . . . . . . . . . . . . . . . . . . . . . . . . . . 135 vii 8 DynamicProgramming 141 8.1 Money Change Again . . . . . . . . . . . . . . . . . . . . . . 144 8.2 Primitive Calculator . . . . . . . . . . . . . . . . . . . . . . . 145 8.3 Edit Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 8.4 Longest Common Subsequence of Two Sequences . . . . . . 149 8.5 Longest Common Subsequence of Three Sequences . . . . . 151 8.6 Maximum Amount of Gold . . . . . . . . . . . . . . . . . . . 153 Solution 1: Analyzing the Structure of a Solution . . . . . . 154 Solution 2: Analyzing All Subsets of Bars . . . . . . . . . . . 156 Solution 3: Memoization . . . . . . . . . . . . . . . . . . . . 158 Python Code . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 8.7 Partitioning Souvenirs . . . . . . . . . . . . . . . . . . . . . 162 8.8 Maximum Value of an Arithmetic Expression . . . . . . . . 164 Appendix 165 Compiler Flags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 Frequently Asked Questions . . . . . . . . . . . . . . . . . . . . . 166 viii About This Book IfindthatIdon’tunderstandthingsunlessItrytoprogramthem. —DonaldE.Knuth,TheArtofComputerProgramming,Volume4 There are many excellent books on Algorithms — why in the world would we 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. Learning algorithms with- out implementing them is like learning surgery based solely on reading an anatomy book. 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 3www.coursera.org/specializations/data-structures-algorithms 4www.edx.org/micromasters/ucsandiegox-algorithms-and-data-structures ix

See more

The list of books you might like

Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.