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 LearnThink 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.
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) . . . . . . . . . . . . . . . 50
Using 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 . . . . . . . . . . . . . . . . 293
Recursion stacks . . . . . . . . . . . . . . . . . . 297
Recursion and iteration . . . . . . . . . . . . . . 307
Tail-calls . . . . . . . . . . . . . . . . . . . . . . 316
Continuations . . . . . . . . . . . . . . . . . . . 324
Continuations, thunks and trampolines . . . . . . 335
9 Divide and conquer and dynamic programming 343
Divide 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 537
Sequences . . . . . . . . . . . . . . . . . . . . . 538
Linked lists sequences . . . . . . . . . . . . . . . 540
Doubly linked lists . . . . . . . . . . . . . . . . . 560
A word on garbage collection . . . . . . . . . . . 579
Iterators . . . . . . . . . . . . . . . . . . . . . . 587
Python iterators and other interfaces . . . . . . . 590
Generators . . . . . . . . . . . . . . . . . . . . . 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 . . . . . . . . . . 782
Leftist heaps . . . . . . . . . . . . . . . . . . . . 786
Binomial heaps . . . . . . . . . . . . . . . . . . . 794
Binary heaps . . . . . . . . . . . . . . . . . . . . 814
Adding keys and values . . . . . . . . . . . . . . 825
Comparisons . . . . . . . . . . . . . . . . . . . . 842
Human encoding . . . . . . . . . . . . . . . . . 846
18 Conclusions 853
Where to go from here . . . . . . . . . . . . . . 855
Show more
