Introduction to Computer Science using Python

Computation & Python Basics

01Algorithms as Recipes 02The Six Operations Behind Every Program 03Primitives, Syntax, and Semantics 04Objects, Types, and Type Casting 05Expressions, Operators, and Types 06Assignment vs. Equality Problem set0/10 Practice∞

01Objects, Names, and Assignment 02String Concatenation, Repetition, and len()03String Indexing and Slicing 04String Immutability and the print() Function 05User Input, Type Conversion, and f-strings 06Comparisons, Booleans, and Logical Operators 07Conditionals: if, elif, and else Problem set0/10 Practice∞

Control Flow & Iteration

01Conditional Branching: if, elif, and else 02Iteration and the While Loop 03While Loops, Counters, and Infinite Loops 04While Loop Variables and Running Products 05The for Loop and range()06The Accumulator Pattern and range()Problem set0/10 MIT problem set0/2 Practice∞

01The break Statement: Exiting a Loop Early 02Looping Over Strings and the in Operator 03Guess-and-Check: Exhaustive Enumeration 04for Loops, Boolean Flags, and Cube Roots 05Nested Loops and Brute-Force Search 06Floats, Binary, and Floating-Point Error Problem set0/10 Practice∞

Numbers & Algorithms

01Converting Integers to Binary (and Negatives)02Why 0.1 Can't Be Stored: Fractions in Binary 03How Floats Are Stored, and Why You Never Use ==04Successive Approximation and the Loop That Never Ends Problem set0/10 Practice∞

01Why Approximation Search Hits a Wall 02Halving the Search Space at Every Step 03Coding Bisection Search for Square Roots 04Fixing Bisection Search for Numbers Below One 05Newton-Raphson: Sliding Down the Tangent Line Problem set0/10 MIT problem set0/1 Practice∞

Functions & Abstraction

01Abstraction and Decomposition: Why Your Phone Is a Black Box 02What a Function Really Is: The Specification and Its Four Parts 03Writing Your First Function: From a Sentence to is_even 04How a Function Call Becomes Its Value: Parameters vs. Arguments 05Return vs. Print: The Mysterious None, and Functions in Real Code 06Building sum_odds: Plan on Paper, Then Catch the Off-by-One Bug Problem set0/10 Practice∞

Scope & Higher-Order Functions

01return vs. print, and the Hidden None That Reveals a Bug 02Turning Bisection Square Root Into a Reusable Function 03Environments and Scope: The Rule Behind UnboundLocalError 04A Function Is an Object: Naming, Passing, and Tracing Calls 05Higher-Order Functions: Building apply(criteria, n)Problem set0/10 Practice∞

Lambdas & Sequences

01Writing Anonymous Functions With Lambda 02Tracing Nested Calls with the Environment Model 03Tuples: An Ordered, Mixed-Type Sequence 04Why Tuples Are Immutable: Nesting and Iteration 05Tuple Unpacking: One-Line Swaps and Many Returns 06The Star (*args), Lists, and Pythonic Loops Problem set0/10 MIT problem set0/3 Practice∞

Mutating Lists

01Lists Mutate, Tuples Don't: The Name vs the Object 02append: Growing a List and the None Trap 03Dot Notation: Building and Filtering Lists 04split and join: Converting Between Strings and Lists 05sort vs. sorted: Mutate in Place or Return a New List 06Writing Functions That Mutate a List In Place 07Appending While Looping, and extend vs append 08Reassignment vs Mutation, Proven with id()Problem set0/10 MIT problem set0/1 Practice∞

Aliases & Copies

01Cloning with L[:]: Mutating a List In Place 02del, pop, and remove: Three Ways to Delete 03The Loop That Skips: Removing While Iterating 04Aliases vs Clones: Why L2 = L1 Is Not a Copy 05Shallow vs Deep Copy: copy.copy and copy.deepcopy Problem set0/10 Practice∞

