The CTP Book

A book for teaching Computational Thinking and Programming skills to people with a background in the Humanities

View on GitHub

Computational Thinking and Programming

This is the official book originally written by Silvio Peroni for the Computational Thinking and Programming course of the second-cycle degree in Digital Humanities and Digital Knowledge of the University of Bologna. The intent of this book was to have open and free material to provide to students to learn the basics of Computational Thinking and Code Programming in Python.

It includes several Python sources, exercises and the related keys. Each chapter starts by introducing an historic hero (either computer scientists, writers, philosophers, or computational agents) who is functional to discuss the main topic addressed in the chapter.

Also, the book is accompanied by additional material and exercises so as to improve computational thinking skills and Python programming.

Please do not hesitate to contact the author for any suggestion and comment on the book on Twitter or by email.

Table of Contents

  1. Introduction to Computational Thinking [PDF] [Google Docs]
    Historic hero: Noam Chomsky

  2. Algorithms [PDF] [Google Docs]
    Historic hero: Ada Lovelace

  3. Computability [PDF] [Google Docs]
    Historic hero: Alan Turing

  4. Programming languages [PDF] [Google Docs]
    Historic hero: Grace Hopper

  5. Organising information: ordered structures [PDF] [Google Docs]
    Historic hero: Donald Knuth

  6. Brute-force algorithms [PDF] [Google Docs]
    Historic hero: Betty Holberton

  7. Organising information: unordered structures [PDF] [Google Docs]
    Historic hero: Jorge Luis Borges

  8. Recursion [PDF] [Google Docs]
    Historic hero: Douglas Hofstadter

  9. Divide and conquer algorithms [PDF] [Google Docs]
    Historic hero: John von Neumann

  10. Dynamic programming algorithms [PDF] [Google Docs]
    Historic hero: Leonardo da Pisa

  11. Organising information: trees [PDF] [Google Docs]
    Historic hero: Gabriel García Márquez

  12. Backtracking algorithms [PDF] [Google Docs]
    Historic hero: AlphaGo

  13. Organising information: graphs [PDF] [Google Docs]
    Historic hero: Leonhard Euler

  14. Greedy algorithms [PDF] [Google Docs]
    Historic hero: Evelyn Berezin

Python code available in each chapter

  1. None
  2. None
  3. None
  4. first_algorithm_empty.py, first_algorithm_no_assignments.py, first_algorithm.py
  5. define_functions.py, list_instructions.py, stack_instructions.py, queue_instructions.py
  6. stack_from_list.py, run_forever.py, linear_search.py, insertion_sort.py
  7. set_instructions.py, dictionary_instructions.py
  8. run_forever_recursive.py, multiplication.py
  9. immutable_values.py, mutable_values.py, immutable_and_mutable_variables.py, merge.py, merge_sort.py
  10. fib_dc.py, fib_dp.py
  11. tree_instructions.py
  12. peg_solitaire.py
  13. graph_instructions.py, multigraph_instructions.py, graph_attribute_instructions.py
  14. line_wrap.py

Keys of the exercises in each chapter

  1. Exercises 1, 2, 3
  2. Exercises 1, 2, 3
  3. Exercises 1, 2, 3
  4. Exercises 1, 2, 3
  5. Exercises 1, 2, 3
  6. Exercises 1, 2, 3, 4, 5
  7. Exercises 1, 2, 3
  8. Exercises 1, 2
  9. Exercises 1, 2, 3
  10. Exercises 1, 2
  11. Exercises 1, 2
  12. Exercises 1, 2
  13. Exercises 1, 2
  14. Exercises 1, 2

Additional exercises

The exercises in this section focus in enhancing the two main activities that concern the learning of a new language (including a programming language), i.e. understanding something written in a certain language, and using such language to develop a new artifact. All the exercises proposed herein are split according to three distinct and increasing levels: beginner, intermediate, advanced.

Understanding

The exercises of this section focus on figuring out the execution of a particular piece of Python code according to a given input. The goal is to test a user to act as an electronic computer when executing a certain Python function. All the exercises of this section are accompanied by the related executable code, which allows one to test what is the output of the functions considering the particular input one can specify through the shell.

Development

The exercises of this section focus on creating a Python function according to a natural language description of its input, output, and behaviour. The goal is to test a user to write a program that can be interpreted by an electronic computer. All the exercises of this section are accompanied by the related executable code, which includes also the tests created as part of the test-driven development methodology introduced in chapter “Programming Language”. This chapter also introduces a possible methodology to follow for the development of an algorithm as a Python function, that can be used as basis to solve the exercises in this section.

Additional material

Atari Go: A DIY version of a famous variant of Go which is useful to learn the basics of the game. It is also available (and citable) on Zenodo:

Peroni, S. (2018). Atari Go. Version 1.0.1. Zenodo. https://doi.org/10.5281/zenodo.2222272

IDEA instructions: binary search: A nonverbal definition of the binary search algorithm, created by Sándor P. Fekete and Sebastian Morr. It is also available in the IDEA website.

IDEA instructions: merge sort: A nonverbal definition of the merge sort algorithm, created by Sándor P. Fekete and Sebastian Morr. It is also available in the IDEA website.

IDEA instructions: quick sort: A nonverbal definition of the quick sort algorithm, created by Sándor P. Fekete and Sebastian Morr. It is also available in the IDEA website.

License

All the documents (chapters, exercises, etc.) are released under a Creative Commons Attribution 4.0 International (CC BY 4.0). For all the third party material used in any document, the license explicitly specified on such material is used.

All the software has been released with an ISC License.

All the data are released under a CC0 1.0 Universal (CC0 1.0) - Public Domain Dedication.

The licenses mentioned above apply to all the entities unless otherwise specified. More information about the licenses are available on the GitHub repository of the book.