Classic computer science problems in Python

✍ Scribed by Kopec, David

• Publisher: Manning Publications Co
• Year: 2019
• Tongue: English
• Leaves: 224
• Category: Library

✦ Synopsis

”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






Small problems Search problems Constraint-satisfaction problems Graph problems Genetic algorithms K-means clustering Fairly simple neural networks Adversarial search Miscellaneous problems

✦ Table of Contents

Back Cover......Page 0
contents......Page 8
acknowledgments......Page 12
Book forum......Page 14
about the author......Page 15
about the cover illustration......Page 16
Why Python?......Page 18
What kinds of problems are in this book?......Page 19
Who is this book for?......Page 20
Python versioning, source code repository, and type hints......Page 21
Part of a series......Page 22
1.1.1 A first recursive attempt......Page 23
1.1.2 Utilizing base cases......Page 25
1.1.3 Memoization to the rescue......Page 26
1.1.4 Automatic memoization......Page 27
1.1.6 Generating Fibonacci numbers with a generator......Page 28
1.2 Trivial compression......Page 29
1.3.1 Getting the data in order......Page 33
1.3.2 Encrypting and decrypting......Page 35
1.4 Calculating pi......Page 36
1.5.1 Modeling the towers......Page 37
1.5.2 Solving The Towers of Hanoi......Page 39
1.7 Exercises......Page 41
2.1.1 Storing DNA......Page 42
2.1.2 Linear search......Page 44
2.1.3 Binary search......Page 45
2.1.4 A generic example......Page 47
2.2.1 Generating a random maze......Page 49
2.2.2 Miscellaneous maze minutiae......Page 50
2.2.3 Depth-first search......Page 51
2.2.4 Breadth-first search......Page 55
2.2.5 A* search......Page 59
2.3.1 Representing the problem......Page 64
2.3.2 Solving......Page 66
2.5 Exercises......Page 68
3 Constraint-satisfaction problems......Page 69
3.1 Building a constraint-satisfaction problem framework......Page 70
3.2 The Australian map-coloring problem......Page 74
3.3 The eight queens problem......Page 76
3.4 Word search......Page 78
3.5 SEND+MORE=MONEY......Page 82
3.6 Circuit board layout......Page 83
3.8 Exercises......Page 84
4.1 A map as a graph......Page 85
4.2 Building a graph framework......Page 88
4.2.1 Working with Edge and Graph......Page 92
4.3.1 Revisiting breadth-first search (BFS)......Page 93
4.4.1 Workings with weights......Page 95
4.4.2 Finding the minimum spanning tree......Page 99
4.5.1 Dijkstra?s algorithm......Page 105
4.7 Exercises......Page 110
5.1 Biological background......Page 111
5.2 A generic genetic algorithm......Page 112
5.3 A naive test......Page 119
5.4 SEND+MORE=MONEY revisited......Page 121
5.5 Optimizing list compression......Page 124
5.6 Challenges for genetic algorithms......Page 126
5.7 Real-world applications......Page 127
5.8 Exercises......Page 128
6 K-means clustering......Page 129
6.1 Preliminaries......Page 130
6.2 The k-means clustering algorithm......Page 132
6.3 Clustering governors by age and longitude......Page 136
6.4 Clustering Michael Jackson albums by length......Page 141
6.5 K-means clustering problems and extensions......Page 142
6.7 Exercises......Page 143
7 Fairly simple neural networks......Page 144
7.1 Biological basis?......Page 145
7.2.1 Neurons......Page 146
7.2.2 Layers......Page 147
7.2.3 Backpropagation......Page 148
7.3.1 Dot product......Page 152
7.4 Building the network......Page 153
7.4.1 Implementing neurons......Page 154
7.4.2 Implementing layers......Page 155
7.4.3 Implementing the network......Page 157
7.5.1 Normalizing data......Page 160
7.5.2 The classic iris data set......Page 161
7.5.3 Classifying wine......Page 164
7.6 Speeding up neural networks......Page 166
7.7 Neural network problems and extensions......Page 167
7.8 Real-world applications......Page 168
7.9 Exercises......Page 169
8.1 Basic board game components......Page 170
8.2.1 Managing tic-tac-toe state......Page 172
8.2.2 Minimax......Page 175
8.2.3 Testing minimax with tic-tac-toe......Page 177
8.2.4 Developing a tic-tac-toe AI......Page 179
8.3.1 Connect Four game machinery......Page 180
8.3.2 A Connect Four AI......Page 185
8.3.3 Improving minimax with alpha-beta pruning......Page 186
8.5 Real-world applications......Page 187
8.6 Exercises......Page 188
9.1 The knapsack problem......Page 189
9.2.1 The naive approach......Page 194
9.3 Phone number mnemonics......Page 199
9.5 Exercises......Page 201
appendix A Glossary......Page 203
B.1 Python......Page 208
B.2 Algorithms and data structures......Page 209
B.4 Functional programming......Page 210
B.5 Open source projects useful for machine learning......Page 211
C.1 What are type hints?......Page 212
C.2 What do type hints look like?......Page 213
C.3 Why are type hints useful?......Page 214
C.4 What are the downsides of type hints?......Page 215
C.5 Getting more information......Page 216
C......Page 218
F......Page 219
M......Page 220
P......Page 221
W......Page 222
Z......Page 223

✦ Subjects

Computer Science;Programming;Science;Technology;Software;Computers;Coding;Textbooks