Introduction to Computational Thinking

Learn approaches of computational thinking and the art of designing algorithms. Most of the algorithms you will see in this book are used in almost all software that runs on your computer.

Learning how to program can be very rewarding. It is a special feeling to seeing a computer translate your thoughts into actions and see it solve your problems for you. To get to that point, however, you must learn to think about computations in a new way—you must learn computational thinking.

This book begins by discussing models of the world and how to formalize problems. This leads onto a definition of computational thinking and putting computational thinking in a broader context. The practical coding in the book is carried out in Python; you’ll get an introduction to Python programming, including how to set up your development environment.

WHAT YOU WILL LEARN

* Think in a computational way
* Acquire general techniques for problem solving
* See general and concrete algorithmic techniques
* Program solutions that are both computationally efficient and maintainable

WHO THIS BOOK IS FOR

Those new to programming and computer science who are interested in learning how to program algorithms and working with other computational aspects of programming.

Thomas Mailund, PhD is an associate professor in bioinformatics at Aarhus University, Denmark. He has a background in math and computer science, including experience programming and teaching in the C, Python and R programming languages. For the last decade, his main focus has been on genetics and evolutionary studies, particularly comparative genomics, speciation, and gene flow between emerging species.

1 Introduction 1

Models of the world and formalising problems . . 4

What is computational thinking? . . . . . . . . . 6

Computational thinking in a broader context . . . 12

What is to come . . . . . . . . . . . . . . . . . . 15

2 Introducing Python programming 19

Obtaining Python . . . . . . . . . . . . . . . . . 20

Running Python . . . . . . . . . . . . . . . . . . 22

Expressions in Python . . . . . . . . . . . . . . . 22

Logical (or boolean) expressions . . . . . . . . . . 26

Variables . . . . . . . . . . . . . . . . . . . . . . 30

Working with strings . . . . . . . . . . . . . . . . 32

Lists . . . . . . . . . . . . . . . . . . . . . . . . 36

Tuples . . . . . . . . . . . . . . . . . . . . . . . 41

iii

Sets and dictionaries . . . . . . . . . . . . . . . . 42

Input and output . . . . . . . . . . . . . . . . . . 44

Conditional statements (if statements) . . . . . . 47

Loops (for and while) . . . . . . . . . . . . . . . 50Using modules . . . . . . . . . . . . . . . . . . . 54

3 Introduction to algorithms 57

Designing algorithms . . . . . . . . . . . . . . . 62

Exercises for sequential algorithms . . . . . . . . 81

Exercises on lists . . . . . . . . . . . . . . . . . . 87

4 Algorithmic eciency 95

The RAM model of a computer and its primitive

operations . . . . . . . . . . . . . . . . . . 97

Types of eciency . . . . . . . . . . . . . . . . . 107

Asymptotic running time and big-Oh notation . . 116

Empirically validating an algorithms running time 135

5 Searching and sorting 141

Searching . . . . . . . . . . . . . . . . . . . . . . 142

Sorting . . . . . . . . . . . . . . . . . . . . . . . 147

Generalising searching and sorting . . . . . . . . 182

How computers represent numbers . . . . . . . . 186

6 Functions 197

Parameters and local and global variables . . . . . 203

Side eects . . . . . . . . . . . . . . . . . . . . . 210

Returning from a function . . . . . . . . . . . . . 215

Higher order functions . . . . . . . . . . . . . . . 221

Functions vs function instances . . . . . . . . . . 227

Default parameters and keyword arguments . . . 230

Generalising parameters . . . . . . . . . . . . . . 234

Exceptions . . . . . . . . . . . . . . . . . . . . . 239

Writing your own Python modules . . . . . . . . 251

7 Inner functions 253

A comparison function for a search algorithm . . 256

Counter function . . . . . . . . . . . . . . . . . . 261

Apply . . . . . . . . . . . . . . . . . . . . . . . . 265

Currying functions . . . . . . . . . . . . . . . . . 269

Function composition . . . . . . . . . . . . . . . 274

Thunks and lazy evaluation . . . . . . . . . . . . 276

