Classic Computer Science Problems in Python
David Kopec
  • MEAP began July 2018
  • Publication in January 2019 (estimated)
  • ISBN 9781617295980
  • 275 pages (estimated)
  • printed in black & white

One accomplishment that the writer really brings off, and which is nontrivial, is that he is able to use an approachable tone without being patronizing or using distracting attempts at humor. The writing is really clear. This is a good example of superb didactic technical writing.

Daniel Kenney-Jung
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!
Table of Contents detailed table of contents

0 Introduction

0.1 Why Python?

0.2 What is a classic computer science problem?

0.3 What kinds of problems are in this book?

0.4 Who is this book for?

0.5 Python versioning, source code repository, and type hints

0.6 No graphics, no UI code, just the standard library

0.7 Part of a series

1 Small problems

1.1 The Fibonacci sequence

1.1.1 A first recursive attempt

1.1.2 Utilizing base cases

1.1.3 Memoization to the rescue

1.1.4 Automatic memoization

1.1.5 Keep it simple, Fibonacci

1.1.6 Generating Fibonacci numbers with a generator

1.2 Trivial compression

1.3 Unbreakable encryption

1.3.1 Getting the data in order

1.3.2 Encrypting and decrypting

1.4 Calculating pi

1.5 The Towers of Hanoi

1.5.1 Modeling the towers

1.5.2 Solving The Towers of Hanoi

1.6 Real-world applications

1.7 Exercises

2 Search problems

2.1.1 Storing DNA

2.1.4 A generic example

2.2 Maze solving

2.2.1 Generating a random maze

2.2.2 Miscellaneous maze minutiae

2.3 Missionaries and cannibals

2.3.1 Representing the problem

2.3.2 Solving

2.4 Real-world applications

2.5 Exercises

3 Constraint-satisfaction problems

3.1 Building a constraint-satisfaction problem framework

3.2 The Australian map-coloring problem

3.3 The eight queens problem

3.5 SEND+MORE=MONEY

3.6 Circuit board layout

3.7 Real-world applications

3.8 Exercises

4 Graph problems

4.1 A map as a graph

4.2 Building a graph framework

4.2.1 Working with Edge and Graph

4.3 Finding the shortest path

4.3.1 Revisiting breadth-first search (BFS)

4.4 Minimizing the cost of building the network

4.4.1 Workings with weights

4.4.2 Finding the minimum spanning tree

4.5 Finding shortest paths in a weighted graph

4.5.1 Dijkstra’s algorithm

4.6 Real-world applications

4.7 Exercises

5 Genetic algorithms

5.1 Biological background

5.2 A generic genetic algorithm

5.3 A naive test

5.4 SEND+MORE=MONEY revisited

5.5 Optimizing List Compression

5.6 Challenges for genetic algorithms

5.7 Real-world applications

5.8 Exercises

6 K-means clustering

6.1 Preliminaries

6.2 The k-means clustering algorithm

6.3 Clustering governors by age and longitude

6.4 Clustering Michael Jackson albums by length

6.5 K-means clustering problems and extensions

6.6 Real-world applications

6.7 Exercises

7 Fairly simple neural networks

7.1 Biological basis?

7.2 Artificial neural networks

7.2.1 Neurons

7.2.2 Layers

7.2.3 Backpropagation

7.2.4 The big picture

7.3 Preliminaries

7.3.1 Dot product

7.3.2 The activation function

7.4 Building the network

7.4.1 Implementing neurons

7.4.2 Implementing layers

7.4.3 Implementing the network

7.5 Classification problems

7.5.1 Normalizing data

7.5.2 The classic iris data set

7.5.3 Classifying wine

7.6 Speeding up neural networks

7.7 Neural network problems and extensions

7.8 Real-world applications

7.9 Exercises

8 Adversarial Search

8.1 Basic board game components

8.2 Tic-tac-toe

8.2.1 Managing tic-tac-toe state

8.2.2 Minimax

8.2.3 Testing minimax with tic-tac-toe

8.2.4 Developing a tic-tac-toe AI

8.3 Connect Four[20]

8.3.1 Connect Four game machinery

8.3.2 A Connect Four AI

8.3.3 Improving minimax with alpha beta pruning

8.4 Minimax improvements beyond alpha beta pruning

8.5 Real-world applications

8.6 Exercises

9 Miscellaneous problems

9.1 The knapsack problem

9.2 The traveling salesman problem

9.2.1 The naive approach

9.2.2 Taking it to the next level

9.3 Phone number mnemonics

9.4 Real-world applications

9.5 Exercises

Appendixes

Appendix A: Glossary

Appendix B: More resources

B.1 Python

B.2 Algorithms and data structures

B.3 Artificial intelligence

B.4 Functional programming

B.5 Open source projects mentioned in this book

Appendix C: A brief introduction to type hints

C.1 What are type hints?

C.1.1 What do type hints look like?

C.2 Why are type hints useful?

C.3 What are the downsides of type hints?

C.4 Getting more information

About the Technology

Don't just learn another language. Become a better programmer instead! Python is used everywhere for web applications, data munging, and powerful machine learning applications. Even problems that seem new or unique stand on the shoulders of classic algorithms, coding techniques, and engineering principles. Master these core skills, and you’ll be ready to use Python for optimization problems, AI, machine learning, and the other challenges you’ll face as you grow your skill as a programmer.

About the book

Classic Computer Science Problems in Python presents dozens of coding challenges, ranging from simple tasks like finding items in a list with a binary search algorithm to clustering data using k-means. For each carefully-selected problem, you’ll find an artful solution along with a clear explanation both of how to think about the problem and how to apply your new skill to other similar scenarios. You’ll appreciate author David Kopec’s amazing ability to connect the core disciplines of computer science to the real-world concerns of apps, data, performance, and even nailing your next job interview!

Based on David’s book Classic Computer Problems in Swift, this book offers Python-based examples to the same core problems as well as a new chapter on Adversarial Search.

What's inside

  • Breadth-first and depth-first search algorithms
  • Constraints satisfaction problems
  • Common techniques for graphs
  • Neural networks and genetic algorithms
  • Adversarial Search

About the reader

For intermediate–advanced Python programmers.

About the author

David Kopec, an Assistant Professor of Computer Science & Innovation at Champlain College, is the author of Dart for Absolute Beginners and Classic Computer Science Problems in Swift. David is an experienced software developer and avid open source contributor.

Manning Early Access Program (MEAP) Read chapters as they are written, get the finished eBook as soon as it’s ready, and receive the pBook long before it's in bookstores.

FREE domestic shipping on three or more pBooks