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∞

Order of Growth: What to Measure, Which Input, and the Worst Case

If timing and counting both work, why aren't they enough, and which input and which case should an efficiency claim be about?

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

costs holds one function's operation counts at inputs 10, 100, 1,000 and 10,000, each ten times the one before. Small inputs can hide the growth, so let the largest inputs decide. Define behaviour(costs) returning exactly one of the strings 'constant', 'linear', 'quadratic' or 'logarithmic'.
1
2
3
4
5
def behaviour(costs): # costs were measured at inputs 10, 100, 1000 and 10000, in that order. return ... # your code here
Python runs in your browser
⌘/Ctrl + Enter runs
returns one of the four names
reads the convert_to_km, sum_of and is_in columns
reads the diameter, square and binary search columns
lets the largest inputs decide

←Previous Counting Operations: Exact Formulas and a Program That Counts Itself Next Big O: An Upper Bound That Only Has to Hold Past the Crossover →

Your summary note

1. Timing versus counting, and where each falls short
  Compare timing and counting on machine and implementation dependence, note what timing hides on small inputs, and reduce the count $3x + 4$ to what still matters once the input is large.
2. Measuring the algorithm's scalability in terms of input size
  Classify mysum as order $x$ and the nested-loop square as order $x^2$ from how runtime scales when the input doubles or grows 10-fold, and list the four behaviours seen so far.
3. Choosing the input that drives growth
  Vary each quantity in is_in(L, e) in turn (the value of e, the magnitudes in L, the length of L) with a pair of searches each, and record which one drives the runtime.
4. Worst-case analysis of a membership search
  Describe the worst, best and average inputs for is_in and how much of L each one examines, and state that the course always analyses the worst case.
Attempt 1 of 2