Paperback(1st Edition)
-
PICK UP IN STORECheck Availability at Nearby Stores
Available within 2 business hours
Related collections and offers
Overview
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
Product Details
| ISBN-13: | 9781617295980 |
|---|---|
| Publisher: | Manning |
| Publication date: | 03/15/2019 |
| Edition description: | 1st Edition |
| Pages: | 224 |
| Sales rank: | 1,096,510 |
| Product dimensions: | 7.30(w) x 9.10(h) x 0.60(d) |
About the Author
Table of Contents
Acknowledgments xi
About this book xiii
About the author xiv
About the cover illustration xv
Introduction 1
0.1 Why Python? 1
0.2 What is a classic computer science problem? 2
0.3 What kinds of problems are in this book? 2
0.4 Who is this book for? 3
0.5 Python versioning, source code repository, and type hints 4
0.6 No graphics, no UI code, just the standard library 5
0.7 Part of a series 5
1 Small problems 6
1.1 The Fibonacci sequence 6
A first recursive attempt 6
Utilizing base cases 8
Memoization to the rescue 9
Automatic memoization 10
Keep it simple, Fibonacci 11
Generating Fibonacci numbers with a generator 11
1.2 Trivial compression 12
1.3 Unbreakable encryption 16
Getting the data in order 16
Encrypting and decrypting 18
1.4 Calculating pi 19
1.5 The Towers of Hanoi 20
Modeling the towers 20
Solving The Towers of Hanoi 22
1.6 Real-world applications 24
1.7 Exercises 24
2 Search problems 25
2.1 DNA search 25
Storing DNA 25
Linear search 27
Binary search 28
A generic example 30
2.2 Maze solving 32
Generating a random maze 32
Miscellaneous maze minutiae 33
Depth-first search 34
Breadth-first search 38
A * search 42
2.3 Missionaries and cannibals 47
Representing the problem 47
Solving 49
2.4 Real-world applications 51
2.5 Exercises 51
3 Constraint-satisfaction problems 52
3.1 Building a constraint-satisfaction problem framework 53
3.2 The Australian map-coloring problem 57
3.3 The eight queens problem 59
3.4 Word search 61
3.5 SEND+MORE=MONEY 65
3.6 Circuit board layout 66
3.7 Real-world applications 67
3.8 Exercises 67
4 Graph problems 68
4.1 A map as a graph 68
4.2 Building a graph framework 71
Working with Edge and Graph 75
4.3 Finding the shortest path 76
Revisiting breadth-first search (BPS) 76
4.4 Minimizing the cost of building the network 78
Workings with weights 78
Finding the minimum spanning tree 82
4.5 Finding shortest paths in a weighted graph 88
Dijkstra's algorithm 88
4.6 Real-world applications 93
4.7 Exercises 93
5 Genetic algorithms 94
5.1 Biological background 94
5.2 A generic genetic algorithm 95
5.3 A naive test 102
5.4 SEND+MORE=MONEY revisited 104
5.5 Optimizing list compression 107
5.6 Challenges for genetic algorithms 109
5.7 Real-world applications 110
5.8 Exercises 111
6 K-means clustering 112
6.1 Preliminaries 113
6.2 The k-means clustering algorithm 115
6.3 Clustering governors by age and longitude 119
6.4 Clustering Michael Jackson albums by length 124
6.5 K-means clustering problems and extensions 125
6.6 Real-world applications 126
6.7 Exercises 126
7 Fairly simple neural networks 127
7.1 Biological basis? 128
7.2 Artificial neural networks 129
Neurons 129
Layers 130
Backpropagation 131
The big picture 135
7.3 Preliminaries 135
Dot product 135
The activation function 136
7.4 Building the network 136
Implementing neurons 137
Implementing layers 138
Implementing the network 140
7.5 Classification problems 143
Normalizing data 143
The classic iris data set 144
Classifying wine 147
7.6 Speeding up neural networks 149
7.7 Neural network problems and extensions 150
7.8 Real-world applications 151
7.9 Exercises 152
8 Adversarial search 153
8.1 Basic board game components 153
8.2 Tic-tac-toe 155
Managing tic-tac-toe state 155
Minimax 158
Testing minimax with tic-tac-toe 160
Developing a tic-tac-toe AT 162
8.3 Connect Four 163
Conned Four game machinery 163
A Connect Four AT 168
Improving minimax with alpha-beta pruning 169
8.4 Minimax improvements beyond alpha-beta pruning 170
8.5 Real-world applications 170
8.6 Exercises 171
9 Miscellaneous problems 172
9.1 The knapsack problem 172
9.2 The Traveling Salesman Problem 177
The naive approach 177
Taking it to the next level 182
9.3 Phone number mnemonics 182
9.4 Real-world applications 184
9.5 Exercises 184
Appendix A Glossary 186
Appendix B More resources 191
Appendix C A brief introduction to type hints 195
Index 201