Comprehensions, Testing & Debugging

01List Comprehensions: Your Build-a-List Loop in One Line 02Reading Any Comprehension: Iterable, Expression, Condition 03Default Parameters: Defaults Last, Keywords at the Call Site 04Returning a Function Object: return g, Not return g()05Catching a Returned Function: Two Names, One Object 06Unit, Regression, and Integration Testing 07Black Box vs Glass Box: Where Test Cases Come From 08Debugging by Bisection: Print Statements as Evidence Problem set0/10 Practice∞

Exceptions & Assertions

01try and except: Catching an Exception Instead of Crashing 02Named Exception Handlers, else, finally, and raise 03raise ValueError and assert: Enforcing Your Docstring 04One Empty List, Four Designs: Crash, None, Default, Assert Problem set0/10 Practice∞

Dictionaries

01Why Lists Fail at Lookup: Parallel Lists and Nested Search 02Dictionaries: Custom Keys, Curly Braces, and KeyError 03Mutating a Dictionary: Add, Overwrite, del, and in 04keys(), values(), items(): Three Windows Into a Dictionary 05Hashing and Immutable Keys: Why a List Can't Be a Key 06Case Study: Building a Word Frequency Dictionary 07Ranking Words by Deleting Them: The Cost of Mutation Problem set0/10 MIT problem set0/8 Practice∞

Recursion

01Multiplying With Only Addition: From Loops to a Smaller Copy 02Writing mult_recur: Base Case, Recursive Step, and the Call Stack 03Divide and Conquer: The Regrade Chain and Writing power_recur 04Recursive Factorial Acted Out: Environments and When to Recurse Problem set0/10 Practice∞

01fib_recur: Two Recursive Calls and an Exploding Call Tree 02Memoization: One Dictionary Cuts 11 Million Calls to 65 03Counting Basketball Scores: Three Base Cases, Three Branches 04Recursion on Lists: Peel One Element, Trust the Rest 05Debugging a Recursive Search: Print, Fix, and Return Types 06Nested Lists: Flatten, Search, and Why Loops Fall Short 07Reversing a List Recursively: The Brackets That Make It Legal 08deep_rev: One Type Test Reverses Every Layer Problem set0/10 MIT problem set0/3 Practice∞

Classes & Objects

01Class vs Instance: The Blueprint Behind Every Object 02Choosing Data and Behavior: Elevators, Employees, and Stacks 03class Coordinate(object): Implementing a Type vs Using It 04The __init__ Constructor: Why Every Method Starts With self 05Creating Instances: Coordinate(3, 4), Dot Notation, and Memory 06Methods and the Dot Operator: distance, and How self Gets Bound Problem set0/10 MIT problem set0/3 Practice∞

Composition & Dunder Methods

01Data Attributes vs Parameter Names: What self Guarantees 02Returning a Value vs Mutating the Object: Writing to_origin 03Composition and ValueError: A Circle Made of Coordinate Objects 04Before the Dot Becomes self: Writing a SimpleFraction Class 05Every Operator Is a Method: Meet Python's Dunder Names 06The __str__ Method: You Decide What print Shows 07Overloading * and float() for a Fraction Class 08Inside reduce: a Nested gcd and the Branch That Returns an int Problem set0/10 Practice∞

Inheritance

01Data and Procedural Attributes: Building the Animal Class 02Getters, Setters and __str__: Why the Method Outlives the Attribute 03Attribute Abuse From Outside, and a Dictionary of Animal Objects 04make_animals: Walking Two Lists in Step to Build a List of Objects 05Hierarchies and Subclasses: The Three Moves a Subclass Can Make 06class Cat(Animal): Inheriting __init__ and the Chain Python Climbs 07Overriding __init__: Person Calls Animal.__init__ By Name 08Student, a Subclass of a Subclass, and the Rabbit Class Variable 09__add__ and __eq__ on Rabbits: Operator Overloading With Shared IDs Problem set0/10 MIT problem set0/5 Practice∞

