Classic Computer Science Problems in Java

by David Kopec

Overview

Sharpen your coding skills by exploring established computer science problems! Classic Computer Science Problems in Java challenges you with time-tested scenarios and algorithms.

Summary
Sharpen your coding skills by exploring established computer science problems! Classic Computer Science Problems in Java challenges you with time-tested scenarios and algorithms. You’ll work through a series of exercises based in computer science fundamentals that are designed to improve your software development abilities, improve your understanding of artificial intelligence, and even prepare you to ace an interview. 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
Whatever software development problem you’re facing, odds are someone has already uncovered a solution. This book collects the most useful solutions devised, guiding you through a variety of challenges and tried-and-true problem-solving techniques. The principles and algorithms presented here are guaranteed to save you countless hours in project after project.

About the book
Classic Computer Science Problems in Java is a master class in computer programming designed around 55 exercises that have been used in computer science classrooms for years. You’ll work through hands-on examples as you explore core algorithms, constraint problems, AI applications, and much more.

What's inside

Recursion, memoization, and bit manipulation
Search, graph, and genetic algorithms
Constraint-satisfaction problems
K-means clustering, neural networks, and adversarial search

About the reader
For intermediate Java programmers.

About the author
David Kopec is an assistant professor of Computer Science and Innovation at Champlain College in Burlington, Vermont.

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
10 Interview with Brian Goetz

Product Details

ISBN-13:	9781617297601
Publisher:	Manning
Publication date:	01/19/2021
Pages:	264
Product dimensions:	7.20(w) x 9.10(h) x 0.60(d)

About the Author

David Kopec teaches at Champlain College in Burlington, VT and is the author of Manning’s Classic Computer Science Problems in Swift.

Table of Contents

Acknowledgments xiii

About this book xv

About the author xvi

About the cover illustration xvii

Introduction 1

0.1 Who should read this book 2

0.2 How this book is organized: A roadmap 3

0.3 About the code 4

0.4 Other online resources 5

1 Small problems 7

1.1 The Fibonacci sequence 7

A first recursive attempt 7

Utilizing base cases 9

Memoization to the rescue 10

Keep it simple, Fibonacci 12

Generating Fibonacci numbers with a stream 13

1.2 Trivial compression 13

1.3 Unbreakable encryption 18

Getting the data in order 18

Encrypting and decrypting 19

1.4 Calculating pi 21

1.5 The Towers of Hanoi 22

Modeling the towers 23

Solving The Towers of Hanoi 23

1.6 Real-world applications 25

1.7 Exercises 26

2 Search problems 27

2.1 DNA search 27

Storing DNA 27

Linear search 30

Binary search 31

A generic example 33

2.2 Maze solving 35

Generating a random maze 37

Miscellaneous maze minutiae 38

Depth-first search 39

Breadth-first search 44

A* search 47

2.3 Missionaries and cannibals 52

Representing the problem 53

Solving 55

2.4 Real-world applications 58

2.5 Exercises 58

3 Constraint-satisfaction problems 59

3.1 Building a constraint-satisfaction problem framework 60

3.2 The Australian map-coloring problem 64

3.3 The eight queens problem 67

3.4 Word search 70

3.5 SEND+MORE=MONEY 76

3.6 Circuit board layout 77

3.7 Real-world applications 78

3.8 Exercises 79

4 Graph problems 80

4.1 A map as a graph 80

4.2 Building a graph framework 83

Working with Edge and UnweightedGraph 88

4.3 Finding the shortest path 89

Revisiting breadth-first search (BFS) 89

4.4 Minimizing the cost of building the network 91

Working with weights 91

Finding the minimum spanning tree 95

4.5 Finding shortest paths in a weighted graph 100

Dijkstra's algorithm 100

4.6 Real-world applications 105

4.7 Exercises 106

5 Genetic algorithms 107

5.1 Biological background 107

5.2 A generic genetic algorithm 108

5.3 A naive test 116

5.4 SEND+MORE=MONEY revisited 118

5.5 Optimizing list compression 122

5.6 Challenges for genetic algorithms 125

5.7 Real-world applications 126

5.8 Exercises 127

6 K-means clustering 128

6.1 Preliminaries 129

6.2 The k-means clustering algorithm 131

6.3 Clustering governors by age and longitude 138

6.4 Clustering Michael Jackson albums by length 142

6.5 K-means clustering problems and extensions 144

6.6 Real-world applications 145

6.7 Exercises 145

7 Fairly simple neural networks 146

7.1 Biological basis? 147

7.2 Artificial neural networks 148

Neurons 148

Layers 149

Backpropagation 150

The big picture 154

7.3 Preliminaries 154

Dot product 154

The activation function 155

7.4 Building the network 156

Implementing neurons 157

Implementing layers 158

Implementing the network 160

7.5 Classification problems 163

Normalizing data 164

The classic iris data set 165

Classifying wine 169

7.6 Speeding up neural networks 172

7.7 Neural network problems and extensions 173

7.8 Real-world applications 174

7.9 Exercises 175

8 Adversarial search 176

8.1 Basic board game components 176

8.2 Tic-tac-toe 178

Managing tic-tac-toe state 178

Minimax 182

Testing minimax with tic-tac-toe 185

Developing a tic-tac-toe AI 187

8.3 Connect Four 189

Connect Four game machinery 189

A Connect Four AI 195

Improving minimax with alpha-beta pruning 197

8.4 Minimax improvements beyond alpha-beta pruning 198

8.5 Real-world applications 199

8.6 Exercises 200

9 Miscellaneous problems 201

9.1 The knapsack problem 201

9.2 The Traveling Salesman Problem 206

The naive approach 207

Taking it to the next level 213

9.3 Phone number mnemonics 213

9.4 Real-world applications 216

9.5 Exercises 216

10 Interview with Brian Goetz 218

Appendix A Glossary 232

Appendix B More resources 238

Index 241