Decorators . . . . . . . . . . . . . . . . . . . . . 281

Eciency . . . . . . . . . . . . . . . . . . . . . . 288

8 Recursion 291

Denitions of recursion . . . . . . . . . . . . . . 291

Recursive functions . . . . . . . . . . . . . . . . 293Recursion stacks . . . . . . . . . . . . . . . . . . 297

Recursion and iteration . . . . . . . . . . . . . . 307

Tail-calls . . . . . . . . . . . . . . . . . . . . . . 316

Continuations . . . . . . . . . . . . . . . . . . . 324

Continuations, thunks and trampolines . . . . . . 335

9 Divide and conquer and dynamic programming 343Divide and conquer running times . . . . . . . . 355

Dynamic programming . . . . . . . . . . . . . . 371

Representing oating point numbers . . . . . . . 392

10 Hidden Markov models 399

Probabilities . . . . . . . . . . . . . . . . . . . . 399

Conditional probabilities and dependency graphs . 410

Markov models . . . . . . . . . . . . . . . . . . . 412

Hidden Markov models . . . . . . . . . . . . . . 421

Forward algorithm . . . . . . . . . . . . . . . . . 425

Viterbi algorithm . . . . . . . . . . . . . . . . . . 433

11 Data structures, objects and classes 439

Classes . . . . . . . . . . . . . . . . . . . . . . . 441

Exceptions and classes . . . . . . . . . . . . . . . 448

Methods . . . . . . . . . . . . . . . . . . . . . . 453

Magical methods . . . . . . . . . . . . . . . . . . 460

Class variables . . . . . . . . . . . . . . . . . . . 464

Objects, classes, meta-classes, and attributes . . . 471

Return of the decorator . . . . . . . . . . . . . . 494

Polymorphism . . . . . . . . . . . . . . . . . . . 500

Abstract data structures . . . . . . . . . . . . . . 504

12 Class hierarchies and inheritance 507

Inheritance and code reuse . . . . . . . . . . . . 516

Multiple inheritance . . . . . . . . . . . . . . . . 524

Mixins . . . . . . . . . . . . . . . . . . . . . . . 532

13 Sequences 537Sequences . . . . . . . . . . . . . . . . . . . . . 538

Linked lists sequences . . . . . . . . . . . . . . . 540

Doubly linked lists . . . . . . . . . . . . . . . . . 560

A word on garbage collection . . . . . . . . . . . 579

Iterators . . . . . . . . . . . . . . . . . . . . . . 587

Python iterators and other interfaces . . . . . . . 590Generators . . . . . . . . . . . . . . . . . . . . . 598

14 Sets 607

Sets with builtin lists . . . . . . . . . . . . . . . . 612

Linked lists sets . . . . . . . . . . . . . . . . . . . 618

Search trees . . . . . . . . . . . . . . . . . . . . 620

Hash table . . . . . . . . . . . . . . . . . . . . . 648

Dictionaries . . . . . . . . . . . . . . . . . . . . 663

15 Red-black search trees 669

A persistent recursive solution . . . . . . . . . . . 670

An iterative solution . . . . . . . . . . . . . . . . 712

16 Stacks and queues 739

Building stacks and queues from scratch . . . . . 745

Expression stacks and stack machines . . . . . . . 748

Quick-sort and the call stack . . . . . . . . . . . . 761

Writing an iterator for a search tree . . . . . . . . 763

Merge sort with an explicit stack . . . . . . . . . . 768

Breadth-rst tree traversal and queues . . . . . . 775

17 Priority queues 779

A tree representation for a heap . . . . . . . . . . 782Leftist heaps . . . . . . . . . . . . . . . . . . . . 786

Binomial heaps . . . . . . . . . . . . . . . . . . . 794

Binary heaps . . . . . . . . . . . . . . . . . . . . 814

Adding keys and values . . . . . . . . . . . . . . 825

Comparisons . . . . . . . . . . . . . . . . . . . . 842

Human encoding . . . . . . . . . . . . . . . . . 84618 Conclusions 853

Where to go from here . . . . . . . . . . . . . . 855