Classic Computer Science Problems in Python
David Kopec
  • March 2019
  • ISBN 9781617295980
  • 224 pages
  • printed in black & white

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, 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!

Listen to this book in liveAudio! liveAudio integrates a professional voice recording with the book’s text, graphics, code, and exercises in Manning’s exclusive liveBook online reader. Use the text to search and navigate the audio, or download the audio-only recording for portable offline listening. You can purchase or upgrade to liveAudio here or in liveBook.

Table of Contents detailed table of contents

Introduction

Why Python?

What is a classic computer science problem?

What kinds of problems are in this book?

Who is this book for?

Python versioning, source code repository, and type hints

No graphics, no UI code, just the standard library

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 DNA search

2.1.1 Storing DNA

2.1.2 Linear search

2.1.3 Binary search

2.1.4 A generic example

2.2 Maze solving

2.2.1 Generating a random maze

2.2.2 Miscellaneous maze minutiae

2.2.3 Depth-first search

2.2.4 Breadth-first search

2.2.5 A* search

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.4 Word search

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.2 What do type hints look like?

C.3 Why are type hints useful?

C.4 What are the downsides of type hints?

C.5 Getting more information

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 Beginners (Apress, 2014) and Classic Computer Science Problems in Swift (Manning, 2018).
combo $39.99 pBook + eBook + liveBook
eBook $31.99 pdf + ePub + kindle + liveBook
Add liveAudio for only $19.99
Prices displayed in rupees will be charged in USD when you check out.

placing your order...

Don't refresh or navigate away from the page.
customers also bought
Grokking Algorithms
An illustrated guide for programmers and other curious people
Aditya Y. Bhargava
Deep Learning with Python
François Chollet
Python Workout
50 Essential Exercises
Reuven M. Lerner
Exploring Data with Python
With chapters selected by Naomi Ceder
Grokking Deep Learning
Andrew W. Trask
Deep Learning and the Game of Go
Max Pumperla and Kevin Ferguson
Foreword by Thore Graepel
Math for Programmers
3D graphics, machine learning, and simulations with Python
Paul Orland
The Quick Python Book, Third Edition
Naomi Ceder
Foreword by Nicholas Tollervey
Practices of the Python Pro
Dane Hillard
The Design of Web APIs
Arnaud Lauret
GANs in Action
Deep learning with Generative Adversarial Networks
Jakub Langr and Vladimir Bok
Natural Language Processing in Action
Understanding, analyzing, and generating text with Python
Hobson Lane, Cole Howard, Hannes Hapke
Foreword by Dr. Arwen Griffioen

FREE domestic shipping on three or more pBooks

related titles