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∞

Why 0.1 Can't Be Stored: Fractions in Binary

Why does 0.375 convert to binary in three clean steps while 0.1 explodes into ~50 bits that never settle?

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 binary fraction 0.101 means 1/2 + 0/4 + 1/8 — each digit after the point switches on a negative power of two. Its three digits are given below, left to right. Compute the decimal value of 0.101 and assign it to value.

(Hint: the place values after the point are 1/2, 1/4, 1/8, and / does ordinary division.)
1
2
3
4
5
6
7
# The three digits of the binary fraction 0.101, left to right. digit1 = 1 digit2 = 0 digit3 = 1 value = ... # your code here — the decimal value of 0.101
Python runs in your browser
⌘/Ctrl + Enter runs
is a number
matches binary 0.101

←Previous Converting Integers to Binary (and Negatives)Next How Floats Are Stored, and Why You Never Use == →

Your summary note

1. The meaning of a base-2 fraction 0.abc
  Write that 0.abc in base 2 is a/2 + b/4 + c/8, next to the base-10 reading a/10 + b/100 + c/1000, with each digit 0 or 1.
2. The multiply, convert and shift recipe
  List the three steps and work 0.375 through them: multiply by 2**3 to reach 3, convert 3 to 11, then move the point three places left for 0.011.
3. Hand-trace of the code on 0.625
  Trace the loop that raises p while the remainder stays non-zero, through 0.625, 0.25 and 0.5, stopping at p = 3 with num = 5, then 101 and finally 0.101.
4. Fractions with no short binary form
  Record that 0.1 must be multiplied by roughly 2**50 before it becomes whole, giving about fifty digits, and that other fractions run longer still, potentially infinite.
Attempt 1 of 2