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.