M269.pdf

Algorithms, data structures and computability Michel Wermelinger 15 August 2023 CONTENTS 1 Introduction 1.1 What to expect........... 1.1.1 Content.......... 1.1.2 Challenges........ 1.1.3 Previous knowledge.... 1.2 How to study............ 1.2.1 Book........... 1.2.2 Mindset.......... 1.2.3 Time allocation...... 1.2.4 Study techniques..... 1.3 Software.............. 1.3.1 Using the VCE...... 1.3.2 Installing the software.. 1.3.3 Switching to notebooks.. 1.4 Notebooks............. 1.4.1 Interface.......... 1.4.2 Reverting to a checkpoint. 1.4.3 Running cells....... 1.4.4 Closing notebooks.... 1.5 Text cells.............. 1.5.1 Basic formatting..... 1.5.2 Lists............ 1.5.3 Tables........... 1.5.4 Mathematical notation.. 1.5.5 Adding study notes.... 1.5.6 Adding cells........ 1.6 Code cells............. 1.6.1 Executing code...... 1.6.2 Software check...... 1.6.3 Autocompleting...... 1.6.4 Changing the indentation. 1.6.5 Finding and replacing text 1.6.6 Commenting code out................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... 3 4 4 5 6 7 7 10 10 11 12 13 15 15 19 20 21 22 23 25 25 26 27 28 28 30 30 30 32 33 34 35 37 i 1.7 2 3 ii 1.6.7 Copying cells.... Summary........... 1.7.1 Notebooks...... 1.7.2 Common commands 1.7.3 Command mode... 1.7.4 Edit mode.................. Numbers and sequence 2.1 Numbers............. 2.1.1 Integers and real numbers 2.1.2 int and float literals. 2.1.3 Mistakes......... 2.2 Arithmetic operations...... 2.2.1 On real numbers.... 2.2.2 On integers....... 2.2.3 On int and float... 2.2.4 On float........ 2.2.5 On int......... 2.2.6 Mistakes......... 2.3 Expressions............ 2.3.1 Mistakes......... 2.4 Assignments........... 2.4.1 Algorithms....... 2.4.2 Names.......... 2.4.3 Mistakes......... 2.5 Functions in mathematics.... 2.5.1 Example......... 2.5.2 Algorithms....... 2.5.3 Mistakes......... 2.6 Functions in Python....... 2.6.1 Documentation..... 2.6.2 Mistakes......... 2.6.3 Optional exercises.... 2.7 Complexity............ 2.7.1 Constant complexity.. 2.7.2 Linear complexity.... 2.7.3 Mistakes......... 2.8 Run-times............. 2.8.1 Checking growth rates. 2.9 Summary............. 2.9.1 Python.......... 2.9.2 Data types........ 2.9.3 Functions........ 2.9.4 Complexity................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... 38 39 39 40 40 41.................................... 43 44 44 45 46 47 48 48 49 50 50 51 52 54 55 55 56 57 59 61 62 63 64 66 67 70 70 71 72 73 74 76 79 79 79 81 82 Booleans and selection 83 3.1 Booleans..................................... 84 3.1.1 The Boolean ADT........................... 84 3.2 3.3 3.4 3.5 3.6 4 3.1.2 Using Booleans......... 3.1.3 The bool type.......... 3.1.4 Mistakes............. Decision problems............ 3.2.1 Problem definition....... 3.2.2 Problem instances........ 3.2.3 Algorithm............ 3.2.4 Complexity........... 3.2.5 Code and tests.......... 3.2.6 Performance........... Boolean expressions........... 3.3.1 Comparisons.......... 3.3.2 Mistakes............. Classification problems......... 3.4.1 Problem definition and instances 3.4.2 Algorithm............ 3.4.3 Complexity........... 3.4.4 Code............... 3.4.5 Tests............... 3.4.6 Performance........... 3.4.7 Mistakes............. Practice.................. 3.5.1 Phone calls........... 3.5.2 Maximum............ 3.5.3 Leap year............ 3.5.4 Optional exercises........ Summary................. 3.6.1 Booleans............ 3.6.2 Solving problems........ 3.6.3 Classification problems..... Sequences and iteration 4.1 The Sequence ADT..... 4.1.1 Inspecting sequences 4.1.2 Creating sequences. 4.2 Strings............ 4.2.1 Literals....... 4.2.2 Inspecting strings.. 4.2.3 Creating strings... 4.3 Iteration............ 4.3.1 For-loops...... 4.3.2 While-loops..... 4.3.3 Repeat-loops.... 4.3.4 Nested loops.... 4.3.5 Optional exercises.. 4.4 Linear search......... 4.4.1 Finding characters.. 4.4.2 Valid password........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... 86 87 88 89 89 90 91 92 92 93 94 94 96 98 99 100 104 104 106 107 107 108 108 109 110 111 111 111 112 113................................................................................................................................................................................................................................................................................................................................ 115 116 116 119 121 121 123 127 130 131 133 135 136 137 137 138 141 iii 4.5 Tuples and tables.......... 4.5.1 Literals and operations.. 4.5.2 Mistakes.......... 4.5.3 Tables........... 4.5.4 Iterating.......... Lists................ 4.6.1 Modifying sequences... 4.6.2 Creating lists....... 4.6.3 Mistakes.......... 4.6.4 Modifying lists...... 4.6.5 Mistakes.......... Reversal.............. 4.7.1 Problem definition.... 4.7.2 Problem instances..... 4.7.3 Algorithm......... 4.7.4 Complexity........ 4.7.5 Code............ 4.7.6 Tests............ 4.7.7 Performance........ Optional practice.......... 4.8.1 DNA............ 4.8.2 Minimum......... 4.8.3 Lexicographic comparison 4.8.4 Palindrome........ 4.8.5 Mode........... 4.8.6 Images........... 4.8.7 Kattis problems...... Summary.............. 4.9.1 Sequence operations... 4.9.2 IPython.......... 4.9.3 Python........... 4.9.4 Problems......... 4.9.5 Complexity............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... 144 144 145 147 149 151 152 154 155 157 159 160 160 161 162 164 164 164 166 169 170 170 170 171 171 171 174 175 175 176 176 178 179 TMA 01 part 1 5.1 Problem definition......... 5.1.1 Problem and output names 5.1.2 Inputs and outputs..... 5.1.3 Preconditions....... 5.1.4 Postconditions....... 5.1.5 Test table......... 5.2 Algorithms and complexity.... 5.2.1 Linear search....... 5.2.2 Complexity........ 5.3 Coding style.................................................................................................................................................................................................................................................. 181 181 182 182 183 183 184 185 185 186 187 4.6 4.7 4.8 4.9 5 6 iv Implementing sequences 189 6.1 Defining data types................................ 190...................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... 191 191 192 195 200 202 204 206 208 208 211 213 214 215 216 218 219 220 221 221 224 224 224 229 231 232 232 233 234 234 Stacks and queues 7.1 Stacks................... 7.1.1 The stack ADT......... 7.1.2 Implementing with an array... 7.1.3 Implementing with a linked list. 7.2 Using stacks............... 7.2.1 Balanced brackets........ 7.2.2 Postfix expressions....... 7.3 Queues.................. 7.3.1 Single- and double-ended queues 7.3.2 Queues with Python lists.... 7.3.3 Deques in Python........ 7.3.4 Using queues.......... 7.4 Implementing queues........... 7.4.1 With a dynamic array...... 7.4.2 With a linked list........ 7.5 Implementing deques........................................................................................................................................................................................................................................................................................................................................... 235 235 236 237 239 241 241 244 246 246 247 248 249 251 251 253 254 6.2 6.3 6.4 6.5 6.6 6.7 6.8 7 6.1.1 Data structure......... 6.1.2 Functions........... 6.1.3 Classes............ 6.1.4 Mistakes............ Static arrays.............. 6.2.1 Variables and assignments.. 6.2.2 The StaticArray class... 6.2.3 Testing methods........ Developing data types......... 6.3.1 Abstract classes........ 6.3.2 Testing data types....... Bounded sequences.......... 6.4.1 Outlining algorithms..... 6.4.2 Insertion............ 6.4.3 The BoundedSequence class. Dynamic arrays............. 6.5.1 The DynamicArray class... 6.5.2 Tests.............. Using dynamic arrays......... 6.6.1 The ArraySequence class.. Linked lists............... 6.7.1 Traversing a linked list.... 6.7.2 Inserting an item....... 6.7.3 The LinkedSequence class. 6.7.4 Linked list v. array...... Summary................ 6.8.1 Classes............ 6.8.2 Data structures........ 6.8.3 Complexity.......... 6.8.4 Python............. v 7.6 7.7 8 9 vi 7.5.1 With a linked list.. 7.5.2 In Python...... Priority queues........ 7.6.1 With dynamic arrays: 7.6.2 With dynamic arrays: 7.6.3 With a linked list.. 7.6.4 Min-priority queues. Summary........... 7.7.1 Stacks........ 7.7.2 Queues....... 7.7.3 Priority queues..................... version 1. version 2..................................... Unordered collections 8.1 Maps.............. 8.1.1 The map ADT..... 8.1.2 Using maps...... 8.1.3 Lookup tables..... 8.2 Dictionaries.......... 8.2.1 Mistakes........ 8.2.2 Using dictionaries... 8.3 Hash tables........... 8.3.1 With separate chaining 8.3.2 Hash functions.... 8.3.3 Unhashable values.. 8.3.4 Complexity...... 8.3.5 Implementation.... 8.4 Sets............... 8.4.1 The set ADT..... 8.4.2 Sets in Python..... 8.4.3 Implementing sets... 8.4.4 Using sets....... 8.5 Bags.............. 8.5.1 The bag ADT..... 8.5.2 Implementing bags.. 8.6 Bags in Python......... 8.6.1 Mistakes........ 8.6.2 Using bags...... 8.7 Summary............ 8.7.1 Maps and dictionaries. 8.7.2 Lookup and hash tables 8.7.3 Sets.......... 8.7.4 Bags...................................................................................................................................................................................................................................... 254 257 257 258 259 262 262 263 264 264 265........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................ 267 267 268 268 270 272 275 277 279 279 282 284 285 286 288 288 289 291 292 294 294 295 297 299 300 302 302 302 303 304 Practice 1 9.1 Pangram.............. 9.1.1 Problem definition.... 9.1.2 Algorithm and complexity 9.1.3 Code and tests................................................................................................... 305 306 307 307 307............................. 9.2....................................................................................................................................................................................................................................................................................................................................................................................................... 308 308 309 309 309 310 311 311 312 313 313 313 315 315 315 316 319...................................................................................................................................................................................................................................... 321 321 322 322 323 323 324 324 324 326 327 11 Exhaustive search 11.1 Linear search, again.............. 11.1.1 Basic search.............. 11.1.2 Simultaneous and successive searches 11.1.3 Sorted candidates........... 11.2 Factorisation.................. 11.2.1 Make candidates explicit....... 11.2.2 Compute solutions.......... 11.2.3 Sort candidates............ 11.2.4 Prime numbers............ 11.3 Constraint satisfaction............. 11.3.1 Problem................ 11.3.2 Algorithm and complexity...... 11.3.3 Code and performance........ 11.3.4 Don’t generate equivalent candidates. 11.3.5 Reduce the range........... 11.3.6 Compute part of a candidate..... 11.3.7 Improved code and performance.................................................................................................................................................................................................................................................................................................... 329 330 330 332 333 334 335 337 338 341 341 342 342 343 345 345 346 346 9.3 9.4 9.5 9.6 Election............... 9.2.1 Problem definition.... 9.2.2 Algorithm and complexity 9.2.3 Code and tests....... Voucher............... 9.3.1 Algorithm and complexity 9.3.2 Code and tests....... Trains................ 9.4.1 Problem definition.... 9.4.2 Algorithm and complexity 9.4.3 Code and tests....... Browsing.............. 9.5.1 Tests............ 9.5.2 ADTs and code...... SMS................ 9.6.1 First approach....... 9.6.2 Second approach..... 10 TMA 01 part 2 10.1 Using collections....... 10.1.1 Ordered collections. 10.1.2 Unordered collections 10.2 Algorithms.......... 10.3 Coding style......... 10.4 Python............ 10.4.1 Language constructs 10.4.2 Built-in types.... 10.4.3 Standard library... 10.4.4 M269 Library.................................. vii 11.4 Searching permutations...... 11.4.1 Problem.......... 11.4.2 Algorithm......... 11.4.3 Complexity........ 11.4.4 Code............ 11.5 Searching subsets.......... 11.5.1 Problem.......... 11.5.2 Algorithm......... 11.5.3 Complexity........ 11.5.4 Code............ 11.6 Practice............... 11.6.1 Duplicates......... 11.6.2 Subset sum........ 11.6.3 Substring......... 11.6.4 PIN............ 11.7 Summary.............. 11.7.1 Problems......... 11.7.2 Complexities....... 11.7.3 Reducing the search space 11.7.4 Python........... 12 Recursion 12.1 The factorial function...... 12.1.1 Definition and algorithm 12.1.2 Code........... 12.1.3 The call stack...... 12.2 Recursion on integers...... 12.2.1 Algorithm........ 12.2.2 Recursive definition... 12.3 Length of a sequence....... 12.3.1 Recursive definition... 12.3.2 Code........... 12.3.3 Mistakes......... 12.4 Inspecting sequences....... 12.4.1 Maximum........ 12.4.2 Membership....... 12.4.3 Indexing......... 12.5 Creating sequences........ 12.5.1 Prepend......... 12.5.2 Linear search...... 12.5.3 Append and insert.... 12.6 Avoiding slicing......... 12.6.1 Problem definition... 12.6.2 Recursive definition... 12.6.3 Code........... 12.7 Subsets and permutations.... 12.7.1 Generating subsets... 12.7.2 Generating permutations viii...................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... 348 348 350 351 353 355 355 356 357 358 359 360 360 361 362 362 363 363 364 364...................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... 365 366 366 367 368 370 370 371 372 372 373 374 375 375 376 378 379 379 379 381 381 382 382 384 386 386 388 12.8 Multiple recursion.......... 12.8.1 Dividing the input...... 12.8.2 Designing multiple recursion 12.9 Summary................... 13 Divide and conquer 13.1 Decrease by one............ 13.1.1 Factorial............ 13.1.2 Sequence length........ 13.2 Decrease by half............ 13.2.1 Problem............ 13.2.2 Algorithm........... 13.2.3 Complexity.......... 13.2.4 Code and performance.... 13.3 Variable decrease............ 13.3.1 Problem............ 13.3.2 Algorithm........... 13.3.3 Complexity.......... 13.4 Binary search.............. 13.4.1 Recursive, with slicing.... 13.4.2 Recursive, without slicing.. 13.4.3 Iterative............ 13.5 Binary search variants......... 13.5.1 Transition........... 13.5.2 Right number in the right place 13.6 Divide and conquer........... 13.6.1 Complexity.......... 13.7 Summary................ 13.7.1 Complexity.......... 13.7.2 Binary search......... 14 Sorting 14.1 Preliminaries....... 14.1.1 Problem..... 14.1.2 Problem instances 14.1.3 Algorithms... 14.1.4 Sorting in Python 14.2 Bogosort......... 14.3 Insertion sort....... 14.3.1 Recursive version 14.3.2 Iterative version. 14.3.3 Complexity... 14.3.4 Performance... 14.4 Selection sort....... 14.4.1 Recursive version 14.4.2 Iterative version. 14.4.3 Code....... 14.4.4 Select largest...................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... 390 390 391 393........................ 395 396 396 397 398 398 399 400 401 402 402 403 404 405 405 407 409 410 410 413 414 414 416 416 417................ 419 420 420 421 423 424 424 425 426 427 429 429 430 431 431 433 434 ix 14.5 Merge sort.............. 14.5.1 Algorithm.......... 14.5.2 Complexity......... 14.5.3 Code and performance... 14.6 Quicksort............... 14.6.1 Algorithm.......... 14.6.2 Complexity......... 14.6.3 Code and performance... 14.6.4 In-place version....... 14.7 Quicksort variants.......... 14.7.1 Three-way quicksort.... 14.7.2 Quickselect......... 14.8 Pigeonhole sort............ 14.8.1 Comparison sort complexity 14.8.2 Algorithm.......... 14.8.3 Complexity......... 14.8.4 Code and tests........ 14.8.5 Performance......... 14.9 Summary............... 14.9.1 Algorithms......... 14.9.2 Complexities........ 15 TMA 02 part 1 15.1 Brute-force search.. 15.1.1 Problem type 15.1.2 Candidates. 15.1.3 Generate... 15.1.4 Test..... 15.1.5 Solutions.. 15.1.6 Algorithm.. 15.1.7 Complexity. 15.1.8 Performance. 15.2 Divide and conquer.. 15.2.1 Complexity............................................................................................................................................................................................................................................................................................................................................................................................................................................................................... 435 435 438 439 440 440 443 444 445 445 446 447 448 448 449 450 450 452 452 453 453.............................................................................................................................................................................................................................................................................................. 455 455 456 456 457 457 458 458 458 459 459 460 16 Rooted trees 16.1 Binary tree........... 16.1.1 Terminology..... 16.1.2 ADT and data structure 16.2 Algorithms on trees...... 16.2.1 Divide and conquer.. 16.2.2 Arm’s-length recursion 16.3 Traversals............ 16.3.1 Depth-first search... 16.3.2 Pre-order traversal.. 16.3.3 In-order traversal... 16.3.4 Post-order traversal.. 16.3.5 Breadth-first search.............................................................................................................................................................................................................................................................................................................. 463 464 465 466 469 469 470 472 473 473 474 475 476 x............................................ 16.4 Binary search trees...... 16.4.1 Search........ 16.4.2 Add node...... 16.4.3 Remove node.... 16.5 Balanced trees........ 16.5.1 Complexity of search 16.5.2 Balanced trees.... 16.5.3 Checking balance.. 16.6 Heapsort........... 16.6.1 Binary heap..... 16.6.2 Inserting items... 16.6.3 Removing the root. 16.6.4 Complexity..... 16.6.5 Heaps in Python... 16.7 Summary........... 16.7.1 Rooted trees..... 16.7.2 Binary trees..... 16.7.3 Binary search trees. 16.7.4 Heaps....................................................................................................... 17 Graphs 1 17.1 Modelling with graphs......... 17.1.1 Exercises........... 17.2 Basic concepts............. 17.2.1 On nodes and edges...... 17.2.2 On graphs........... 17.2.3 Special graphs......... 17.2.4 ADT.............. 17.3 Edge list representation........ 17.3.1 Exercises........... 17.4 Adjacency matrix representation.... 17.4.1 Exercises........... 17.5 Adjacency list representation...... 17.5.1 Exercises........... 17.6 Classes for graphs........... 17.6.1 The DiGraph class...... 17.6.2 The UndirectedGraph class. 17.6.3 Special graphs......... 17.6.4 Random graphs........ 17.7 Traversing a graph........... 17.7.1 First algorithm........ 17.7.2 Complexity.......... 17.7.3 Code and tests......... 17.7.4 Second algorithm....... 17.8 Breadth- and depth-first search..... 17.8.1 Breadth-first search...... 17.8.2 Depth-first search....... 17.8.3 Tests......................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... 478 479 481 483 486 486 487 489 491 492 493 494 495 496 497 497 498 499 499........................... 501 502 506 507 508 509 511 513 513 514 516 517 518 520 521 521 525 527 532 536 537 537 539 540 548 548 549 550 xi 17.8.4 Comparison.. 17.9 Summary........ 17.9.1 Terminology. 17.9.2 Data structures 17.9.3 Traversals... 17.9.4 Python................................................................................................................................................................................... 558 560 561 562 563 563 18 Greed 18.1 Interval scheduling...... 18.1.1 The greedy approach 18.1.2 Greedy choices... 18.1.3 Algorithm...... 18.2 Weighted graphs....... 18.2.1 Data structures... 18.2.2 Classes....... 18.3 Minimum spanning tree... 18.3.1 First algorithm... 18.3.2 Second algorithm.. 18.3.3 Code......... 18.4 Shortest paths......... 18.4.1 Algorithm...... 18.4.2 Code......... 18.4.3 Applications..... 18.5 Summary........... 18.5.1 Weighted graphs.. 18.5.2 Python............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................ 565 567 568 569 574 575 577 579 583 584 587 589 591 592 594 600 601 601 602 19 Practice 2 19.1 Jousting....... 19.1.1 Exercises. 19.2 Dot product..... 19.2.1 Exercises. 19.3 Beams....... 19.3.1 Exercises. 19.4 Up and down.... 19.4.1 Exercises. 19.5 A knight goes places 19.5.1 Exercises..................................................................................................................................................................................................................................................................... 603 604 604 605 606 607 608 609 609 610 612......... 615 615 615 616 616 616 617 618 618 618.................................................. 20 TMA 02 part 2 20.1 Using graphs.......... 20.1.1 Modelling with graphs 20.1.2 Algorithms...... 20.2 Applying greed......... 20.2.1 Approaches...... 20.2.2 Correctness...... 20.3 Python............. 20.3.1 Language constructs. 20.3.2 Standard library.... xii........................................................................................................................................................................................................................ 20.3.3 M269 library.............................. 618 21 Graphs 2 21.1 Undirected graph components...... 21.1.1 Problem definition and instances 21.1.2 Algorithm and complexity... 21.1.3 Code and tests.......... 21.2 Directed graph components....... 21.2.1 Problem and instances..... 21.2.2 Algorithm and complexity... 21.2.3 Code and tests.......... 21.3 Topological sort............. 21.3.1 Problem............. 21.3.2 Algorithm and code....... 21.3.3 Complexity........... 21.3.4 Exercises............ 21.4 State graphs............... 21.4.1 Problem............. 21.4.2 Graph.............. 21.4.3 Code............... 21.4.4 Complexity........... 21.5 Practice.................. 21.5.1 Rook’s moves.......... 21.5.2 Islands.............. 21.6 Summary................. 22 Backtracking 22.1 Generate sequences......... 22.1.1 Recursive generation.... 22.1.2 Accept partial candidates.. 22.2 Prune the search space........ 22.2.1 Local and global constraints 22.2.2 Avoid visits......... 22.3 Trackword.............. 22.3.1 The problem......... 22.3.2 Candidates and extensions. 22.3.3 The constraints....... 22.3.4 Template.......... 22.4 Optimise............... 22.4.1 The problem......... 22.4.2 Keep the best........ 22.4.3 Avoid worse candidates... 22.4.4 Start well.......... 22.5 Back to the TSP........... 22.5.1 The main function...... 22.5.2 The value function..... 22.5.3 Checking the constraints.. 22.5.4 The backtracking function.................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................. 621 622 623 624 624 626 627 628 630 631 631 633 635 636 637 638 639 641 644 644 645 646 647..................... 649 650 651 654 655 656 658 659 660 660 662 664 665 665 665 667 668 669 671 673 673 675 xiii 22.6 Generate subsets.......... 22.7 Back to the knapsack........ 22.7.1 The problem........ 22.7.2 The value function.... 22.7.3 The constraints functions. 22.7.4 The backtracking function 22.7.5 The main function..... 22.7.6 Sort extensions...... 22.8 Summary............................................................................................................................................................................................................................. 676 678 678 679 679 680 682 683 685 23 Dynamic Programming 23.1 Fibonacci............. 23.1.1 Recursive........ 23.1.2 Top-down........ 23.1.3 Bottom-up........ 23.1.4 With arrays....... 23.1.5 A graph perspective... 23.2 Longest common subsequence.. 23.2.1 Recursive........ 23.2.2 Top-down........ 23.2.3 Recursive with indices. 23.2.4 Top-down with matrix. 23.2.5 Bottom-up........ 23.2.6 Complexity and run-time 23.3 Knapsack............. 23.3.1 Recursive........ 23.3.2 Common subproblems. 23.3.3 Top-down and bottom-up 23.3.4 Complexity....... 23.4 TSP, take 3............ 23.4.1 Recursive, take 1.... 23.4.2 Recursive, take 2.... 23.4.3 Top-down........ 23.4.4 Bottom-up........ 23.4.5 Complexity....... 23.5 Summary..................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... 687 688 688 690 693 694 695 696 697 699 700 701 703 705 705 706 708 709 711 712 713 714 716 718 720 720 24 Practice 3 24.1 Safe places..... 24.1.1 Exercises. 24.2 Extra staff...... 24.2.1 Exercises. 24.3 Borrow a book... 24.3.1 Exercises. 24.4 Levenshtein distance 24.4.1 Exercises. 24.5 Higher and higher. 24.5.1 Exercises................................................................................................................................................................................................................................................. 723 724 724 725 726 728 728 729 730 732 733 xiv...................................................................... 25 TMA 03 part 1 25.1 Problems on graphs............ 25.1.1 Starting with the graph...... 25.1.2 Starting with the general problem 25.2 Backtracking................ 25.2.1 Constraints on sequences..... 25.2.2 Best sequence........... 25.2.3 Constraints on sets........ 25.2.4 Best set.............. 25.3 Dynamic programming...................................................................................................................................................................................... 737 737 738 738 739 740 741 743 744 745 26 Complexity classes 26.1 Tractable and intractable problems. 26.1.1 Problem complexity.... 26.1.2 Tractable problems.... 26.1.3 Intractable problems... 26.1.4 The twilight zone..... 26.2 The P and NP classes........ 26.2.1 SAT............ 26.2.2 Class P.......... 26.2.3 Class NP......... 26.2.4 P versus NP........ 26.3 Reductions............. 26.3.1 Median.......... 26.3.2 Minimum and maximum. 26.3.3 Interval scheduling.... 26.4 Problem hardness.......... 26.4.1 Comparing problems... 26.4.2 Transitivity........ 26.4.3 The NP-hard class..... 26.4.4 The NP-complete class.. 26.4.5 P versus NP........ 26.5 Theory and Practice........ 26.5.1 Theory.......... 26.5.2 Practice.......... 26.6 Summary.............. 26.6.1 Reductions........ 26.6.2 Problem classes...... 26.6.3 Problems...................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... 749 750 750 751 752 753 754 754 755 755 757 759 760 761 762 764 764 765 766 766 767 768 768 769 770 770 771 772 27 Computability 27.1 Turing machine......... 27.1.1 Definition....... 27.1.2 Parity bit....... 27.1.3 Implementation.... 27.1.4 Checking passwords. 27.2 The Church–Turing thesis... 27.2.1 Computational models................................................................................................................................................................. 773 773 774 775 777 781 782 782.............. xv 27.2.2 Universal models....... 27.2.3 Length of string........ 27.3 Static analysis............. 27.3.1 Functions on functions.... 27.3.2 Writing functions on functions 27.3.3 Navel gazing......... 27.4 Undecidability............. 27.4.1 The halting problem..... 27.4.2 The totality problem..... 27.4.3 Rice’s theorem........ 27.4.4 The equivalence problem... 27.4.5 Reduction and computability. 27.4.6 The problem landscape.... 27.5 Summary................ 27.5.1 Turing machines....... 27.5.2 Computability......... 28 TMA 03 part 2 28.1 Problem classes.... 28.1.1 Computable.. 28.1.2 Tractable... 28.1.3 Intractable... 28.1.4 NP-hard.... 28.1.5 NP....... 28.1.6 NP-complete. 28.2 Turing machines.... 28.3 Python......... 28.3.1 Standard library 28.3.2 M269 library. 28.4 Final words................................................................... 29 Hints 29.1 Introduction........... 29.1.1 Text cells........ 29.2 Numbers and sequence...... 29.2.1 Expressions....... 29.2.2 Functions in mathematics 29.2.3 Functions in Python... 29.2.4 Complexity....... 29.2.5 Run-times........ 29.3 Booleans and selection...... 29.3.1 Booleans........ 29.3.2 Decision problems... 29.3.3 Boolean expressions.. 29.3.4 Classification problems. 29.3.5 Practice......... 29.4 Sequences and iteration..... 29.4.1 The Sequence ADT... xvi.................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... 783 785 787 787 789 790 792 792 794 794 794 795 796 797 797 798............ 801 801 802 802 803 803 803 804 804 805 805 805 805................ 807 807 807 808 808 808 808 808 809 809 809 810 810 810 811 812 812 29.5 29.6 29.7 29.8 29.9 29.10 29.11 29.4.2 Strings......... 29.4.3 Iteration........ 29.4.4 Linear search..... 29.4.5 Tuples and tables... 29.4.6 Lists.......... 29.4.7 Reversal........ 29.4.8 Optional practice... Implementing sequences.... 29.5.1 Developing data types. 29.5.2 Bounded sequences.. 29.5.3 Using dynamic arrays. 29.5.4 Linked lists...... Stacks and queues....... 29.6.1 Stacks......... 29.6.2 Using stacks...... 29.6.3 Queues........ 29.6.4 Implementing queues. 29.6.5 Implementing deques. 29.6.6 Priority queues.... Unordered collections..... 29.7.1 Maps......... 29.7.2 Dictionaries...... 29.7.3 Hash tables...... 29.7.4 Sets.......... 29.7.5 Bags.......... 29.7.6 Bags in Python.... Practice 1............ 29.8.1 Pangram........ 29.8.2 Election........ 29.8.3 Voucher........ 29.8.4 Trains......... 29.8.5 Browsing....... 29.8.6 SMS.......... Exhaustive search....... 29.9.1 Linear search, again.. 29.9.2 Factorisation..... 29.9.3 Constraint satisfaction 29.9.4 Searching permutations 29.9.5 Searching subsets... 29.9.6 Practice........ Recursion............ 29.10.1 Recursion on integers. 29.10.2 Length of a sequence. 29.10.3 Inspecting sequences. 29.10.4 Creating sequences.. 29.10.5 Avoiding slicing.... 29.10.6 Multiple recursion.. Divide and conquer....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... 812 813 813 813 814 814 815 816 816 816 817 817 817 817 818 819 819 820 820 821 821 821 822 822 823 823 824 824 824 825 826 826 827 828 828 828 828 829 829 829 830 830 830 830 831 831 831 832 xvii 29.12 29.13 29.14 29.15 29.16 29.17 29.18 29.19 29.20 xviii 29.11.1 Variable decrease........ 29.11.2 Binary search.......... 29.11.3 Binary search variants..... Sorting.................. 29.12.1 Insertion sort.......... 29.12.2 Selection sort.......... 29.12.3 Merge sort............ 29.12.4 Quicksort............ 29.12.5 Quicksort variants........ Rooted trees............... 29.13.1 Algorithms on trees....... 29.13.2 Traversals............ 29.13.3 Binary search trees....... 29.13.4 Balanced trees.......... 29.13.5 Heapsort............. Graphs 1................. 29.14.1 Modelling with graphs..... 29.14.2 Basic concepts......... 29.14.3 Edge list representation..... 29.14.4 Adjacency matrix representation 29.14.5 Adjacency list representation.. 29.14.6 Classes for graphs........ 29.14.7 Traversing a graph....... Greed................... 29.15.1 Minimum spanning tree..... 29.15.2 Shortest paths.......... Practice 2................. 29.16.1 Jousting............. 29.16.2 Dot product........... 29.16.3 Beams.............. 29.16.4 Up and down.......... 29.16.5 A knight goes places...... Graphs 2................. 29.17.1 Undirected graph components. 29.17.2 Directed graph components... 29.17.3 Topological sort......... 29.17.4 State graphs........... 29.17.5 Practice............. Backtracking............... 29.18.1 Back to the TSP......... 29.18.2 Back to the knapsack...... Dynamic Programming......... 29.19.1 Longest common subsequence. 29.19.2 Knapsack............ 29.19.3 TSP, take 3........... Practice 3................. 29.20.1 Safe places........... 29.20.2 Extra staff............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................ 832 832 832 832 832 833 833 834 834 834 834 835 835 835 836 836 836 837 837 837 837 838 838 838 838 839 839 839 840 840 841 841 842 842 842 842 843 843 844 844 844 844 844 844 845 845 845 846 29.20.3 Borrow a book.......... 29.20.4 Levenshtein distance....... 29.20.5 Higher and higher......... 29.21 Complexity classes............. 29.21.1 Tractable and intractable problems 29.21.2 The P and NP classes....... 29.21.3 Reductions............ 29.22 Computability............... 29.22.1 Turing machine.......... 29.22.2 The Church–Turing thesis.... 29.22.3 Undecidability.......... 30 Answers 30.1 Introduction........... 30.1.1 Text cells........ 30.2 Numbers and sequence...... 30.2.1 Arithmetic operations.. 30.2.2 Expressions....... 30.2.3 Assignments...... 30.2.4 Functions in mathematics 30.2.5 Functions in Python... 30.2.6 Complexity....... 30.2.7 Run-times........ 30.3 Booleans and selection...... 30.3.1 Booleans........ 30.3.2 Decision problems... 30.3.3 Boolean expressions.. 30.3.4 Classification problems. 30.3.5 Practice......... 30.4 Sequences and iteration..... 30.4.1 The Sequence ADT... 30.4.2 Strings.......... 30.4.3 Iteration......... 30.4.4 Linear search...... 30.4.5 Tuples and tables.... 30.4.6 Lists........... 30.4.7 Reversal......... 30.5 Implementing sequences..... 30.5.1 Developing data types.. 30.5.2 Bounded sequences... 30.5.3 Linked lists....... 30.6 Stacks and queues........ 30.6.1 Stacks.......... 30.6.2 Using stacks....... 30.6.3 Queues......... 30.6.4 Implementing queues.. 30.6.5 Implementing deques.. 30.6.6 Priority queues........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... 846 847 848 849 849 849 849 850 850 850 851................................... 853 853 853 854 854 854 855 855 856 856 857 858 858 860 861 861 863 868 868 869 870 871 873 874 875 879 879 879 880 880 880 881 883 885 886 886 xix 30.7 Unordered collections..... 30.7.1 Maps......... 30.7.2 Dictionaries...... 30.7.3 Hash tables...... 30.7.4 Sets.......... 30.7.5 Bags.......... 30.7.6 Bags in Python.... 30.8 Practice 1............ 30.8.1 Pangram........ 30.8.2 Election........ 30.8.3 Voucher........ 30.8.4 Trains......... 30.8.5 Browsing....... 30.8.6 SMS.......... 30.9 Exhaustive search....... 30.9.1 Linear search, again.. 30.9.2 Factorisation..... 30.9.3 Constraint satisfaction 30.9.4 Searching permutations 30.9.5 Searching subsets... 30.9.6 Practice........ 30.10 Recursion............ 30.10.1 Recursion on integers. 30.10.2 Length of a sequence. 30.10.3 Inspecting sequences. 30.10.4 Creating sequences.. 30.10.5 Avoiding slicing.... 30.10.6 Multiple recursion.. 30.11 Divide and conquer....... 30.11.1 Variable decrease... 30.11.2 Binary search..... 30.11.3 Binary search variants 30.12 Sorting............. 30.12.1 Insertion sort..... 30.12.2 Selection sort..... 30.12.3 Merge sort....... 30.12.4 Quicksort....... 30.12.5 Quicksort variants... 30.12.6 Pigeonhole sort.... 30.13 Rooted trees.......... 30.13.1 Binary tree...... 30.13.2 Algorithms on trees.. 30.13.3 Traversals....... 30.13.4 Binary search trees.. 30.13.5 Balanced trees..... 30.13.6 Heapsort........ 30.14 Graphs 1............ 30.14.1 Modelling with graphs xx................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................ 889 889 890 891 891 893 894 895 895 898 900 901 904 906 908 908 910 910 910 911 911 914 914 915 915 916 917 918 919 919 920 920 922 922 922 923 924 924 925 925 925 926 927 927 928 929 930 930 30.15 30.16 30.17 30.18 30.19 30.20 30.21 30.22 30.14.2 Basic concepts.......... 30.14.3 Edge list representation...... 30.14.4 Adjacency matrix representation. 30.14.5 Adjacency list representation... 30.14.6 Classes for graphs......... 30.14.7 Traversing a graph........ Greed.................... 30.15.1 Interval scheduling........ 30.15.2 Minimum spanning tree...... 30.15.3 Shortest paths........... Practice 2.................. 30.16.1 Jousting.............. 30.16.2 Dot product............ 30.16.3 Beams............... 30.16.4 Up and down........... 30.16.5 A knight goes places....... Graphs 2.................. 30.17.1 Undirected graph components.. 30.17.2 Directed graph components.... 30.17.3 Topological sort.......... 30.17.4 State graphs............ 30.17.5 Practice.............. Backtracking................ 30.18.1 Back to the TSP.......... 30.18.2 Back to the knapsack....... Dynamic Programming.......... 30.19.1 Longest common subsequence.. 30.19.2 Knapsack............. 30.19.3 TSP, take 3............ Practice 3.................. 30.20.1 Safe places............ 30.20.2 Extra staff............. 30.20.3 Borrow a book.......... 30.20.4 Levenshtein distance....... 30.20.5 Higher and higher......... Complexity classes............. 30.21.1 Tractable and intractable problems 30.21.2 The P and NP classes....... 30.21.3 Reductions............ Computability............... 30.22.1 Turing machine.......... 30.22.2 The Church–Turing thesis.... 30.22.3 Undecidability........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... 931 932 933 934 935 936 936 936 937 939 940 940 941 943 946 948 951 951 952 952 954 954 955 955 956 957 957 960 962 963 963 964 966 967 971 974 974 974 975 975 975 977 978 31 Figures 979 31.1 Introduction................................... 979 31.1.1 Software................................. 979 31.1.2 Notebooks................................ 980 xxi 31.2 31.3 31.4 31.5 31.6 31.7 31.8 31.9 31.10 31.11 31.12 31.13 xxii 31.1.3 Text cells............ 31.1.4 Code cells............ Sequences and iteration......... 31.2.1 Reversal............. Implementing sequences......... 31.3.1 Static arrays........... 31.3.2 Bounded sequences....... 31.3.3 Linked lists........... Stacks and queues............ 31.4.1 Stacks.............. 31.4.2 Queues............. 31.4.3 Implementing deques...... Unordered collections.......... 31.5.1 Hash tables........... Practice 1................. 31.6.1 Trains.............. 31.6.2 Browsing............ Exhaustive search............ 31.7.1 Searching permutations..... Sorting.................. 31.8.1 Merge sort............ 31.8.2 Quicksort............ Rooted trees............... 31.9.1 Binary tree........... 31.9.2 Traversals............ 31.9.3 Binary search trees....... 31.9.4 Balanced trees.......... 31.9.5 Heapsort............. Graphs 1................. 31.10.1 Modelling with graphs..... 31.10.2 Basic concepts......... 31.10.3 Edge list representation..... 31.10.4 Adjacency matrix representation 31.10.5 Adjacency list representation.. Greed................... 31.11.1 Interval scheduling....... 31.11.2 Weighted graphs........ 31.11.3 Minimum spanning tree..... 31.11.4 Shortest paths.......... Practice 2................. 31.12.1 Beams.............. 31.12.2 Up and down.......... 31.12.3 A knight goes places...... Graphs 2................. 31.13.1 Undirected graph components. 31.13.2 Directed graph components... 31.13.3 Topological sort......... 31.13.4 State graphs........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... 981 981 983 983 983 983 984 985 986 986 986 986 986 986 987 987 987 988 988 988 988 988 989 989 989 990 990 991 992 992 993 994 994 994 994 994 995 996 996 997 997 997 998 998 998 999 999 1000 31.14 Backtracking.............. 31.14.1 Generate sequences...... 31.14.2 Trackword........... 31.14.3 Back to the TSP........ 31.14.4 Generate subsets....... 31.15 Dynamic Programming........ 31.15.1 Fibonacci........... 31.15.2 Longest common subsequence 31.15.3 Knapsack........... 31.15.4 TSP, take 3.......... 31.16 Practice 3................ 31.16.1 Extra staff........... 31.16.2 Borrow a book........ 31.16.3 Levenshtein distance..... 31.16.4 Higher and higher....... 31.17 Complexity classes........... 31.17.1 The P and NP classes..... 31.17.2 Reductions.......... 31.17.3 Problem hardness....... 31.17.4 Summary........... 31.18 Computability............. 31.18.1 Turing machine........ 31.18.2 The Church–Turing thesis.. 31.18.3 Undecidability........ 31.18.4 Summary........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................ 1001 1001 1001 1002 1002 1002 1002 1003 1004 1004 1005 1005 1005 1005 1006 1006 1006 1006 1007 1008 1008 1008 1009 1009 1010 xxiii xxiv Algorithms, data structures and computability To Clara, Ana and Claudia CONTENTS 1 Algorithms, data structures and computability This textbook is part of the 2023/24 presentation of the Open University module M269 Algorithms, data structures and computability. This is the version as of 15 August 2023. Copyright © 2020–2023 The Open University All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, transmitted or utilised in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, without written permission from the publisher or a licence from the Copyright Licensing Agency Ltd. Details of such licences (for reprographic reproduction) may be obtained from the Copyright Licensing Agency Ltd, 5th Floor, Shackleton House, 4 Battle Bridge Lane, London SE1 2HX (website www.cla.co.uk). Open University materials may also be made available in electronic formats for use by students of the University. All rights, including copyright and related rights and database rights, in electronic materials and their contents are owned by or licensed to The Open University, or otherwise used by The Open University as permitted by applicable law. In using electronic materials and their contents you agree that your use will be solely for the purposes of following an Open University course of study or otherwise as licensed by The Open University or its assigns. Except as permitted above you undertake not to copy, store in any medium (including electronic storage or use in a website), distribute, transmit or retransmit, broadcast, modify or show in public such electronic materials in whole or in part without the prior written consent of The Open University or in accordance with the Copyright, Designs and Patents Act 1988. Acknowledgements I thank my colleagues Alistair Willis, Andy Connolly, Phil Molyneux, Shena Deuchars (critical readers), Jonathan Darch (editor) and Andrew Whitehead (graphic designer) for their input, which greatly improved the content and presentation of this book. Thanks are also due to Alan Bradshaw, Allan Thrower and Mark Hall for specifying, procuring and configuring the JupyterHub server. Many thanks to Tony Hirst and all students and tutors who reported typos and other mistakes. Thanks to Margarida Mamede for suggesting some exercises and to Steve Halim for his Methods to Solve site, from which I selected some of the Kattis problems. A very special thanks to the rest of the M269 team: Adam Linson, Alexis Lansbury, Ann Walshe, Brendan Quinn, Jane Evans, Oli Howson and Phil Hackett. Without their support and their hard work to get the myriad other things done (write TMAs and marking guides, hire tutors, produce all the paperwork and budgets necessary, etc. etc.) the new M269 wouldn’t exist. Last but not least, many thanks to the tutors for their tutorials, student support, marking feedback and for coping with the many changes introduced by the new edition. 2 CONTENTS CHAPTER 1 INTRODUCTION Money may make the world go round, but it’s algorithms that make money go round. When you shop online or in-store, algorithms are the step-by-step procedures that computers follow to apply discounts and taxes, to encrypt and transmit your card details, to do any currency conversions, and to finally debit your account and credit the seller’s. Algorithms recommend what to read, watch and buy, whom to date and whether we should get a loan. Algorithms predict the weather, drive cars, recognise faces and trade in the stock market. Our lives increasingly depend on algorithms. M269 is an introduction to what algorithms are and how they work. You will learn some general algorithmic techniques and ways of organising data so that algorithms can use it. Techniques, algorithms and data structures that are quite advanced or specific to particular domains (imaging, artificial intelligence, etc.) are outside the scope of this module. Algorithms should produce their results as quickly as possible. You will learn how to measure the efficiency of an algorithm in a way that doesn’t depend on which computer executes it. In the last part of this module you will become aware of the limitations of algorithms and learn about problems for which no efficient algorithm is currently known, and problems that can’t be solved by any algorithm. This chapter tells you what to expect in M269 and guides you in preparing for it. 3 Algorithms, data structures and computability 1.1 What to expect This section briefly describes what you can expect from M269 and what is expected of you. 1.1.1 Content Algorithms, data structures and computability have been core topics of Computing courses around the world for decades, and for a good reason. The first two topics are eminently practical: knowledge of how to structure data, construct algorithms and analyse their efficiency is useful for the design and implementation of any software system. It’s knowledge you can immediately put to use in other modules and in your professional life. The third topic is somewhat theoretical, but it is the Computer Science topic. Computability addresses the fundamental questions of what computation is and what can and can’t be computed. I’m sure you will find M269 useful and intellectually stimulating. M269 covers most of the core algorithm, data structure and computability topics recommended for undergraduate computing curricula by professional bodies. The first third of M269 (Chapters 2–10) explains the basic data structures and programming constructs needed for the rest of M269. Those chapters are therefore the most intensive with respect to the amount of terminology and concepts introduced, but you should know several of them from prior study. Half of M269 (Chapters 11–25) is dedicated to algorithmic techniques, introducing further data structures, as needed. The final Chapters 26–28 are about the complexity and computability of computational problems. As in most modules, you can expect the material to get more difficult as you progress. Info: The recommended core topics are listed here. A recurring theme of M269 is abstraction. As you shall see later, an algorithm is an abstraction of the steps executed by a computer, data structures abstract the relationships between the data being processed, and the complexity of an algorithm is an abstraction of its run-time. Abstracting from problem-specific details leads to general models, rules and concepts that help us tackle new problems: that’s the power of abstraction. The cover of this book illustrates the abstraction process, going from a detailed representation of a cow to a general geometric shape, the rectangle. Info: The cover shows Theo van Doesburg’s Composition VIII (The Cow) and three studies leading to it, all from 1917–18. MoMA’s website has more drawings and more information on the final study. The emphasis of M269 is computational problem solving. The module gives you techniques and a process for solving several types of problems, comparing alternative solutions, and communicating problems and solutions clearly. Many examples illustrate all of this. Much of the teaching is done through examples and exercise solutions. Study them carefully. Don’t just glance through them: make sure you understand each example and solution before moving on. 4 Chapter 1. Introduction Algorithms, data structures and computability However, learning is not passive: it’s an activity. We don’t learn how to walk, drive a car or play a musical instrument just by watching others doing it. The only way to learn how to solve problems is to solve problems, and M269 is full of exercises for you to practise. Expect to spend most of your time figuring out how to solve a problem, trying out different approaches, analysing which one is best, writing, testing and debugging code, and documenting your solution. Algorithms can be described in plain English but must be implemented in some programming language for computers to execute them. M269 uses Python because it’s an expressive, readable and uncluttered programming language. M269 aims for you to develop sought-after cognitive and professional skills around problem solving, programming and communication. The intended learning outcomes of M269 are: Knowledge and understanding: – Understand the common general-purpose data structures, algorithmic techniques and complexity classes. – Know about the limits of computation and their practical implications. – Understand the Turing Machine model of computation. Cognitive skills: – Develop and apply algorithms and data structures to solve computational problems. – Analyse the complexity of algorithms to support software design choices. Key skills: – Explain how an algorithm or data structure works, in order to communicate with relevant stakeholders. Practical and professional skills: – Write readable, tested, documented and efficient Python code. 1.1.2 Challenges There’s usually a jump in pace and difficulty from Stage 1 to Stage 2 modules and M269 is among the most challenging Stage 2 Computing modules. If you don’t have experience of high-intensity study, in which you need to understand and apply many terms, concepts and techniques, you may wish to pass a Stage 2 module before starting M269. M269 is challenging mainly for three reasons. First, it contains lots of material and over 5,000 lines of Python code in order to cover the recommended core topics in a single module, due to how the OU curriculum is organised. Other universities spread the M269 material (and additional topics) across two or three modules. To cope with the amount of M269 material, previous students found it useful to: use concept-mapping software to organise the M269 topics and terminology 1.1. What to expect 5 Algorithms, data structures and computability look at the TMAs before working through the corresponding chapters to gauge what to study in depth, what to skim and what to skip. The TMAs are in the ‘Assessment’ tab of the M269 website. Second, M269 is about solving computational problems, which is inherently difficult: it requires experience, technical knowledge, persistence and creativity. No wonder good problem-solvers are sought after and well paid! I’ve written parts of this book in a ‘think aloud’ style, so that you can see how I approach a problem. Another feature of this textbook is the question checklists in Chapters 5, 10, 15, 20, 25 and 28 to help steer you in the right direction when solving a problem. Nevertheless, learning by yourself how to solve problems is difficult. Problem solving is best done together with others, to bounce off ideas and check potential solutions for errors and possible improvements. I encourage you to actively participate in the forums and tutorials. Just reading other’s posts or watching recorded tutorials doesn’t provide the same learning experience as interacting with peers and tutors. Third, the M269 topics are inherently abstract and not easy to convey just with text and static figures. Understanding how code works and how it changes data in memory is not easy from just reading the code. Some students found Python tutor useful to visualise the step-by-step execution of M269 code. Let’s not beat about the bush: M269 is hard work and challenging. But if you put in the effort, you’ll gain conceptual and practical problem-solving skills sought by employers. 1.1.3 Previous knowledge I assume you have had an introduction to Python, like in TM112, and that you can write simple short programs using the following constructs: variables, expressions and assignments integers, Booleans, strings, lists and some operations on them selection statements (if-elif-else and nested ifs) iteration statements (while-loop, for-in-range, for-in-collection) function definitions and calls. Chapters 2 to 4 recap these constructs, but you may find the pace too fast and the explanations too brief if you don’t have Python experience. The initial chapters include new material too, so don’t skip them even if you are familiar with Python. I also assume you have basic mathematical proficiency: you understand and know how to use percentages, powers (like n4 and 2𝑛 ), logarithms and scientific notation (like 4.3×10−8 ) you can write and evaluate expressions for ‘word problems’ like calculating the service charge as a percentage of a restaurant bill you can manipulate algebraic expressions, e.g. transform 𝑥 + 4𝑦 = 20 into 𝑦 = 5 − 𝑥/4. 6 Chapter 1. Introduction Algorithms, data structures and computability You can check your Python and maths knowledge with the ‘Are you ready for M269’ quiz, if you haven’t done it before registering for M269. The quiz and revision resources are available from the M269 page of the Computing & IT study site. Activities Before continuing with the next section, go to the M269 website and do the activities for this section, in Week 1 of the study planner, under heading ‘Section 1.1’, to help you get a better idea of what to expect in M269. This includes watching a BBC programme on algorithms; some of them will be presented in more detail in M269. 1.2 How to study To successfully complete M269, see it as a project: it has a start and an end, goals (the learning outcomes), a schedule (the study planner) and deliverables (the TMAs). Like any project, M269 requires planning and preparation. The first step is to get to know the M269 materials, which consist of this book, three TMAs, and other resources on the M269 website. 1.2.1 Book This book is provided in three formats: Jupyter notebooks, PDF and HTML. Each has its advantages. The PDF format is read-only. Using a free PDF reader, you can read the PDF book on a tablet, use the PDF’s table of contents to jump to any subsection, and quickly search for a particular word over the whole book. Depending on the PDF reader and the accessibility settings of your computer, you can even have the book’s content read to you, e.g. during commuting, but code and technical notation may be read out incorrectly. A PDF reader also allows you to bookmark pages, highlight passages, add notes and print pages, e.g. the summary section at the end of most chapters. The HTML book is read-only too. You can read it with any web browser. As with the PDF book, you can search for any word, go directly to any section, and possibly have the content read to you. You can also bookmark and print HTML pages. Each HTML page is a complete section, corresponding to several PDF pages. You can change the font size of the HTML book with your browser’s zoom in and zoom out commands. Jupyter notebooks are interactive documents that contain both text and code. I mean real, executable, editable code, not static text in a monospaced font. With notebooks, you don’t need to constantly switch between a text-only book and a programming environment. So you’ll have more time for practice. The M269 TMAs are notebooks too, to save you and your tutor time from handling separate files with the TMA questions, your answers and your code. Notebooks are editable. You will edit the notebooks we provide to fix errata and to write answers to exercises and TMA questions. You may add study notes, alternative solutions, wrong solutions and comments why they’re wrong. Upon completing M269, you will have unique notebooks, with your answers and notes. 1.2. How to study 7 Algorithms, data structures and computability Working with Jupyter notebooks requires a laptop or desktop computer, with a proper keyboard and a decent-sized screen. There’s one Jupyter notebook per book section, to keep them relatively small. Unlike with the PDF and HTML formats, you can’t easily search for a term across all notebooks, only within a single notebook. It’s also not as easy to highlight passages and make notes in Jupyter notebooks. Notebook files have the extension ‘.ipynb’, which comes from their original name: IPython notebooks. (IPython stands for interactive Python.) Do not double-click on a notebook to open it: this will probably open a text editor showing the internal format of a notebook. If you have double-clicked on a notebook, then immediately close the editor without changing the file. The next section explains how to install the necessary software to use notebooks. Once the software is installed, you’ll be able to work on notebooks with a web browser. If for accessibility or other reasons you can’t or don’t want to use Jupyter notebooks, you can instead use your preferred code editor with the provided Python files, one per notebook, with all the code in that notebook. Some code is specific to Jupyter, but most of it can be executed in any Python environment. Most book sections have exercises. At the end of each one there’s a link to its answer. Most exercises also have a link to a hint. Each hint and answer is in a separate notebook (and separate page in the HTML version), so that you don’t accidentally see the hint or answer for the next exercise. However, the PDF version has several hints and answers on the same page. Once you have read the hint or answer in HTML or PDF, you can return to the exercise by using the ‘back’ command of your browser or PDF app. This book uses a few conventions, explained next. All formats look slightly different, due to the way the PDF and HTML books are generated from the notebooks. Exercises are numbered consecutively from 1 in each section, so that you can easily refer to them in the forums and tutorials. For example, Exercise 1.3.2 is the second exercise of Section 3 of Chapter 1. Besides exercises, the book has short questions to check your understanding of the concepts. Each question and its answer are separated by a horizontal line like this: Consider the lines as ‘stop and think’ signs. At these points you should stop reading, answer the question in your head, and then continue. Terms in bold, e.g. algorithm, may occur in the assessment. You must be able to understand these terms and use them in your answers. You don’t have to memorise definitions. Info: I use information boxes like this one to indicate alternative terms you may find in other books or on the web, to refer back to TM112, to provide the sources of exercises and data, etc. You can skip information boxes: they won’t be assessed. Information boxes are blue in the Jupyter and HTML formats, and they are simply text framed by two horizontal lines in the PDF book. 8 Chapter 1. Introduction Algorithms, data structures and computability Note: I use advice boxes like this one for important teaching points, e.g. to help you solve problems and implement algorithms more effectively. Most advice boxes are in the main sections, but some appear in the solutions to exercises. Advice boxes are beige in the notebooks, orange in the HTML book, and they are simply text framed by a rectangle in the PDF book. Code examples look like this: : def list_length(a_list): """Return the length of a list.""" length = 0 for item in a_list: length = length + 1 return length Info: This function appears in TM112 Block 2 Section 4.1.4. If the code produces some result, it’s shown immediately below: : list_length(['on your marks', 'get set', 'go!']) : 3 Note the use of syntax colouring to highlight the different parts of the code: strings, special words, function names, etc. Each book format may use a different colour scheme. Code fragments and templates, i.e. text that looks like code but can’t be executed, is typeset as follows. for item in collection: process the item Code within a paragraph of text is typeset like this: length = length + 1. Occasionally, code lines are longer than the page width, like this one: : a_long_variable_name_for_a_long_and_silly_string = ˓→'supercalifragilisticexpialidocious is quite atrocious rather than␣ ˓→delicious' In the PDF book, long lines are split in two or more. Each line besides the first one starts with the symbol ˓→ to show it’s the continuation of the previous line. Spaces at the end of a line are explicitly shown with the symbol ␣. In the Jupyter and HTML books, use the mouse to scroll the long line to the right and read the rest of it. 1.2. How to study 9 Algorithms, data structures and computability 1.2.2 Mindset An important part of your study preparation is to get into the right mindset. As I mentioned, problem solving requires practice: lots of it, and regularly. There’s no recipe for solving computational problems, especially when we’re looking for the most efficient algorithm. There are general techniques, but it requires creativity to select the right one and adapt it to the problem at hand. You must view the problem from different perspectives, explore alternatives, weigh their pros and cons. Creativity is in part a systematic exploration of different approaches. There will be dead ends and you need to give your brain a break to start afresh. It’s hard to have marathons of creativity. Think little and often about the M269 exercises. Use idle periods (like queuing) to mull over them, preferably every day. As toddlers we stood up on our own, tried to walk, fell and got hurt. That didn’t stop us continuing trying and eventually succeeding. Likewise, when solving problems our initial attempts probably won’t work: our algorithms will not compute the correct output for some inputs, they won’t be efficient for large inputs, the code will crash. At such times, it’s easy to get frustrated and fed up, give up, and move to the next exercise. It’s easy and wrong. We learn more from our mistakes than from our successes. Throughout the book I’ll give you tips on how to handle errors, but it helps from the outset if you take mistakes in your stride, as an unavoidable part of problem solving, instead of as something to despair about. You should also remember that you’re not alone and that problem solving is a social activity. In professional practice, problems are solved in teams that bounce ideas around, discuss alternative designs, and look at each other’s code. You can discuss the exercises with your tutor and in the forums, ask for help, and even work on the exercises together with other students. Studying part-time at a distance can feel lonely at times, so you may wish to have some ‘study buddies’ whom you meet regularly online or face to face. Note however that you’ll have to work on the assignments by yourself. Employers need assurances that you have the knowledge and the skills to become an active player in their problem-solving teams. You can however ask for clarifications: if a question isn’t clear, contact your tutor. Note: Problem solving requires regular hard work, grit, resilience, and a willingness to fail and to ask for help. 1.2.3 Time allocation M269 is a 30-credit module over 30 weeks, so expect to work for an average of 10 hours per week. If you’re studying part-time, I strongly advise you to do at most one other 30-credit module in parallel to M269. Each week usually corresponds to one book chapter. The material gets progressively harder, so early weeks like this one don’t require 10 hours to read and work through, while others may require more. 10 Chapter 1. Introduction Algorithms, data structures and computability Note: Get ahead of the study planner whenever you can. Don’t forget to plan for activities done outside the book, like installing software, participating in tutorials and forums, and working on the TMAs. This book contains several optional exercises. They are not accounted for in the workload. The study planner allocates two study-free weeks to each TMA. Use them well. The corresponding book chapters don’t introduce new material: they just provide some guidance for the TMA. If you’re studying more than one module, check all the submission dates and plan your work on TMAs accordingly. As part of your planning, set up study periods that fit your personal and work life pattern. Don’t fret if they get occasionally thrown off by life events: the TMA weeks give you some slack to catch up. As you study M269 and gain experience in what works best for you, be prepared to change your initial plan. M269 requires (and aims to develop) two important transferable skills: coping with lots of technical information in a short period of time, and being pragmatic about what can be done to meet a deadline. 1.2.4 Study techniques Psychology studies on how we learn have made some surprising findings over the decades. Some of the learning techniques that studies found to be effective are: 1. Vary your study environment, so that the brain gets different stimuli. 2. Self-test regularly, e.g. with flashcards or by explaining what you learned to others. 3. Sleep, to help the brain re-process information and build connections. 4. If you’re stuck with a problem, take a break and do something unrelated. 5. Break up study time, to force the brain to dig up again the information and re-store it. 6. Start a longer project as early as possible, to help the brain be attuned to information that is relevant to the project. Technique 1 is not just about varying the time and place of study, but also the way you study: reading, taking notes, discussing with peers, etc. However, keeping re-reading and highlighting the same material, or rewriting your notes, is a very passive way of learning, in which your brain is not recalling or applying the material learned. Hence the need for technique 2. Every year some M269 students post in the forums that something they were struggling with suddenly ‘clicked’ after dinner or the next day, once they looked at it with ‘fresh eyes’. That’s techniques 3 and 4 at work. Note that working on a problem for 2–3 minutes doesn’t count as ‘being stuck’. The brain needs to grapple with a problem or a concept for some time and from different angles to ‘absorb’ it. There’s of course no guarantee that ‘sleeping on it’ will reveal a solution to you. Rather, not giving enough rest to the brain will make learning harder. A recurring theme emerges from the above: the brain seems to learn best when it is repeatedly engaging with the same material but in different ways and when it is given the time to process 1.2. How to study 11 Algorithms, data structures and computability the acquired material. The brain needs to forget and be probed again to learn what is important to remember. Info: For more details on these techniques and the studies behind them, read Benedict Carey’s How we learn. Studying better is not about putting in more hours, but about using the time you have available more wisely. Here are some suggestions for M269, repeating some given previously. Don’t study 5h on one day and five on the next, for example. It’s better to split the 10 weekly hours across three or four non-consecutive days. (Technique 5) Instead of listening to a tutorial recording, it’s better to spend the same time attending it and interacting with tutor and peers. (1) Interleave reading and coding: that’s why M269 is delivered as Jupyter notebooks. (1) If you don’t understand something after the second reading, go out of the ‘book environment’: ask your tutor, ask on the forum, attend a tutorial, do a concept map, use visualisations and other third-party material, etc. (1) Do flashcards with the terms in the summary sections of each chapter. (2) Attempt to answer other students’ queries on the forums, even if you’re not very sure of your answer. (2) Don’t skip the stop-and-think lines or the exercises; try to do the optional ones. (2) Attempt the exercises in chapters 9, 19 and 24 because they draw on material in earlier chapters, thus making you revisit concepts and apply them. (2 and 5) Before working through a chapter, read (or skim again) the next TMA, to be aware of which material is most relevant. (6) Activity Go to Week 1 of the study planner and do the preparation activities listed under the heading ‘Section 1.2’: download the TMAs, contact your tutor, book tutorials, subscribe to the forums, etc. 1.3 Software This chapter explains how to use Jupyter notebooks in a web browser. Jupyter officially only supports Chrome, Firefox and Safari, but Edge should work too. Note: To avoid problems later on, update your browser now to its most recent version. 12 Chapter 1. Introduction Algorithms, data structures and computability Info: If you’re familiar with a coding environment that supports notebooks, like Visual Studio Code and PyCharm, you may prefer to use it instead of a browser. You have two options for working with Jupyter in a web browser. You can use the M269 virtual computing environment (VCE) on the OU’s Open Computing Lab, and you can install the software locally on your desktop or laptop. Using the VCE has two advantages: you can work on a tablet and you don’t have to install or configure any software. The disadvantage is that you need a reasonable internet connection. Using a local installation on your desktop or laptop allows you to work offline, but you must install and configure the Jupyter software. You can use both the VCE and a local installation, but it can get tedious. As you work through the notebooks and modify them, you need to upload and download them to and from the server to keep your local and remote workspaces in sync. To avoid that, I suggest you use the remote server and the local installation for different purposes, e.g. read the materials on the VCE and do the exercises on your machine. A note before we start: the Jupyter and VCE interfaces may have changed since I made the screenshots for this book. If you don’t intend to use the VCE, skip the next subsection and go directly to Section 1.3.2. 1.3.1 Using the VCE 1. Go to the ‘Resources’ tab of the M269 website and click on the link to the Open Computing Lab (OCL). 2. In the OCL, start the M269 VCE. You will now see the notebook dashboard, with a (currently empty) list of the files and folders on the server. If there’s a message about migrating to Notebook 7, click “don’t show anymore”. Figure 1.3.1 Next, you need to upload the M269 materials to the VCE. The easiest way is to upload the book-r1.zip archive you downloaded from the M269 website and then unpack the archive on the server. 3. Click on the ‘Upload’ button. A file dialogue window showing your local files and folders appears. 1.3. Software 13 Algorithms, data structures and computability 4. Navigate to the folder with the zip archive and select it. You may get a dialogue asking you to confirm that you want to upload such a large file. The browser window now looks like this. Figure 1.3.2 1. Click on the blue ‘Upload’ button and wait until the upload is complete. 2. Click on the ‘New’ button. A drop-down menu appears. Select the option ‘Terminal’. 3. A new browser tab appears, with a terminal. Enter unzip book-r1.zip. Wait until all files have been extracted. 4. Close the tab with the terminal. Return to the tab with the notebook dashboard. You should see an additional folder named book-r1. If you wish, you can now download the three TMA zip archives from the M269 website, upload them to the VCE and unzip them. You should end up with one folder per TMA. Before continuing, let’s take a detour and see how to download files: tick the checkboxes to their left and a download button will appear. Figure 1.3.3 You can download files but not folders. To download one or more folders, create a zip archive with them and download the archive. For example, you can create a new zip archive with the current content of the book-r1 folder or you can update the book-r1.zip archive with the files you changed or added. 14 Chapter 1. Introduction Algorithms, data structures and computability In both cases you must first click New > Terminal. To create a new archive, enter zip -r new.zip book-r1, where new is whatever name you want to give to the archive. To update the existing archive, enter instead zip -ru book-r1.zip book-r1. After the archive has been created or updated, which can take some time, go to the notebook dashboard, click on the checkbox next to the archive (as in the above screenshot) and download it. You will need to proceed similarly to create and download an archive of your TMA folder before submitting it to the eTMA system. Note: Remember to regularly back up your VCE files. I don’t recommend working locally on your computer and on the VCE because you will need to constantly upload and download the individual files you change, or create and unpack zip archives, to keep your notebooks in sync. If you intend to only work in the VCE, skip the next subsection and go directly to Section 1.3.4, otherwise log out of the VCE and install the software on your machine. 1.3.2 Installing the software To install Jupyter on your machine, follow the instructions on https://dsa-ou.github.io/m269-installer. They also tell you how to start using Jupyter. Return to here when the instructions tell you to go back to the book. 1.3.3 Switching to notebooks At this point you have a browser tab showing the notebook dashboard on the VCE or on your local machine. The dashboard should list the contents of your M269 folder, with the book-r1 subfolder and possibly a subfolder for each TMA. 1. Click on the book-r1 folder name (not the folder icon). Your screen should look similar to this: Figure 1.3.4 1.3. Software 15 Algorithms, data structures and computability 2. Click on the notebooks folder. 3. Scroll down past the chapter folders and click on the M269.ipynb file. This opens a new web browser tab with the M269 cover notebook. It looks like this, but with a longer table of contents: Figure 1.3.5 16 Chapter 1. Introduction Algorithms, data structures and computability 3. Click on the ‘Introduction’ link. You get something like this in a new tab: Figure 1.3.6 1.3. Software 17 Algorithms, data structures and computability 4. Click on the link to the fourth section, ‘Notebooks’. You get something like this in a new tab: Figure 1.3.7 18 Chapter 1. Introduction Algorithms, data structures and computability As the last three steps show, every time you click on a link to a notebook, it’s opened in a new tab. Unfortunately, if the notebook is already open, the browser will open another copy of that notebook. It’s therefore easy to end up with lots of tabs, several of them showing the same notebook. Make sure you close notebooks that you don’t need anymore. (I’ll tell you how to properly close a notebook later.) Avoid clicking on the ‘previous section’ link at the end of each notebook: you probably have it already open. You can easily see which sections you opened from the tab titles: they start with the chapter and section number. Note: With multiple tabs open, you may prefer to list them vertically, so that you can read the full tab name. Most browsers have extensions that list tabs vertically instead of horizontally. Now you can stop reading the M269 book in PDF or HTML and switch to notebooks: start reading the Section 1.4 notebook you just opened. 1.4 Notebooks As I wrote at the end of the previous section, I’m assuming that you’re reading this section not in the PDF or HTML format, but as a notebook. This section explains how to use notebooks. To avoid problems, don’t click on anything until I tell you to. Info: Much of this and the following sections also applies to other Jupyter interfaces, like JupyterLab and Visual Studio Code. 1.4. Notebooks 19 Algorithms, data structures and computability 1.4.1 Interface Your screen should look similar to this: Figure 1.4.1 At the very top, next to Jupyter’s logo, is the name of the notebook. Jupyter regularly saves the notebook automatically. If there are no changes, or all have been saved, you’ll see next to the notebook name the indication ‘(autosaved)’, otherwise you’ll see ‘(unsaved changes)’. Autosaving is a blessing and a curse. On the one hand, you won’t lose any modifications to a notebook (if for example the power fails), except for those made in the last few minutes. On the other hand, if you get into a knot with all the modifications made, you only have the latest autosaved version, not the original notebook, to start anew. Fortunately, Jupyter provides the best of both worlds. You can explicitly save a notebook, which will also create a checkpoint. Jupyter only keeps the latest checkpoint of each notebook. You can discard the current state of the notebook and reinstate the saved checkpoint anytime. (I’ll show you how later.) You should save a notebook whenever you have a stable version of it that you may wish to revert to. I recommend saving a notebook the first time you open it, to have a checkpoint with the original notebook. I also recommend saving after completing each exercise. 1. To create a checkpoint of this notebook, press Ctrl-S (short for Control-S) on Windows and Linux, or Cmd-S (short for Command-S) on macOS. The existence of a checkpoint is shown next to the notebook’s name: Figure 1.4.2 Let’s continue with the rest of the notebook’s interface. Below the top row is the menu bar, which gives access to various commands. At the right-hand end of the menu bar are some 20 Chapter 1. Introduction Algorithms, data structures and computability status indicators, explained later. Below the menu bar is the tool bar, with buttons to quickly access some commands. Below the tool bar is the notebook itself. A notebook is a sequence of cells, each being either text or code. (Notebooks can have other kinds of cells, but we won’t use them.) Code cells are written in Python; text cells are written in Markdown, explained in the next section. At any point, a notebook is either in command mode or edit mode. When you open a notebook, it starts in command mode. The currently selected cell has a bar to its left: it’s blue when in command mode and green when in edit mode. When you open a notebook, Jupyter associates a kernel to it to execute the code cells in the notebook. If the programming language is Python, then Jupyter uses the IPython interpreter as the kernel. It extends the Python interpreter with functionality that notebooks rely on. To finish this overview of the interface, follow the notebook’s built-in tour. It explains the status indicators and how to switch between modes, among other things. After the tour, scroll down back to this place, without clicking on anything. 2. To start the tour, select Help > User Interface Tour, i.e. click on the ‘Help’ menu and then select ‘User Interface Tour’. 1.4.2 Reverting to a checkpoint After the tour, the start of this notebook looks like this: Figure 1.4.3 The tour entered edit mode for the first cell, thereby showing the Markdown source of the text. Then the tour returned to command mode, making the bar blue again. To revert to the original notebook, with the formatted text, do this: 1. First select File > Revert to Checkpoint and then select the created checkpoint. Figure 1.4.4 1.4. Notebooks 21 Algorithms, data structures and computability You’ll see a dialogue asking if you really really want to discard all changes and revert to a previous state. 2. Click the ‘Revert’ button in that dialogue. You should now have the original notebook, as in the first screenshot. 1.4.3 Running cells There’s an easier way to reformat a text cell, without having to discard any changes we made. To see how, you must first redo what the user interface tour did. 1. At this stage, the first cell should be selected, with a blue bar. If that’s not the case, click once anywhere on the heading to select it. 2. Press Enter to switch to edit mode. The left bar turns green and the Markdown source appears. 3. Press Esc to switch to command mode. The bar turns blue. You’re now in the same state as at the end of the interface tour. To get back the formatted text, you have to run the cell. Running a text cell formats it; running a code cell executes its code. (We’ll get to code cells in Section 1.6.) Running a cell can be done in three different ways: by using the mouse to select the command from the menu bar or the tool bar, or by pressing a keyboard shortcut. 22 Chapter 1. Introduction Algorithms, data structures and computability Note: To use notebooks productively, I recommend you avoid the mouse and use keyboard shortcuts instead. They are listed in Help > Keyboard Shortcuts, as the tour mentioned, but you only need to learn a few by heart for M269. 4. To run the selected cell, press Ctrl-Enter on Linux and Windows or Cmd-Enter on macOS. (Alternatively, select Cell > Run Cells in the menu bar, or click the ‘Run’ button in the tool bar.) The first cell is now formatted again. 1.4.4 Closing notebooks Now that the notebook is back in its original state, you can close it. You can’t however just close its web browser tab: you must halt (shut down) its kernel too. (I’ll tell you how in a minute.) If you store your notebooks in the cloud, you should close and halt all notebooks when you finish each study session, so that you can continue your study from another computer. Notebooks are interactive web pages and therefore require a web server to manage the interaction with the user, pass code to the kernel for execution, and pass results back to the notebook for display. That web server is Jupyter. If you try to close a notebook with unsaved changes, the server will ask whether you want to stay on the notebook or leave it. If you don’t want to save your latest changes, leave the notebook, otherwise stay on it, wait a moment until it’s autosaved, and then close and halt it. If you want to make a checkpoint of your notebook before closing it you must save it explicitly. If by mistake you closed your notebooks by closing their browser tabs, without halting the corresponding kernels, then shutting down the server will halt all kernels still running. See further below for how to shut down Jupyter. Well, it’s time to properly close this notebook, to move on to the next section or to end your study session. There’s no keyboard shortcut for closing and halting a notebook, to avoid doing it by mistake, but since you’ll be opening and closing lots of notebooks, I suggest you add your own shortcut. 1. Select Help > Edit Keyboard Shortcuts. 2. Scroll down until you see ‘close and halt’. 3. Click on ‘add shortcut’ and type a key combination that doesn’t conflict with existing ones. I chose Alt-Q because it’s easy to remember (quit) and isn’t used by Jupyter or my web browser. Figure 1.4.5 1.4. Notebooks 23 Algorithms, data structures and computability To see how to define other key combinations, scroll all the way down. There’s a help section at the end of the list of all note

Document Details

Tags

Related

Full Transcript

Upgrade to continue