Classic Computer Science Problems in Swift: Essential Techniques for Practicing Programmers

Classic Computer Science Problems in Swift: Essential Techniques for Practicing Programmers

by David Kopec

Paperback

$37.90 $39.99 Save 5% Current price is $37.9, Original price is $39.99. You Save 5%.
Choose Expedited Shipping at checkout for guaranteed delivery by Wednesday, January 23

Product Details

ISBN-13: 9781617294891
Publisher: Manning Publications Company
Publication date: 04/22/2018
Pages: 224
Sales rank: 663,818
Product dimensions: 7.30(w) x 8.70(h) x 0.50(d)

About the Author

David Kopec is an Assistant Professor of Computer Science & Innovation at Champlain College in Burlington, VT. He is an experienced iOS developer and the author of Dart for Absolute Beginners.

Table of Contents

Acknowledgments xiii

About this book xv

Introduction 1

1 Small problems 5

1.1 The Fibonacci sequence 5

A first recursive attempt 5

Utilizing base cases 7

Memoization to the rescue 8

Keep it simple, Fibonacci 9

1.2 Trivial compression 10

1.3 Unbreakable encryption 13

Getting the data in order 14

Encrypting and decrypting 15

1.4 Calculating pi 16

1.5 The Towers of Hanoi 17

Modeling the towers 18

Solving The Towers of Hanoi 18

1.6 Real-world applications 20

1.7 Exercises 21

2 Search problems 22

2.1 DNA search 22

Storing DNA 23

Linear search 24

Binary search 25

A generic example 27

2.2 Maze solving 28

Generating a random maze 28

Miscellaneous maze minutiae 29

Depth-first search 30

Breadth-first search 34

A* search 37

2.3 Missionaries and cannibals 41

Representing the problem 42

Solving 44

2.4 Real-world applications 45

2.5 Exercises 46

3 Constraint-satisfaction problems 47

3.1 Building a constraint-satisfaction problem framework 48

3.2 The Australian map-coloring problem 52

3.3 The eight queens problem 55

3.4 Word search 57

3.5 Send+More=Money 61

3.6 Circuit board layout 62

3.7 Real-world applications 63

3.8 Exercises 64

4 Graph problems 65

4.1 Building a graph framework 67

A concrete implementation of Edge 72

A concrete implementation of Graph 72

4.2 Finding the shortest path 75

Defining a path 75

Revisiting breadth-first search (BFS) 75

4.3 Minimizing the cost of building the network 78

Workings with weights 78

Finding the minimum spanning tree 83

4.4 Finding shortest paths in a weighted graph 88

Dijkstra's algorithm 89

4.5 Real-world applications 93

4.6 Exercises 94

5 Genetic algorithms 95

5.1 Biological background 95

5.2 Preliminaries 96

5.3 A generic genetic algorithm 98

5.4 A naive test 105

5.5 Send+More=Money revisited 107

5.6 Challenges for genetic algorithms 111

5.7 Real-world applications 111

5.8 Exercises 112

6 K-means clustering 113

6.1 Preliminaries 113

6.2 The k-means clustering algorithm 117

6.3 Clustering governors by age and longitude 122

6.4 K-means clustering problems and extensions 126

6.5 Real-world applications 127

6.6 Exercises 128

7 Fairly simple neural networks 129

7.1 Biological basis? 130

7.2 Artificial neural networks 131

Neurons 131

Layers 132

Backpropagation 133

The big picture 136

7.3 Preliminaries 137

Help with randomization 137

Fast arithmetic 138

7.4 The activation function 140

7.5 Building the network 141

Implementing neurons 141

Implementing layers 143

Implementing the network 144

7.6 Classification problems 147

Normalizing data 148

The classic iris data set 148

Classifying wine 152

7.7 Neural network problems and extensions 154

7.8 Real-world applications 155

7.9 Exercises 156

8 Miscellaneous problems 157

8.1 The knapsack problem 157

8.2 The traveling salesman problem 162

The naive approach 162

Taking it to the next level 167

8.3 Phone number mnemonics 168

8.4 Tic-tac-toe 170

Managing state 170

Minimax 173

8.5 Real-world applications 176

8.6 Exercises 177

Appendix A Glossary 179

Appendix B More resources 184

Aappendix C A brief history of Swift 189

Index 197

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews