Introduction (6 pages)
In the Introduction, the goals are to: sell the book, set expectations for what knowledge it will provide, and explain its structure. Swift is a new language, so part of selling the book is selling the language. Readers who are anxious about their ability to follow along throughout the book (as may be the case with students and those with little computer science experience) have their minds put at ease by how little prior knowledge is assumed (that being the basics of Swift programming). The target audience is further defined through the use of example readers. Tips for getting the most out of the structure of the book are presented.
1) Why Swift?
2) What is a classic computer science problem?
3) Who is this book for?
4) Swift Versioning and Tools
5) No Graphics, no UI Code
Chapter 1: Small Problems (24 pages)
The reader needs some basic tools and techniques in order to follow the rest of the book. Recursion, dynamic programming, memorization, and simulation are covered through several easily digested problems. The goal is to whet the reader's appetite without being overwhelming.
1) The Fibonacci Sequence
a. A First Recursive Attempt
b. Utilizing Base Cases
c. Memorization to the Rescue
d. Keep it Simple, Fibonacci
2) The Knapsack Problem
3) Unbreakable Encryption
a. Getting Our Data in Order
b. Encrypting and Decrypting
4) Calculating Pi
5) The Towers of Hanoi
a. Modeling the Towers
b. Solving the Towers of Hanoi
6) Exercises
Chapter 2: Search Problems (40 pages)
First elementary linear and binary search are presented. The tradeoffs of each are discussed. Then, depth-first search is presented as a means of solving grid based problems. Bread-first search is explained in contrast to depth-first search with an emphasis on how easy it is to change the original code of depth-first search to breadth-first search by swapping the stack for a queue. Finally, A* is presented as the ultimate algorithm for efficient search in many problems.
1) DNA Search
a. Storing DNA
b. Linear Search
c. Binary Search
d. A Generic Example
2) Maze Solving
a. Generating a Random Maze
b. Miscellaneous Maze Minutiae
c. Depth-First Search i. Stacks
ii. The DFS Algorithm
d. Breadth-First Search
i. Queues
ii. The BFS Algorithm
e. A* Search
i. PriorityQueues
ii. Heuristics
1. Euclidean Distance
2. Manhattan Distance
iii. The A* Algorithm
3) Missionaries and Cannibals
a. Representing the Problem
b. Solving
4) Exercises
Chapter 3: Constraint Satisfaction Problems (25 pages)
Constraints satisfaction problems are explained as a combination of variables, domain, and constraints. A framework for constructing them and solving them using a simple backtracking approach and a simple object-oriented constraint class hierarchy is presented. The framework is then used to solve several famous constraint satisfaction problems.
1) Building a Constraint Satisfaction Problem Framework
2) The Australian Map Coloring Problem
3) The Eight Queens Problem
4) Word Search
5) SEND+MORE=MONEY
6) Circuit Board Layout
7) Exercises
Chapter 4: Graph Problems (20 pages)
The reader learns about graphs. What is a vertex and what is an edge? What do graphs look like? The open source framework SwiftGraph is presented. Some of its code is explored. SwiftGraph is used as a tool for solving several graph problems.
1) What is a graph?
2) SwiftGraph
3) Nine Tails
4) The Bridges of Konigsberg
5) Exercises
Chapter 5: Genetic Algorithms (30 pages)
Evolutionary computation and genetic algorithms are explained in detail with concentration on implementing a generic genetic algorithm that uses a fitness function, crossover, mutation, recombination, reproduction, and selection to solve problems. Tradeoffs between genetic algorithms and more traditional approaches to problem solving are explored.
1) Natural Selection
2) A Generic Genetic Algorithm
a. Population
b. Crossover
c. Mutation
d. Fitness Function
3) Old Searches with a Genetic Algorithm
4) The Traveling Salesman Problem
a. Naive Approach
i. NP-Completeness
b. Genetic Algorithm Approach
5) Exercises
Chapter 6: K-Means Clustering (15 pages)
K-Means clustering is explained in detail as a means of classification. The algorithm is used to classify a set of pre-built data about music albums. The classification is then tried again using several different configurations of the algorithm.
1) The K-means Clustering Algorithm
2) Classifying Music
3) Experimenting with Different Initial Setups
4) Exercises
Chapter 7: Fairly Simple Neural Networks (25 pages)
The goal is not to present an expansive introduction to this broad and hot topic, but instead to allow the reader to see how a simple network can be built from scratch using some fundamental building blocks. Theory is touched on, but practical predictive classification is the end goal.
1) What is a neural network?
a. Machine Learning
b. Different Types
2) Building a Simple Network
3) Classifying Irises
4) Classifying Wines
5) Exercises
Chapter 8: Miscellaneous Problems (15 pages)
Fun or interesting problems that didn't quite fit in another chapter are gathered here.
1) The Monty Hall Problem
2) The Knight's Tour
3) 15-Puzzle
4) Exercises
Appendix A: Glossary (4 pages)
All of the terms written in italics throughout the book are defined in one place here.
Appendix B: Further Resources (6 pages)
Books and online resources that delve deeper into particular topics of computer science and/or Swift are presented.
