Week 13 — Readings & Resources

Introduction to Computer Science Free sample edition

Your primary reading is Chapter 13 (in this module). Everything below is the optional, go-deeper layer — pick what helps, skip the rest.

How to use this page

This page has 11 items (5 readings and 6 videos). Allow 90–107 minutes for everything. Each group points back to the matching chapter section and class-session segment, so use the full menu when you want more, or take the quick path below.

Every video here has captions: turn them on with the CC button in the player. The chapter covers the same ideas in text.

Pick-one quick path (19–21 min total)

① Checking every item, and counting the checks

Chapter 13, Section “Check every item in turn: linear search” · Session 1, Segment 2, “Linear search and the comparison counter” · Remember: linear search checks items from the front, and a missing target costs a check of every item.

DSA Linear Search — W3Schools — a one-screen reference with an animation and a try-it box; read Manual Run Through, Linear Search Implementation, and Linear Search Time Complexity, and predict how many values the search checks before you press run. This builds on Week 9's work with lists, since the search walks a list by its index. (reading, 6–8 min)
Learn Linear Search in 3 minutes — Bro Code — a short demo of a search that walks an array one item at a time and reports the index or -1; the code is in Java, so read it for the idea, then write the same function in Python in your browser runner. Use it while working through the Week-13 module overview. (video, 4 min) (captions: automatic)
How Binary Search Makes Computers Much, Much Faster — Tom Scott — a seven-minute explainer of binary versus linear search and of the sorted indexes that let a database halve its search; listen for why the items have to be kept in order before halving can work. (video, 7 min) (captions: creator)

② Halving a sorted list

Chapter 13, Section “Halve the list: binary search” · Session 1, Segment 4, “Binary search and its precondition” · Remember: binary search compares with the middle item and throws away half, and it only works on a sorted list.

Binary Search, With Code — Programiz — a short explainer with step-by-step pictures and Python code; read Binary Search Working and the Iteration Method, and compare its low, high, and mid with this week's lo, hi, and mid. Stop here before the recursive method; next week takes that up. (reading, 8–12 min)
Binary search in 4 minutes — Michael Sambol — a four-minute walk through an example search on a sorted array, then the code and its time complexity; pause before each new middle item and predict which half is thrown away. (video, 4 min) (captions: creator)

③ Sorting pass by pass, and naming the growth

Chapter 13, Section “Name the growth: Big-O” · Session 2, Segment 7, “Selection sort and the growth classes” · Remember: selection sort's comparisons quadruple when the list doubles, and Big-O names how a step count grows, not the exact count.

Selection Sort Algorithm — Programiz — a pictured walk through each pass; read Working of Selection Sort and Selection Sort Complexity, and check that its comparison count matches the chapter's formula for a list of five. (reading, 6–10 min)
Big-O: How Code Slows as Data Grows — Ned Batchelder — the written version of a PyCon 2018 conference talk; read from the start through the jelly-bean jars and the encyclopedia search, where doubling the data adds one divide-in-half step, and skip the timing figures later on, since this course counts steps rather than seconds. (reading, 15–20 min)
Selection sort in 3 minutes — Michael Sambol — a three-minute, step-by-step run of selection sort on a short array; count the comparisons as you watch and check your count against n(n − 1) ⁄ 2. (video, 3 min) (captions: creator)
Learn Big O notation in 6 minutes — Bro Code — a quick tour of Big O notation, a worked example, and a comparison of runtime classes; at each class the video names, say which program from this week belongs to it. (video, 6 min) (captions: automatic)
Big-O: How Code Slows as Data Grows, PyCon 2018 — PyCon 2018 — the recorded talk behind the written version above, for when you would rather listen; watch the opening chapters, Terminology, Counting beans, and Finding words, and treat the rest as optional depth. (video, 29 min) (captions: automatic)

Optional one-stop reference (free online reference)

bisect, Array bisection algorithm — Python Software Foundation — the official documentation for the standard library's own halving tool on a sorted list, the course's free reference for every language fact; read the opening paragraph, which names the bisection algorithm and its use on a list kept in sorted order, and skip the function reference below it. (reading, 2–4 min)

Heads-up (links rot): these point to outside sites that occasionally move or rename pages. If a link ever fails, tell your instructor and use the reference above in the meantime.

Provenance: Built with The Course Maker · samples.thecoursemaker.com