Computing without Computers

This textbook takes an ‘unplugged’ approach to learning the critical concepts in computer science. It relies heavily on metaphors as a means for readers to grasp new topics and relate them to their current understanding. It also contains puzzles which aid understanding.

The book includes chapters covering:

• Programs and algorithms, including basic understanding of algorithms and lots of real-world examples of rule-based situations

• Programming languages, including the need to avoid ambiguity and the avoidance of errors in high-level languages. Also compilers and machine code are explained. Real world metaphors such as jigsaws, giving directions or going shopping are provided.

• Sequences.

• Variables, their declaration and their assignment are illustrated using a game of chess. Various data types and expressions are covered including Boolean, with numerous metaphors including the works of Shakespeare and putting up shelves!

• Selection in programs, including branched and nested IF and ELIF statements,

• Iteration and recursion, including WHILE and FOR loop execution and break conditions. An ongoing example of a maze is used to illustrate generalisable statements. Nesting of loops is explained, and decomposition is used as a means to spot patterns to create generalised statements. Recursion is explained in simplistic terms using pseudocode, and avoiding discussion of coding.

• Functions and procedures, and comments in code. Decomposition is once again illustrated using a range of real world examples, such as complex pizza recipes. Parameter parsing is explained, again in the context of cookery.

• Input and output is related to human communication and memory. Libraries and the stories they contain are a model for persistent storage, while letters in the sand represent non-persistent storage. Buffers are explained also.

• Object-oriented programming is contrasted to procedural programming referenced in the early examples. Multiple metaphors ensure that classes, objects, attributes and other features of OOP are understood in terms of abstraction. Polymorphism is explained as is inheritance and overloading.

The second part of the book covers data structures including:

• Lists and circular lists
• Arrays, including multidimensional arrays, look-up tables, adjacency matrices,
• Records
• Queues and stacks, including FIFO, LIFO and priority queues,
• Dynamic data structures such as linked lists, trees, graphs, Random access and serial access data structures,

The third part goes deeper into algorithms, including:

• Linear search using games
• Binary search, illustrated with many examples
• Tree searching
• Bucket searches and hash tables
• Sorting algorithms, including bucket sort, straight selection sort, bubblesort, binary bucket sort, radix sort, tree sorting, merge sort, indexes.
• Path algorithms illustrated by Richard Feynman following ants in the bath.
• Choosing algorithms by time; speed vs space; pre-processing; accuracy