Classic Computer Science Problems in Python Video Edition

**Summary** __Classic Computer Science Problems in Python__ deepens your knowledge of problem-solving techniques from the realm of computer science by challenging you with time-tested scenarios, exercises, and algorithms. As you work through examples in search, clustering, graphs, and more, you'll remember important things you've forgotten and discover classic solutions to your "new" problems! Purchase of the print book includes a free eBook in PDF, Kindle, and ePub formats from Manning Publications. **About the Technology** Computer science problems that seem new or unique are often rooted in classic algorithms, coding techniques, and engineering principles. And classic approaches are still the best way to solve them! Understanding these techniques in Python expands your potential for success in web development, data munging, machine learning, and more. **About the Book** __Classic Computer Science Problems in Python__ sharpens your CS problem-solving skills with time-tested scenarios, exercises, and algorithms, using Python. You'll tackle dozens of coding challenges, ranging from simple tasks like binary search algorithms to clustering data using k-means. You'll especially enjoy the feeling of satisfaction as you crack problems that connect computer science to the real-world concerns of apps, data, performance, and even nailing your next job interview! **What's Inside** * Search algorithms * Common techniques for graphs * Neural networks * Genetic algorithms * Adversarial search * Uses type hints throughout * Covers Python 3.7 **About the Reader** For intermediate Python programmers. **About the Author** **David Kopec** is an assistant professor of Computer Science and Innovation at Champlain College in Burlington, Vermont. He is the author of __Dart for Absolute Beginne__ (Apress, 2014) and __Classic Computer Science Problems in Swift__ (Manning, 2018). **Table of Contents** 1. Small problems 2. Search problems 3. Constraint-satisfaction problems 4. Graph problems 5. Genetic algorithms 6. K-means clustering 7. Fairly simple neural networks 8. Adversarial search 9. Miscellaneous problems Classic Computer Science Problems in Python -1 contents 8 acknowledgments 12 about this book 14 Trademarks 14 Book forum 14 about the author 15 about the cover illustration 16 Introduction 18 Why Python? 18 What is a classic computer science problem? 19 What kinds of problems are in this book? 19 Who is this book for? 20 Python versioning, source code repository, and type hints 21 No graphics, no UI code, just the standard library 22 Part of a series 22 1 Small problems 23 1.1 The Fibonacci sequence 23 1.1.1 A first recursive attempt 23 1.1.2 Utilizing base cases 25 1.1.3 Memoization to the rescue 26 1.1.4 Automatic memoization 27 1.1.5 Keep it simple, Fibonacci 28 1.1.6 Generating Fibonacci numbers with a generator 28 1.2 Trivial compression 29 1.3 Unbreakable encryption 33 1.3.1 Getting the data in order 33 1.3.2 Encrypting and decrypting 35 1.4 Calculating pi 36 1.5 The Towers of Hanoi 37 1.5.1 Modeling the towers 37 1.5.2 Solving The Towers of Hanoi 39 1.6 Real-world applications 41 1.7 Exercises 41 2 Search problems 42 2.1 DNA search 42 2.1.1 Storing DNA 42 2.1.2 Linear search 44 2.1.3 Binary search 45 2.1.4 A generic example 47 2.2 Maze solving 49 2.2.1 Generating a random maze 49 2.2.2 Miscellaneous maze minutiae 50 2.2.3 Depth-first search 51 2.2.4 Breadth-first search 55 2.2.5 A* search 59 2.3 Missionaries and cannibals 64 2.3.1 Representing the problem 64 2.3.2 Solving 66 2.4 Real-world applications 68 2.5 Exercises 68 3 Constraint-satisfaction problems 69 3.1 Building a constraint-satisfaction problem framework 70 3.2 The Australian map-coloring problem 74 3.3 The eight queens problem 76 3.4 Word search 78 3.5 SEND+MORE=MONEY 82 3.6 Circuit board layout 83 3.7 Real-world applications 84 3.8 Exercises 84 4 Graph problems 85 4.1 A map as a graph 85 4.2 Building a graph framework 88 4.2.1 Working with Edge and Graph 92 4.3 Finding the shortest path 93 4.3.1 Revisiting breadth-first search (BFS) 93 4.4 Minimizing the cost of building the network 95 4.4.1 Workings with weights 95 4.4.2 Finding the minimum spanning tree 99 4.5 Finding shortest paths in a weighted graph 105 4.5.1 Dijkstra?s algorithm 105 4.6 Real-world applications 110 4.7 Exercises 110 5 Genetic algorithms 111 5.1 Biological background 111 5.2 A generic genetic algorithm 112 5.3 A naive test 119 5.4 SEND+MORE=MONEY revisited 121 5.5 Optimizing list compression 124 5.6 Challenges for genetic algorithms 126 5.7 Real-world applications 127 5.8 Exercises 128 6 K-means clustering 129 6.1 Preliminaries 130 6.2 The k-means clustering algorithm 132 6.3 Clustering governors by age and longitude 136 6.4 Clustering Michael Jackson albums by length 141 6.5 K-means clustering problems and extensions 142 6.6 Real-world applications 143 6.7 Exercises 143 7 Fairly simple neural networks 144 7.1 Biological basis? 145 7.2 Artificial neural networks 146 7.2.1 Neurons 146 7.2.2 Layers 147 7.2.3 Backpropagation 148 7.2.4 The big picture 152 7.3 Preliminaries 152 7.3.1 Dot product 152 7.3.2 The activation function 153 7.4 Building the network 153 7.4.1 Implementing neurons 154 7.4.2 Implementing layers 155 7.4.3 Implementing the network 157 7.5 Classification problems 160 7.5.1 Normalizing data 160 7.5.2 The classic iris data set 161 7.5.3 Classifying wine 164 7.6 Speeding up neural networks 166 7.7 Neural network problems and extensions 167 7.8 Real-world applications 168 7.9 Exercises 169 8 Adversarial search 170 8.1 Basic board game components 170 8.2 Tic-tac-toe 172 8.2.1 Managing tic-tac-toe state 172 8.2.2 Minimax 175 8.2.3 Testing minimax with tic-tac-toe 177 8.2.4 Developing a tic-tac-toe AI 179 8.3 Connect Four 180 8.3.1 Connect Four game machinery 180 8.3.2 A Connect Four AI 185 8.3.3 Improving minimax with alpha-beta pruning 186 8.4 Minimax improvements beyond alpha-beta pruning 187 8.5 Real-world applications 187 8.6 Exercises 188 9 Miscellaneous problems 189 9.1 The knapsack problem 189 9.2 The Traveling Salesman Problem 194 9.2.1 The naive approach 194 9.2.2 Taking it to the next level 199 9.3 Phone number mnemonics 199 9.4 Real-world applications 201 9.5 Exercises 201 appendix A Glossary 203 appendix B More resources 208 B.1 Python 208 B.2 Algorithms and data structures 209 B.3 Artificial intelligence 210 B.4 Functional programming 210 B.5 Open source projects useful for machine learning 211 appendix C A brief introduction to type hints 212 C.1 What are type hints? 212 C.2 What do type hints look like? 213 C.3 Why are type hints useful? 214 C.4 What are the downsides of type hints? 215 C.5 Getting more information 216 index 218 Symbols 218 A 218 B 218 C 218 D 219 E 219 F 219 G 220 H 220 I 220 J 220 K 220 L 220 M 220 N 221 O 221 P 221 Q 222 R 222 S 222 T 222 U 222 V 222 W 222 X 223 Y 223 Z 223 Back Cover -1 "Whether you're a novice or a seasoned professional, there's an Aha! moment in this book for everyone." James Watson, Adaptive Classic Computer Science Problems in Python deepens your knowledge of problem solving techniques from the realm of computer science by challenging you with time-tested scenarios and algorithms. As you work through examples in search, clustering, graphs, and more, you'll remember important things you've forgotten and discover classic solutions to your "new" problems! Computer science problems that seem new or unique are often rooted in classic algorithms, coding techniques, and engineering principles. And classic approaches are still the best way to solve them! Understanding these techniques in Python expands your potential for success in web development, data munging, machine learning, and more. Classic Computer Science Problems in Python sharpens your CS problem-solving skills with time-tested scenarios, exercises, and algorithms, using Python. You'll tackle dozens of coding challenges, ranging from simple tasks like binary search algorithms to clustering data using k-means. You'll especially enjoy the feeling of satisfaction as you crack problems that connect computer science to the real-world concerns of apps, data, performance, and even nailing your next job interview! Inside: Search algorithms Common techniques for graphs Neural networks Genetic algorithms Adversarial search Uses type hints throughout Covers Python 3.7 This book/course is made for For intermediate Python programmers. David Kopec is an assistant professor of Computer Science and Innovation at Champlain College in Burlington, Vermont. He is the author of Dart for Absolute Beginners (Apress, 2014) and Classic Computer Science Problems in Swift (Manning, 2018). A fun way to get hands-on experience with classical computer science problems in modern Python. Jens Christian Bredahl Madsen, IT Relation Highly recommended to everyone who is interested in deepening their understanding, not only of the Python language, but also of practical computer science. Daniel Kenney-Jung, MD, University of Minnesota Classic problems presented in a wonderfully entertaining way with a language that always seems to have something new to offer. Sam Zaydel, RackTop Systems NARRATED BY LISA FARINA 'Whether you're a novice or a seasoned professional, there's an Aha! moment in this book for everyone.'- James Watson, Adaptive ”Highly recommended to everyone interested in deepening their understanding of Python and practical computer science.” —Daniel Kenney-Jung, MD, University of Minnesota Key Features • Master formal techniques taught in college computer science classes • Connect computer science theory to real-world applications, data, and performance • Prepare for programmer interviews • Recognize the core ideas behind most “new” challenges • Covers Python 3.7 Purchase of the print book includes a free eBook in PDF, Kindle, and ePub formats from Manning Publications. About The Book Programming problems that seem new or unique are usually rooted in well-known engineering principles. Classic Computer Science Problems in Python guides you through time-tested scenarios, exercises, and algorithms that will prepare you for the “new” problems you'll face when you start your next project. In this amazing book, you'll tackle dozens of coding challenges, ranging from simple tasks like binary search algorithms to clustering data using k-means. As you work through examples for web development, machine learning, and more, you'll remember important things you've forgotten and discover classic solutions that will save you hours of time. What You Will Learn • Search algorithms • Common techniques for graphs • Neural networks • Genetic algorithms • Adversarial search • Uses type hints throughout This Book Is Written For For intermediate Python programmers. About The Author David Kopec is an assistant professor of Computer Science and Innovation at Champlain College in Burlington, Vermont. He is the author of Dart for Absolute Beginners (Apress, 2014), Classic Computer Science Problems in Swift (Manning, 2018), and Classic Computer Science Problems in Java (Manning, 2020) Table of Contents 1. Small problems 2. Search problems 3. Constraint-satisfaction problems 4. Graph problems 5. Genetic algorithms 6. K-means clustering 7. Fairly simple neural networks 8. Adversarial search 9. Miscellaneous problems

Classic Computer Science Problems in Python deepens your knowledge of problem solving techniques from the realm of computer science by challenging you with time-tested scenarios, exercises, and algorithms. As you work through examples in search, clustering, graphs, and more, you'll remember important things you've forgotten and discover classic solutions to your "new" problems!