Learning Algorithms Through Programming and Puzzle Solving-Leanpub (2018).pdf

发布时间：2022-06-14 发布人：admin 分类：说明书资料大小：5.14M 资料格式：pdf 举报版权申诉

211bc069-b047-4534-8d51-7802f0d34c2b.pdf-第1页.png

第1页 / 共138页

211bc069-b047-4534-8d51-7802f0d34c2b.pdf-第2页.png

第2页 / 共138页

211bc069-b047-4534-8d51-7802f0d34c2b.pdf-第3页.png

第3页 / 共138页

211bc069-b047-4534-8d51-7802f0d34c2b.pdf-第4页.png

第4页 / 共138页

211bc069-b047-4534-8d51-7802f0d34c2b.pdf-第5页.png

第5页 / 共138页

211bc069-b047-4534-8d51-7802f0d34c2b.pdf-第6页.png

第6页 / 共138页

211bc069-b047-4534-8d51-7802f0d34c2b.pdf-第7页.png

第7页 / 共138页

211bc069-b047-4534-8d51-7802f0d34c2b.pdf-第8页.png

第8页 / 共138页

About This Book

Programming Challenges and Algorithmic Puzzles

What Lies Ahead

Meet the Authors

Meet Our Online Co-Instructors

Acknowledgments

Algorithms and Complexity

What Is an Algorithm?

Pseudocode

Problem Versus Problem Instance

Correct Versus Incorrect Algorithms

Fast Versus Slow Algorithms

Big-O Notation

Algorithm Design Techniques

Exhaustive Search Algorithms

Branch-and-Bound Algorithms

Greedy Algorithms

Dynamic Programming Algorithms

Recursive Algorithms

Divide-and-Conquer Algorithms

Randomized Algorithms

Programming Challenges

Sum of Two Digits

Maximum Pairwise Product

Naive Algorithm

Fast Algorithm

Testing and Debugging

Can You Tell Me What Error Have I Made?

Stress Testing

Even Faster Algorithm

A More Compact Algorithm

Solving a Programming Challenge in Five Easy Steps

Reading Problem Statement

Designing an Algorithm

Implementing an Algorithm

Testing and Debugging

Submitting to the Grading System

Good Programming Practices

Algorithmic Warm Up

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

Greedy Algorithms

Money Change

Maximum Value of the Loot

Maximum Advertisement Revenue

Collecting Signatures

Maximum Number of Prizes

Maximum Salary

Divide-and-Conquer

Binary Search

Majority Element

Improving QuickSort

Number of Inversions

Organizing a Lottery

Closest Points

Dynamic Programming

Money Change Again

Primitive Calculator

Edit Distance

Longest Common Subsequence of Two Sequences

Longest Common Subsequence of Three Sequences

Maximum Amount of Gold

Partitioning Souvenirs

Maximum Value of an Arithmetic Expression

Appendix

Compiler Flags

Frequently Asked Questions

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. 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, you will ﬁnd 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” the key algorithmic ideas on your own! Even if you fail to solve some 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 oﬀer “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

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 About This Book Programming Challenges and Algorithmic Puzzles What Lies Ahead Meet the Authors Meet Our Online Co-Instructors Acknowledgments 1 Algorithms and Complexity 1.1 What Is an Algorithm? . . . . . . . . . . . . . . . . . . . . . 1.2 Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Problem Versus Problem Instance . . . . . . . . . . . . . . . 1.4 Correct Versus Incorrect Algorithms . . . . . . . . . . . . . 1.5 Fast Versus Slow Algorithms . . . . . . . . . . . . . . . . . . 1.6 Big-O Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Algorithm Design Techniques 2.1 Exhaustive Search Algorithms . . . . . . . . . . . . . . . . . 2.2 Branch-and-Bound Algorithms . . . . . . . . . . . . . . . . 2.3 Greedy Algorithms . . . . . . . . . . . . . . . . . . . . . . . 2.4 Dynamic Programming Algorithms . . . . . . . . . . . . . . 2.5 Recursive Algorithms . . . . . . . . . . . . . . . . . . . . . . 2.6 Divide-and-Conquer Algorithms . . . . . . . . . . . . . . . 2.7 Randomized Algorithms . . . . . . . . . . . . . . . . . . . . 3 Programming Challenges 3.1 Sum of Two Digits . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Maximum Pairwise Product . . . . . . . . . . . . . . . . . . 3.2.1 Naive Algorithm . . . . . . . . . . . . . . . . . . . . . 3.2.2 Fast Algorithm . . . . . . . . . . . . . . . . . . . . . . 3.2.3 Testing and Debugging . . . . . . . . . . . . . . . . . v ix xii xv xvi xvii xviii 1 1 1 1 3 4 6 7 7 8 8 8 12 18 20 25 26 29 30 34 34

vi Contents 3.2.4 Can You Tell Me What Error Have I Made? . . . . . . 3.2.5 Stress Testing . . . . . . . . . . . . . . . . . . . . . . 3.2.6 Even Faster Algorithm . . . . . . . . . . . . . . . . . 3.2.7 A More Compact Algorithm . . . . . . . . . . . . . . 3.3 Solving a Programming Challenge in Five Easy Steps . . . . 3.3.1 Reading Problem Statement . . . . . . . . . . . . . . 3.3.2 Designing an Algorithm . . . . . . . . . . . . . . . . 3.3.3 Implementing an Algorithm . . . . . . . . . . . . . . 3.3.4 Testing and Debugging . . . . . . . . . . . . . . . . . 3.3.5 Submitting to the Grading System . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Good Programming Practices 4 Algorithmic Warm Up 4.1 Fibonacci Number . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Last Digit of Fibonacci Number . . . . . . . . . . . . . . . . 4.3 Greatest Common Divisor . . . . . . . . . . . . . . . . . . . 4.4 Least Common Multiple . . . . . . . . . . . . . . . . . . . . 4.5 Fibonacci Number Again . . . . . . . . . . . . . . . . . . . . 4.6 Last Digit of the Sum of Fibonacci Numbers . . . . . . . . . 4.7 Last Digit of the Sum of Fibonacci Numbers Again . . . . . 5 Greedy Algorithms 5.1 Money Change . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Maximum Value of the Loot . . . . . . . . . . . . . . . . . . 5.3 Maximum Advertisement Revenue . . . . . . . . . . . . . . 5.4 Collecting Signatures . . . . . . . . . . . . . . . . . . . . . . 5.5 Maximum Number of Prizes . . . . . . . . . . . . . . . . . . 5.6 Maximum Salary . . . . . . . . . . . . . . . . . . . . . . . . . 6 Divide-and-Conquer 6.1 Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Majority Element . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Improving QuickSort . . . . . . . . . . . . . . . . . . . . . . 6.4 Number of Inversions . . . . . . . . . . . . . . . . . . . . . . 6.5 Organizing a Lottery . . . . . . . . . . . . . . . . . . . . . . 6.6 Closest Points . . . . . . . . . . . . . . . . . . . . . . . . . . 36 37 41 42 42 42 43 43 44 45 45 53 54 56 58 59 60 62 63 65 66 69 71 73 75 77 81 82 85 87 88 90 92

Contents vii 7 Dynamic Programming 97 98 7.1 Money Change Again . . . . . . . . . . . . . . . . . . . . . . 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

分享到：

赞收藏

资料库

Learning Algorithms Through Programming and Puzzle Solving-Leanpub (2018).pdf

相关推荐

开发技术

热门标签

最新资料