An Object-Oriented Case Study

01Designing a Workout Class: __init__ Makes Five Attributes From Three 02Two State Dictionaries: __dict__ on the Class and on the Object 03A Getter That Estimates: Class Variables, None, and datetime 04parser.parse and Where a Class Variable Actually Lives 05class RunWorkout(Workout): Inheritance and super().__init__06One __str__ in the Parent, Three Kinds of Workout Printing 07A Subclass Where Its Parent Goes, and Positional Argument Order 08Overriding get_calories: How Python Picks Which Method Runs 09__eq__ With super(), and the Last Word on Building Classes Problem set0/10 MIT problem set0/4 Practice∞

Program Efficiency

01Correct Isn't Fast: time.time() and Three Functions Built to Be Measured 02Timing Nine Input Sizes, and Four Reasons the Seconds Measure the Machine 03One Unit per Operation: Costing Three Functions by Hand, Then in Code 04Ten Times the Input, a Hundred Times the Work: Reading Operation Counts Problem set0/10 Practice∞

01A Finer Clock: time.perf_counter and a Runtime That Never Moves 02Which Parameter Costs Time? compound, sum_of, and One Linear Shape 03Brute Force, Bisection, or in: Timing Three Searches to 100 Million 04A Loop Inside a Loop: the diameter Function and Quadratic Growth 05Counting Operations: Exact Formulas and a Program That Counts Itself 06Order of Growth: What to Measure, Which Input, and the Worst Case 07Big O: An Upper Bound That Only Has to Hold Past the Crossover 08Big Theta: Bounded From Both Sides, Keep Only the Dominant Term 09Reading Theta Off the Loops: Two Laws and Six Complexity Classes Problem set0/10 Practice∞

A Finer Clock: time.perf_counter and a Runtime That Never Moves

Why does a finer clock suddenly show real times, and what does it look like when a function's runtime never moves at all?

Finger exercises

Short drills on what this video just taught. Write the code, run the checks, and reveal the answer only if you are stuck.

0 / 5 passed

The ordinary clock moves in whole ticks of about a thousandth of a second: at any instant it shows the last tick that has passed, not the nearest one, so 12.3456 seconds reads as 12.345. The // operator may be useful. Define tick_reading(instant, tick) that returns what a clock with tick size tick shows at the true time instant (both in seconds).
1
2
3
4
5
def tick_reading(instant, tick): # your code here: what a clock that moves in whole ticks shows at this instant return ...
Python runs in your browser
⌘/Ctrl + Enter runs
returns a time in seconds
shows the last tick that has passed, not the nearest one
a call 3e-7 seconds long reads as zero on a millisecond clock
a clock ticking every hundred-millionth of a second sees the same call

←Previous Ten Times the Input, a Hundred Times the Work: Reading Operation Counts Next Which Parameter Costs Time? compound, sum_of, and One Linear Shape →

Your summary note

1. Resolution of the performance counter versus time.time()
  Write the two resolutions side by side - about $10^{-8}$ seconds for time.perf_counter() and about $10^{-3}$ for time.time() - and record that short functions once timed at zero now show a real time.
2. The timing recipe as a difference
  List the steps - read the counter into t, call the function, read again, subtract for dt - and record that the counter gives a position in a time frame, not an absolute date.
3. Input sizes as powers of ten
  Write the loop that builds L_N from [1] by appending L_N[-1]*10 eight times, list the nine sizes up to $10^8$ , and trace the timing loop that prints dt and 1/dt for each N.
4. Constant time: convert_to_km across eight orders of magnitude
  Copy convert_to_km and its timing table, record that every input from 10 to $10^8$ takes between 3.00e-07 and 7.00e-07 seconds, and write the outlying first row's 4.30e-06 as $10^{-8}$ seconds.
Attempt 1 of 2