raise first argument to power of second
1.2 pow(100,2)
argument
1.3 (defining new functions)
default argument values
1.4 if arg provided, default is ignored
xxx // 10 removes rightmost value
modulus % gives remainder
Conditional Statements
t or f
booleann
, <, >=, <=, ==, !=,
= repeat while a condition stays true
stop until eigth fibb number
End when reach return or early stop from
inside (if statements)
while loop
rebind name pred to value curr & curr to
pred + curr
pred, curr = curr, pred + curr
right of = evaluated before rebinding
control c to force stop looop
expression in boolean context + quoted line
of text thats displayed if expression
Assertations: assert statements to verify evaluates to false
expectations; ex: output tested
a test function! runs a bunch of assertations
1.5
Testing
Then Python can run those examples and
check the outputs match.
embedd test in docstrong, see if results
match
Doctest Running doctest
base/edge cases (smallest valid input, like
fib(2))
What makes a “good” test set? typical case
large/extreme case
print(...) →
shows something on the console
immediately (output)
Truthy values all values not 0 or empty
Falsey values empty or 0 values---includes none
if not returned--> returns none print(square(4))
if A false, false
A and B True if both A & B are both true
Lab
evaluates to first falsey/false value or the
goes from left to right
Boolean Operators last truthy values
True if one or the other is true
A or B
Evaluate to first truthy value or last falsey
value
Print(...) returns None
Python evaluates the entire right-hand side
first, then assigns the results to the left-hand
side names.
more_chocolate, more_cake = chocolate(),
prints are by product- not assigned
cake
HOF returns functions and takes functions
as arguments. NOT data
ASSIGNMENT: with and w/o ()
ex using lambda
map means: apply square to each number
map(square, range(5))
from range(5)
predicate = a function that takes one
element from sequence and returns
filter(predicate, sequence)
True/False to decide which original items
to keep.
Reduce takes in a function that successively
combines two items of the second input.
First the function is called with items 0 and
reduce (function, sequence) 1, then that result is "combined" with item 2,
that result item 3 and so on.
1.6 (High order functions &
sequences)
from left to right, does whatever combining
function you give it.
sharing names among nested def
Lexical scope
all can use a!
way to create function w/o giving its name
Lambda expressions lambda x: x * x left of : is input!
lambda expression must be single
expression ( part after :)
this also allowed cuz single expression
when given x, apply g then apply f
a function that takes another function and
returns a new function (usually the old one
+ extra behavior).
Function Decorators
rational(n,d)
list() --> creates [] list
2.2 Data abstraction get(index) is a function that returns x if you
ask for index 0, and y if you ask for index 1.
Then pair returns this get function.
pairing
p is a callable function
p is now the get function, and stores 20 as x, 14 as y.
len(list) --> return length of sequence
* operator returns repetitions of original list
example another way-- for xx in xx
sequence unpacking
takes two integer arguments, first number =
and one < last number
Ranges(a ,b )
if only one given, starts at 0
not for statement
list comprehensions remember []
Sequence processing sum, min, max
aggregation
functions that take other functions as inputs
Higher order functions
in & not in
membership
evaluates true of false --> whether an
element appears in a sequence
Sequence abstraction
[starting index of slice : one beyond ending
2.3 Sequences index]
Slicing
any bound omitted assumed to be extreme
value, 0 or ending index
len for strings return the number of letters
" in "
Strings membership
matches substrings (letters ) rather than
elements
str() creates strings
a root (the top node)--label
zero or more branches (children), and each
way to store hiearchies
branch is itself a tree
a leaf is a tree with no branches
stored as list:[ label, branch1, branch2,
branch3, ... ]
Trees
ex
defined
decision tree for "“How can I write n as a
sum of numbers ≤ m?”
Partition Tree
pair containing first element of sequence
and the rest of the sequence
empty= end
[start, rest] rest of a linked list is a linked list or 'empty'
Linked list
check whether linked list
build big list by. building small list and
recursive construction
combining them
Written with {} containing key: value
pairs, e.g. {"bob": "Team A"}
Dictionary (dict) Read: d[key]
Add/overwrite: d[key] = value
.items() gives all pairs
d.keys() Returns a view of all the dictionary’s keys.
Methods d.values() eturns a view of all the dictionary’s values.
looks up a key in a dictionary. If the key exists: returns its value.
d.get(key, default) key= expects a function that takes one item
no brackets!
add value through append to key in
dictionary
Dictionaries d[key].append()
works when dictionary values are lists
It still returns a key from the dict,
but it compares keys using
some_function(key).
min(d, ...) iterates over the dict's keys by
default. The key= parameter says: "don't
min(d, key = xxx) compare keys directly — instead, compare
them by transforming each key first
using this function."
w/o key, compare key strings alphabetically
creating dictionaryes using {} comprehensoin!
Mutable: can change in place (same object) list, dict, set
Immutable: cannot change in place (new
int, float, bool, str, tuple
object created)
immutable sequences that may contain
mutable things
Tuples
ex: mutate inner list
list() → []
list(iterable)→ turns the iterable into a list
list(existing_list) → shallow copy (new outer
list, same inner objects)
Adds multiple elements to the end of a list
(in-place).
extend — unpacks an iterable, adds each
list(...) a.extend([])
element
key difference
Adds one element at a specific index (in-
place), shifting everything to the right.
Mutable data
a.insert( , )
You make one function that can do multiple If you want inner to change count that lives
actions depending on a message you pass in.' in outer, you must say nonlocal count.
Message passing- dispatch function
⬆️ c remembers state bc count is in outer
frame
instead of if/elif. store behaviors in
dictionairies
Key = message name
Value = function to run
Dispatch Dictionaries
dispatch here is name of dictionary
dispatch['inc'] is a function dispatch['get'] is a function
dispatch['inc]() means:
look up the function stored under key 'inc'
call it with ()
function is recursive if it calls itself, or calls
another function that calls it back
Base case (stop) When the problem is “already solved”.
Turn the problem into the same problem
Recursive step (smaller problem)
but smaller, and call the function again.
example
the result is from the 叠加
of the part you
plus from the recursion function. which
slowly builds up your end result
in many questions, try to see if isolating
last/first number, and do that one by one
can give result
n%10 = gives last digit
n//10=everything except last digit
n! = n * (n-1)!
base: 1! = 1
Factorial (recursion vs iteration)
recursive factorial: solve n by using
solutions to n-1
iterative: builds upwards
function calls itself more than once in onee
activation
fibonacci example
Recursion give two options and compare
example
prev is last number picked in subsequence
so far
Tree recursions
helper(total - coin, coin) = you use at least
one of this coin
two choices
helper(total, next_smaller_coin(coin)) = you
use zero of this coin
coin partion example
Partions
the result comes from adding the 1s from
return
partions
Ways example ways if step + ways if jump
step (move forward one spot) or jump
(move forward two spots)
prints after recursion happen in reverse
Printing & recursions
order.
you’re only allowed to use the constructor +
selector functions the ADT gives you, not cannot directly adress to raw data
“peek inside” the raw data structure.
Constructor: makes an ADT value. ex: point(x, y), empty_board()
object is a data structure that contains many
data info
only accessed through selectors, cannot
makes a object
directly access
cluster is a list of restaurant object
ex: restaurant_location(r)[0] for r in
cluster this means: go though each restuarant
object at a time, and take the first
ADT (Abstract Data Types) element in the object
ex: x_point(p), y_point(p), rows(board),
Selector / accessor: extracts information.
diagonal(board, i)
Abstraction barrier: rule that client code
must only use the interface, not the
internal structure.
Internal representation: the actual data
structure used under the hood
Data c88c (list/tuple/dict/string/etc).
way to bundle data & behavior tgt into
objects
self is just the object to the left of the dot.
the blueprint/template
defines what attributes/methods all objects
of that type will have
structure
The init method the constructor
called automatically when creating new
object
Defining a class
Class sets up starting values
self refers to specfic object/instance being
created
call class like a function to create new
instances
Creating object from a class specific object created from a class
basically what you get when you create smt
Object/Instance
from the class.
a = Account('Kirk') creates one account
function defined inside a class
always takes self as its first parameter
defining behavior w methods
calling a.deposit(15) automatically passes a
as self.
OOP (Object oriented
data tied to one specific object
programming)
self.balance self.holder
only runs once at creation
Set in __init__
basically a method
belong to one object
Attributes
1. Instance attributes of obj — found?
set with self.x = ...
return it.
inside __init__
belongs to the class itself. shared across all
instances
2. Class attributes of the class — found?
Dot expression lookup order return it (or return a bound method if it's a set directly in class body
function).
class Account:
interest = 0.02
instance att shadows class att
If one class is a specialized version of
another, it can inherit from it.
Subclass gets everything from the parents
Inheritance
for free, only define whats different
Writing a subclass
Inheriting from more than one class
Multiple Inheritance
Method resolution order(Who wins when
both parents define the same method?)
Lab
methods in class
repeat (building. methods in clas)
a linked list is a chain of nodes, where each
node holds a value AND a pointer to the
next node
Each node has exactly two things: first
(the value) and rest (a pointer to the next
node, or empty if it's the last one)
example. linked list as class. Each node is a instance
Linked list-class
ex: adding methods
w recursion
iterative way
lst[0] is the first element, lst[1:] is
everything after it. So this says: "make a
node with the first element, and its rest is
the linked list version of everything
List to linked list
remaining."
Link is a class that takes in (first, rest)
tree has a label (its value) and a tuple of
branches(each is also tree). no branch=leaf
branches always return a LIST
recursive pattern: to do smt to whole tree, do it
to label, then to each branch
t.branches
by: for b in t.branches you are going
through EACH branch (tree(#) in that layer. w. recursion: helper(b, depth+1). By using b
-recursing allows you to go beyond that you can go to deeper layers
layer
Trees--class is_leaf
need t.label = t.label **2 to actually mutate
the label
simply square(t.label) doesn't mutate!
square the labels.
max path sums
max path sums
Questions
make even
t.branches gives list of branches in the tree.
for b in t.branches loops over each branch
for b in t.branches goes down in each
Prune small surviving branch and prune there too@
lambda b: b.label to get the number in each
tree in each Tree()
Set: collection of distinct values. Learn how
you store that & How fast you search it.
three rep w/ diff. speed
store elements in linked list, no
sorting/structure
Sets--Class Unordered list check: walk start to end, scan everything
problem: look through every element
keep list in inc. order. so when searching
value, see a bigger value, you can stop
Ordered
speed faster
arange values in tree. Left is aways smaller,
right always bigger
search: compare your value w/current
Binary
nodes. if too small, go left. too big, go right.
Each step cuts remaining candidates in half.
how does it scale? input change--output
change? program fast or slow.
shape of growth as n gets large
Efficiency
Screenshot 2026-04-08 at 15.48.46.png
Θ(1): nothing changes
Θ(log n): barely changes (adds a few steps) cut search space in half
complexity analysis:If I make the input 10x
Θ(n): 10x more work
bigger, what happens to the work
Θ(n²): 100x more work
Θ(φⁿ): catastrophically more work
eager= compute/store now
Lazy = compute when asked
Lazy evaluation
Range is lazy.
same & new iterator
object that gives elements one at a time via
next(); moving thru data
remembers where it is, raises StopIteration
when complete
Two iterators on the same list are
Iterators independent — they each track their own
position
★ Two names for the same iterator share
one position (they're the same object)
★ iter(iterator) returns the iterator itself —
no copy made
★ A for-loop uses __iter__ and __next__
under the hood automatically
iter() to make one
next() to advance
special kind of iterator you define w/
function that uses yield instead of return build custom iterator, write w/ yield
-it pauses and resumes execution
A generator does nothing until something
externally triggers it. There are two ways:
Calling a generator function does NOT run
any of its code. It just creates the generator
object. A generator function runs only when you
Implicit Sequences call next() on it, and even then it only
runs until the next yield, then pauses
again.
Generators
yield
generator function vs regular function
bc its a generator, each time i
next(hailstone) it gives me next value of n
EXAMPLE
Without the n = part, n never changes, so
the while loop runs forever with the same
value — infinite loop!
lazily computed linked list. rest is only
computed when asked
persistent, functional version of iterator.
Streams head unchanged,always known; tail is
lambda waiting
can represent infinite sequences. Tail is
commputed on demand via stored lambda
Comparison
conaumed: once you read or next() through
iterator, its gone, cannot go back to start.
You write step-by-step instructions for HOW
to do it
Imperative
python
Everything is functions, no changing state
Functional
haskell
Programming Paradigms
Everything is objects with methods
Object oriented
OOP, java, python
You describe WHAT you want, not HOW to
get it
Declarative
SQL, bc for ex: select name from cities
where latitude > 43; you dont tell how just
your demand
build one using select with union to stack
rows, then give it a name with create table.
Tables = the data Structure
Table = the whole grid of data
Row / record = one entry (one city)
Column = one attribute (latitude)
union = stack rows from two tables together
where you query the data, filter rows,
order, sort
select (what columns) from (which table) select: picks which column you want to
where (filter rows) order by (sort). see from table
select name from cities where latitude > 43
Structure, there is also having and LIKE select name, 60*abs(latitude-38) as distance
compute new values in select
from cities
LIKE: pattern matching on text. Where
xxx LIKE %H
order by DESC (descending)
HAVING: filters after group by ,whereas
select where filters BEFORE grouping.
Aggregate functions only can be used in
SELECT or HAVING
1.when you put two table names in from ,
SQL makes every combo of rows. 2. Use
where to keep only ones that match
resukt: only rows where names match
declarative programming-SQL
JOIN
FROM table1
JOIN table2 ON <condition>
% = anything can go here
USING LIKE
collapse many rows into one summary
value
max(weight) → 12000 — biggest value
min(legs) → 2 — smallest value
sum(weight) → 12056 — total
count(*) → 6 — number of rows
Aggregation Use of aggregate functions
legs: what to group by, then find
group by-- split into buckets, then agg. each max(weight) of each group
bucket
results
Using with, you can define a table that
with. creates a temp. named table
references itself
start w base case, add rows by referencing
table your building
Recursion
if want entire table. select * from ints;
select n; only wants to see single column
table n
MUST END ALL SQL W/ ;
n //= 10 --> allow it to check every pair of
adjacent digits by repeatedly chopping off
the last digit.
n // 10 --> chops off last digit
n % 10 --> gives the last digit
While problems
while, and/or, loops
Iteration Problems
if a<= b: is to ensure way of multiplying
won't overlap. ex: 2 x 6 and 6 x 2
High order functions
HOF returns functions! not data
remember the use of brackets
List comprehensions
in = in means membership: “is this inside
that container?”
when print gives function
Mint refers to class itself, the class attribute.
Self.year is the year of the specific instance.
in this case. Mint.present_year is class 统一的
hard questions i struggled with OOPS current year & self.year is year specific coin
value of the coin plus one extra cent for was stamped/made
each year of age beyond 50.
use of max to +1 cent every year over 50
super().action(gamestate) means calls
action(gamestate) from parent class which
Class
is container ant! so you dont need to rewrite
the action again
super() -- in last line
class whose objects are iterable iterators,
and this specific one restarts every time a
new for loop begins.
init runs once you create the class
iter runs when a for loop starts (restarting,
since current changes after one loop)
and next runs every loop round
Iter
formula/structure for __next__
if xxx:
raise StopIteration
result=
self.xxx -+ = smt
return result
Iterator count down to 10
generator
countdown to 0 example
example
SQL examples
from matches every possible combo of rows
in the two tables, so you choose the ones allows us to obtain courses grouped by
where the hall (room name) matches, but
excludes the exact same row matches (share
same course)
Complexer tables; using distinct. & Copies
of same table!
Similar. Selects two columns. variations of
the same table
full= full size of turkey at 24 month oldd
full= current weight + how much more
A turkey is expected to increase in weight they'll grow. & months of growth remaining
by 1 kilogram each month until it is 24 = 24 - age
months old. After 24 months, it is not -use of min is to cap age at 24
expected to grow.
1.2 pow(100,2)
argument
1.3 (defining new functions)
default argument values
1.4 if arg provided, default is ignored
xxx // 10 removes rightmost value
modulus % gives remainder
Conditional Statements
t or f
booleann
, <, >=, <=, ==, !=,
= repeat while a condition stays true
stop until eigth fibb number
End when reach return or early stop from
inside (if statements)
while loop
rebind name pred to value curr & curr to
pred + curr
pred, curr = curr, pred + curr
right of = evaluated before rebinding
control c to force stop looop
expression in boolean context + quoted line
of text thats displayed if expression
Assertations: assert statements to verify evaluates to false
expectations; ex: output tested
a test function! runs a bunch of assertations
1.5
Testing
Then Python can run those examples and
check the outputs match.
embedd test in docstrong, see if results
match
Doctest Running doctest
base/edge cases (smallest valid input, like
fib(2))
What makes a “good” test set? typical case
large/extreme case
print(...) →
shows something on the console
immediately (output)
Truthy values all values not 0 or empty
Falsey values empty or 0 values---includes none
if not returned--> returns none print(square(4))
if A false, false
A and B True if both A & B are both true
Lab
evaluates to first falsey/false value or the
goes from left to right
Boolean Operators last truthy values
True if one or the other is true
A or B
Evaluate to first truthy value or last falsey
value
Print(...) returns None
Python evaluates the entire right-hand side
first, then assigns the results to the left-hand
side names.
more_chocolate, more_cake = chocolate(),
prints are by product- not assigned
cake
HOF returns functions and takes functions
as arguments. NOT data
ASSIGNMENT: with and w/o ()
ex using lambda
map means: apply square to each number
map(square, range(5))
from range(5)
predicate = a function that takes one
element from sequence and returns
filter(predicate, sequence)
True/False to decide which original items
to keep.
Reduce takes in a function that successively
combines two items of the second input.
First the function is called with items 0 and
reduce (function, sequence) 1, then that result is "combined" with item 2,
that result item 3 and so on.
1.6 (High order functions &
sequences)
from left to right, does whatever combining
function you give it.
sharing names among nested def
Lexical scope
all can use a!
way to create function w/o giving its name
Lambda expressions lambda x: x * x left of : is input!
lambda expression must be single
expression ( part after :)
this also allowed cuz single expression
when given x, apply g then apply f
a function that takes another function and
returns a new function (usually the old one
+ extra behavior).
Function Decorators
rational(n,d)
list() --> creates [] list
2.2 Data abstraction get(index) is a function that returns x if you
ask for index 0, and y if you ask for index 1.
Then pair returns this get function.
pairing
p is a callable function
p is now the get function, and stores 20 as x, 14 as y.
len(list) --> return length of sequence
* operator returns repetitions of original list
example another way-- for xx in xx
sequence unpacking
takes two integer arguments, first number =
and one < last number
Ranges(a ,b )
if only one given, starts at 0
not for statement
list comprehensions remember []
Sequence processing sum, min, max
aggregation
functions that take other functions as inputs
Higher order functions
in & not in
membership
evaluates true of false --> whether an
element appears in a sequence
Sequence abstraction
[starting index of slice : one beyond ending
2.3 Sequences index]
Slicing
any bound omitted assumed to be extreme
value, 0 or ending index
len for strings return the number of letters
" in "
Strings membership
matches substrings (letters ) rather than
elements
str() creates strings
a root (the top node)--label
zero or more branches (children), and each
way to store hiearchies
branch is itself a tree
a leaf is a tree with no branches
stored as list:[ label, branch1, branch2,
branch3, ... ]
Trees
ex
defined
decision tree for "“How can I write n as a
sum of numbers ≤ m?”
Partition Tree
pair containing first element of sequence
and the rest of the sequence
empty= end
[start, rest] rest of a linked list is a linked list or 'empty'
Linked list
check whether linked list
build big list by. building small list and
recursive construction
combining them
Written with {} containing key: value
pairs, e.g. {"bob": "Team A"}
Dictionary (dict) Read: d[key]
Add/overwrite: d[key] = value
.items() gives all pairs
d.keys() Returns a view of all the dictionary’s keys.
Methods d.values() eturns a view of all the dictionary’s values.
looks up a key in a dictionary. If the key exists: returns its value.
d.get(key, default) key= expects a function that takes one item
no brackets!
add value through append to key in
dictionary
Dictionaries d[key].append()
works when dictionary values are lists
It still returns a key from the dict,
but it compares keys using
some_function(key).
min(d, ...) iterates over the dict's keys by
default. The key= parameter says: "don't
min(d, key = xxx) compare keys directly — instead, compare
them by transforming each key first
using this function."
w/o key, compare key strings alphabetically
creating dictionaryes using {} comprehensoin!
Mutable: can change in place (same object) list, dict, set
Immutable: cannot change in place (new
int, float, bool, str, tuple
object created)
immutable sequences that may contain
mutable things
Tuples
ex: mutate inner list
list() → []
list(iterable)→ turns the iterable into a list
list(existing_list) → shallow copy (new outer
list, same inner objects)
Adds multiple elements to the end of a list
(in-place).
extend — unpacks an iterable, adds each
list(...) a.extend([])
element
key difference
Adds one element at a specific index (in-
place), shifting everything to the right.
Mutable data
a.insert( , )
You make one function that can do multiple If you want inner to change count that lives
actions depending on a message you pass in.' in outer, you must say nonlocal count.
Message passing- dispatch function
⬆️ c remembers state bc count is in outer
frame
instead of if/elif. store behaviors in
dictionairies
Key = message name
Value = function to run
Dispatch Dictionaries
dispatch here is name of dictionary
dispatch['inc'] is a function dispatch['get'] is a function
dispatch['inc]() means:
look up the function stored under key 'inc'
call it with ()
function is recursive if it calls itself, or calls
another function that calls it back
Base case (stop) When the problem is “already solved”.
Turn the problem into the same problem
Recursive step (smaller problem)
but smaller, and call the function again.
example
the result is from the 叠加
of the part you
plus from the recursion function. which
slowly builds up your end result
in many questions, try to see if isolating
last/first number, and do that one by one
can give result
n%10 = gives last digit
n//10=everything except last digit
n! = n * (n-1)!
base: 1! = 1
Factorial (recursion vs iteration)
recursive factorial: solve n by using
solutions to n-1
iterative: builds upwards
function calls itself more than once in onee
activation
fibonacci example
Recursion give two options and compare
example
prev is last number picked in subsequence
so far
Tree recursions
helper(total - coin, coin) = you use at least
one of this coin
two choices
helper(total, next_smaller_coin(coin)) = you
use zero of this coin
coin partion example
Partions
the result comes from adding the 1s from
return
partions
Ways example ways if step + ways if jump
step (move forward one spot) or jump
(move forward two spots)
prints after recursion happen in reverse
Printing & recursions
order.
you’re only allowed to use the constructor +
selector functions the ADT gives you, not cannot directly adress to raw data
“peek inside” the raw data structure.
Constructor: makes an ADT value. ex: point(x, y), empty_board()
object is a data structure that contains many
data info
only accessed through selectors, cannot
makes a object
directly access
cluster is a list of restaurant object
ex: restaurant_location(r)[0] for r in
cluster this means: go though each restuarant
object at a time, and take the first
ADT (Abstract Data Types) element in the object
ex: x_point(p), y_point(p), rows(board),
Selector / accessor: extracts information.
diagonal(board, i)
Abstraction barrier: rule that client code
must only use the interface, not the
internal structure.
Internal representation: the actual data
structure used under the hood
Data c88c (list/tuple/dict/string/etc).
way to bundle data & behavior tgt into
objects
self is just the object to the left of the dot.
the blueprint/template
defines what attributes/methods all objects
of that type will have
structure
The init method the constructor
called automatically when creating new
object
Defining a class
Class sets up starting values
self refers to specfic object/instance being
created
call class like a function to create new
instances
Creating object from a class specific object created from a class
basically what you get when you create smt
Object/Instance
from the class.
a = Account('Kirk') creates one account
function defined inside a class
always takes self as its first parameter
defining behavior w methods
calling a.deposit(15) automatically passes a
as self.
OOP (Object oriented
data tied to one specific object
programming)
self.balance self.holder
only runs once at creation
Set in __init__
basically a method
belong to one object
Attributes
1. Instance attributes of obj — found?
set with self.x = ...
return it.
inside __init__
belongs to the class itself. shared across all
instances
2. Class attributes of the class — found?
Dot expression lookup order return it (or return a bound method if it's a set directly in class body
function).
class Account:
interest = 0.02
instance att shadows class att
If one class is a specialized version of
another, it can inherit from it.
Subclass gets everything from the parents
Inheritance
for free, only define whats different
Writing a subclass
Inheriting from more than one class
Multiple Inheritance
Method resolution order(Who wins when
both parents define the same method?)
Lab
methods in class
repeat (building. methods in clas)
a linked list is a chain of nodes, where each
node holds a value AND a pointer to the
next node
Each node has exactly two things: first
(the value) and rest (a pointer to the next
node, or empty if it's the last one)
example. linked list as class. Each node is a instance
Linked list-class
ex: adding methods
w recursion
iterative way
lst[0] is the first element, lst[1:] is
everything after it. So this says: "make a
node with the first element, and its rest is
the linked list version of everything
List to linked list
remaining."
Link is a class that takes in (first, rest)
tree has a label (its value) and a tuple of
branches(each is also tree). no branch=leaf
branches always return a LIST
recursive pattern: to do smt to whole tree, do it
to label, then to each branch
t.branches
by: for b in t.branches you are going
through EACH branch (tree(#) in that layer. w. recursion: helper(b, depth+1). By using b
-recursing allows you to go beyond that you can go to deeper layers
layer
Trees--class is_leaf
need t.label = t.label **2 to actually mutate
the label
simply square(t.label) doesn't mutate!
square the labels.
max path sums
max path sums
Questions
make even
t.branches gives list of branches in the tree.
for b in t.branches loops over each branch
for b in t.branches goes down in each
Prune small surviving branch and prune there too@
lambda b: b.label to get the number in each
tree in each Tree()
Set: collection of distinct values. Learn how
you store that & How fast you search it.
three rep w/ diff. speed
store elements in linked list, no
sorting/structure
Sets--Class Unordered list check: walk start to end, scan everything
problem: look through every element
keep list in inc. order. so when searching
value, see a bigger value, you can stop
Ordered
speed faster
arange values in tree. Left is aways smaller,
right always bigger
search: compare your value w/current
Binary
nodes. if too small, go left. too big, go right.
Each step cuts remaining candidates in half.
how does it scale? input change--output
change? program fast or slow.
shape of growth as n gets large
Efficiency
Screenshot 2026-04-08 at 15.48.46.png
Θ(1): nothing changes
Θ(log n): barely changes (adds a few steps) cut search space in half
complexity analysis:If I make the input 10x
Θ(n): 10x more work
bigger, what happens to the work
Θ(n²): 100x more work
Θ(φⁿ): catastrophically more work
eager= compute/store now
Lazy = compute when asked
Lazy evaluation
Range is lazy.
same & new iterator
object that gives elements one at a time via
next(); moving thru data
remembers where it is, raises StopIteration
when complete
Two iterators on the same list are
Iterators independent — they each track their own
position
★ Two names for the same iterator share
one position (they're the same object)
★ iter(iterator) returns the iterator itself —
no copy made
★ A for-loop uses __iter__ and __next__
under the hood automatically
iter() to make one
next() to advance
special kind of iterator you define w/
function that uses yield instead of return build custom iterator, write w/ yield
-it pauses and resumes execution
A generator does nothing until something
externally triggers it. There are two ways:
Calling a generator function does NOT run
any of its code. It just creates the generator
object. A generator function runs only when you
Implicit Sequences call next() on it, and even then it only
runs until the next yield, then pauses
again.
Generators
yield
generator function vs regular function
bc its a generator, each time i
next(hailstone) it gives me next value of n
EXAMPLE
Without the n = part, n never changes, so
the while loop runs forever with the same
value — infinite loop!
lazily computed linked list. rest is only
computed when asked
persistent, functional version of iterator.
Streams head unchanged,always known; tail is
lambda waiting
can represent infinite sequences. Tail is
commputed on demand via stored lambda
Comparison
conaumed: once you read or next() through
iterator, its gone, cannot go back to start.
You write step-by-step instructions for HOW
to do it
Imperative
python
Everything is functions, no changing state
Functional
haskell
Programming Paradigms
Everything is objects with methods
Object oriented
OOP, java, python
You describe WHAT you want, not HOW to
get it
Declarative
SQL, bc for ex: select name from cities
where latitude > 43; you dont tell how just
your demand
build one using select with union to stack
rows, then give it a name with create table.
Tables = the data Structure
Table = the whole grid of data
Row / record = one entry (one city)
Column = one attribute (latitude)
union = stack rows from two tables together
where you query the data, filter rows,
order, sort
select (what columns) from (which table) select: picks which column you want to
where (filter rows) order by (sort). see from table
select name from cities where latitude > 43
Structure, there is also having and LIKE select name, 60*abs(latitude-38) as distance
compute new values in select
from cities
LIKE: pattern matching on text. Where
xxx LIKE %H
order by DESC (descending)
HAVING: filters after group by ,whereas
select where filters BEFORE grouping.
Aggregate functions only can be used in
SELECT or HAVING
1.when you put two table names in from ,
SQL makes every combo of rows. 2. Use
where to keep only ones that match
resukt: only rows where names match
declarative programming-SQL
JOIN
FROM table1
JOIN table2 ON <condition>
% = anything can go here
USING LIKE
collapse many rows into one summary
value
max(weight) → 12000 — biggest value
min(legs) → 2 — smallest value
sum(weight) → 12056 — total
count(*) → 6 — number of rows
Aggregation Use of aggregate functions
legs: what to group by, then find
group by-- split into buckets, then agg. each max(weight) of each group
bucket
results
Using with, you can define a table that
with. creates a temp. named table
references itself
start w base case, add rows by referencing
table your building
Recursion
if want entire table. select * from ints;
select n; only wants to see single column
table n
MUST END ALL SQL W/ ;
n //= 10 --> allow it to check every pair of
adjacent digits by repeatedly chopping off
the last digit.
n // 10 --> chops off last digit
n % 10 --> gives the last digit
While problems
while, and/or, loops
Iteration Problems
if a<= b: is to ensure way of multiplying
won't overlap. ex: 2 x 6 and 6 x 2
High order functions
HOF returns functions! not data
remember the use of brackets
List comprehensions
in = in means membership: “is this inside
that container?”
when print gives function
Mint refers to class itself, the class attribute.
Self.year is the year of the specific instance.
in this case. Mint.present_year is class 统一的
hard questions i struggled with OOPS current year & self.year is year specific coin
value of the coin plus one extra cent for was stamped/made
each year of age beyond 50.
use of max to +1 cent every year over 50
super().action(gamestate) means calls
action(gamestate) from parent class which
Class
is container ant! so you dont need to rewrite
the action again
super() -- in last line
class whose objects are iterable iterators,
and this specific one restarts every time a
new for loop begins.
init runs once you create the class
iter runs when a for loop starts (restarting,
since current changes after one loop)
and next runs every loop round
Iter
formula/structure for __next__
if xxx:
raise StopIteration
result=
self.xxx -+ = smt
return result
Iterator count down to 10
generator
countdown to 0 example
example
SQL examples
from matches every possible combo of rows
in the two tables, so you choose the ones allows us to obtain courses grouped by
where the hall (room name) matches, but
excludes the exact same row matches (share
same course)
Complexer tables; using distinct. & Copies
of same table!
Similar. Selects two columns. variations of
the same table
full= full size of turkey at 24 month oldd
full= current weight + how much more
A turkey is expected to increase in weight they'll grow. & months of growth remaining
by 1 kilogram each month until it is 24 = 24 - age
months old. After 24 months, it is not -use of min is to cap age at 24
expected to grow.
