Self-paced course taken summer ‘22, linked here. Beginner programming course using Python — teaches data abstraction, … Great focus on shortcuts and problem-solving with code; has hints of competitive coding strategies. Texts used include Composing Programs by John DeNero. Completed homework linked here.



ch1.1: getting started

  • Python devs emphasized human interpretability of Python code — easy to read/understand
  • an interactive session is signaled by the >>>
  • statements describe actions; expressions describe computations

ch1.2: elements of programming

  • any powerful programming language should be able to describe data and functions, or, “have data and process it”
  • expressions describe a computation and evaluates it to a value
    • infix notation is when operators (+, -, *, /) appear between operands (the numbers)
    • all expressions can be generalized to function notation
  • a call expression applies a function to some arguments
  • not all functions are available by default and many have to be imported through modules
  • = is the assignment operator, which matches names to the results of compound operations or to functions
    • the names are remembered by Python’s interpreter, which means that the interpreter has some kind of memory — the memory is an environment
  • nested function calls repeated the same procedure until the expression is evaluated: first evaluate the operator (function) and then its operands (arguments)
  • pure functions have an input and an output and will always return the same output for the same input
    • can’t have side effects or change behavior over time, making them reliable
    • simpler to test
  • non-pure functions change the state of the interpreter or computer, ex: print
  • a function that doesn’t specify a return value will return None


  • every expression in Python is generalized to function call notation
  • any call expression is made up of an operator and its operands, which are also expressions (possibly made up of more operators and operands)

call expression tree

  • three ways to bind values to names: importing modules, assignment, and def statements (functions)
  • with a frame, a name can only be bound to one value
  • Python evaluates all the expressions to the right of the assignment operator =, and then it binds the resultant values to the name(s) on the left
  • abstraction is the process of naming something complex and treating it as a whole entity without worrying about its details
    • functions are a form of abstraction:
      def <name>(<formal parameters>):
          return <return expression>
      • the function signature (first line) defines how many arguments a function will take — the signature is the name of the object
      • the function body (remainder) is where the computational process happens
  • an environment is a sequence of frames
    • a frame is a bit of a memory that keeps track of what names mean (it’s also called a scope)
    • any name evaluates to the assigned value in the closest frame, starting with the local frame and working towards the global frame
  • to use a local variable from the global frame, you have to return the local variable first (assuming it’s a function call)


ch1.3: defining new functions

  • to define a function is to give a name to a compound operation, which allows the operation to be referred to
  • the def statement and the assignment operator = bind names to values — any previously bindings are lost
  • bindings exist in frames which are layered
    • a local frame is created every time a function is called
      • a name only exists in that frame for as long as the frame exists, ie once the function call is over, any bindings within the function will disappear
  • the scope (existence) of a local name is limited to its function or its frame
  • functional abstraction is the idea that the only thing that matters about a function is its return value, and not the process which that value is computed
    • three core values to functional abstraction: domain, or the set of arguments of a function; range, or the set of values it can return; intent, the relationship between the inputs and outputs

ch1.4: designing functions

  • a function should have exactly one job
  • don’t repeat yourself — if you are copy-pasting code, it can probably be turned into a function
  • triple quoted docstrings at the top of a function body typically describe what the function does
    def pressure(v, t, n):
        """Compute the pressure in pascals of an ideal gas.
        Applies the ideal gas law:
        v -- volume of gas, in cubic meters
        t -- absolute temperature in degrees kelvin
        n -- particles of gas
        k = 1.38e-23  # Boltzmann's constant
        return n * k * t / v
  • default function values can be specified in the function signature

[stopped reading the textbook lol]


  • Python’s interactive interpreter will print any value returned from an expression or function that isn’t None, which represents nothing
  • pure functions return values and have the same output for the same input
  • non-pure functions have an input and output but something else happens before the output, like some text being printed to the terminal
  • a def statement is how a function is created — includes the signature and body, which are bound to the name of the function
    • the frame isn’t created until the function is called
  • multi-frame environments consist of a global frame and then local frames
    • a name evaluates to the earliest assigned instance of a value to that name, whether that be in the local frame or otherwise
  • there are two kinds of division
    • / is called true division which divides like normal, ex: 2013 / 10 evaluates to 201.3
    • // is called floor division which rounds down to the nearest integer, ex: 2013 / 10 evaluates to 201
  • to return multiple values from a function, use a comma
  • Python can run in a file, run in the interactive mode, or run a file in interactive mode
  • Python can run an interactive session by taking code from a function’s docstring
    def divide_exact(n,d):
        """Return the quotient and remainder of dividing n by d.
        >>> q, r = divide_exact(2013, 10)
        >>> q
        >>> r
        return floordiv(n, d), mod(n, d)
    python3 -m doctest -v ["filename"]
  • use the if, elif, else to execute a suite (set of statements after a header) that evaluate to true to a boolean statement
  • boolean statements will always evaluate to either True or False
    • false values: False, 0, "", None
    • true values: anything that isn’t false
  • iteration allows us to repeat stuff
    • for a while loop, we evaluate the header’s boolean expression, and then execute the following suite and evaluate the header again

higher-order functions

  • characteristics of functions
    • domain: the set of all inputs as arguments
    • range: the set of all outputs
  • each function should have exactly one general job
  • an assert keyword can be followed by a boolean expression that will throw an error if the expression evaluates to false
    • this is useful for checking if given arguments are within specifications
  • a higher-order function is a first-class value, and can take another function as an argument, or can also be returned as a return value
    def make_adder(n):
        """Return a function that takes one argument k and returns k + n.
        >>> add_three = make_adder(3)
        >>> add_three(4)
        def adder(k):
        	return k + n
        return adder
    • the function adder is returned from make_adder and assigned to add_three with n=3
  • lambda expressions are expressions that evaluate to functions — use the lambda keyword, ex: square = lambda x: x*xsquare(4) evaluates to 16
    • the function name can be skipped and directly called, ex: (lambda x: x*x)(4) evaluates to 16
  • lambdas can’t use conditionals while def statements can; def statements give functions a name while lambdas don’t (it’s just called a lambda)
  • and and or are logical operators which don’t require all statements to be checked to evaluate fully
    • for and, if the first statement is false, then the whole statement is false
    • for or, if the first statement is true, then the whole statement is true
      • ex: return (n==0) or (1/n != 0), the expression wouldn’t throw a zero-division error because n==0 evaluate to true first so true is returned without considering the second expression
  • a conditional expression can take the form <consequent> if <predicate> else <alternative>
    • the <predicate> is evaluated first, and if it’s true, the expression evaluates to the <consequent> value
    • if <predicate> is false, then the expression evaluates to <alternative>
    print("cons" if 2==2 else "alt")
    # prints cons
    print("cons" if 2==3 else "alt")
    # prints alt


  • a higher-order function is a function that can take another function as an argument, or returns another function as a return value
  • a return statement brings information from a local frame into a global frame (or similar)
  • the parent frame of a frame created from a returned function is the frame where that function was created, which means that function has access to its parent frame values
    • below: make_adder returns a function adder in frame f1; when the new add_three function (a sub-function of adder) is called, it can access values in its parent frame, f1

python tutor frames

  • the environment created by calling a top-level function consists of a local frame followed by the global frame
  • a function can return itself, which can lead to the same function being called on multiple arguments in the same line of code
    • the function does not run forever because the return value is only a function object, and not a call to that function
    def print_all(x):
    	return print_all
    # 1
    # 3
    # 5
  • currying is transforming a multi-argument function into a single-argument, higher-order function
    • when calling add_three, it has access to the f2 and f1 frames which store the variables x and function f



  • abstraction is giving a name to a process and referring to it as a whole and not worrying about the details of the process
    • function names don’t matter for correctness of a program, but they matter to humans :(
  • a docstring is the best way to document a function’s purpose
  • a syntax error is detectable before the program starts executing and they are caused by errors in the form/language of the code, ex: unclosed parentheses
  • a runtime error is detected by the interpreter while the program is executing, ex: TypeError which occurs when math doesn’t work out between objects of different types…
  • a logical error isn’t detected at all, the program runs but doesn’t do as expected
  • a decorator is a function that goes at the top of a function, which is called on the function
    def triple(x): # calls trace on triple
        return 3*x 


  • a recursive function is a function that calls itself
    • uses conditional statements to check for base cases — usually doesn’t end in a recursive call, and a value is directly returned
    • each call to the function will solve a simpler problem than the last call (smaller n)
  • mutual recursion is when two different functions call each other, ex: Luhn algorithm
  • iteration is a special case of recursion
    • to convert from recursion to iteration, you need to figure out what state has to be maintained after each recursive call (which should match to each iterative call…)

tree recursion

  • until a value is returned from a function call, that call is not completed
  • statements can happen before and after recursive calls
  • tree-shaped recursion happens when the body of a recursive function calls itself more than once
    • ex: computing a Fibonacci number n requires finding the Fibonacci number at n-1 and n-2 fib tree recursion
  • some problems are best resulted by a recursive function…
  • counting partitions example — looks like a competitive programming problem
    • Given a number n, using parts of up to size m, find the number of ways that n can be represented as a sum of positive integer parts with size m in increasing order; ex: count_partitions(6,4) means we should find all the possible ways that we can form 6 using parts of up to size 4. (2+4, 1+1+4, 1+2+3, 1+1+2+2…)
    def count_partitions(n,m):
        if n == 0:
            return 1
        elif n < 0:
            return 0
        elif m == 0:
            return 0
            with_m = count_partitions(n-m, m)
            without_m = count_partitions(n, m-1)
            return with_m + without_m


  • a list is a built-in data type that can hold a group of any objects
    • has indexing using brackets and len function for the length of the list
    • multiplying a list forms a repetition of the list, while adding two lists together merges them into one list
    • to test if an element appears in a container, use the in keyword
      • if the element is nested too deeply (more than one layer…?) then in can’t find it — it only looks at each element of the list
  • a for statement can iterate through a list or a range of numbers
    for <name> in <expression>:
    • a sequence can be unpacked in the for statement, ex: each value in the nested list pairs=[[4,4],[3,5],[1,2]] can be assigned to a variable using for x, y in pairs
  • a range is also a sequence type, like a list, but represent consecutive integers
    • convert a range to a list using the list function
  • list comprehensions are shortcuts to generate new lists from existing lists
    odds = [1,3,5,7,9]
    evens = [x+1 for x in odds] # list comprehension
    # [2,4,6,8,10]
    div_25 = [x for x in odds if 25 % x == 0] # only added to the list if the condition evaluates true
    # [1,5]
  • strings are a way of representing data
    • \n represents a new line
    • len and indexing can also be used
    • in evaluates to substrings which means you can look for whole words


  • a method for combining data values satisfies the closure property if the result of the combination can be itself combined using the same method
    • two lists can be combined using the + operator, whose result can be added to another list!
    • important for creating hierarchical structures
  • slicing is an operation that can be performed on lists and ranges — it uses the [lower:upper] notation, ex: "berkeley"[0:3] returns "ber"
    • always creates new objects
  • sum will add all non-string values in a list together with an optional parameter as the start value of the summation
  • max will return the maximum value of the sequence and takes an optional function key as a parameter that can be applied to all values to find the max of that function, ex: max([1,2,3,4,5], key=lambda x: 7-(x-4)*(x-2)) returns 3
  • all returns if all values in an iterable will return true

data abstraction

  • abstract data types allows us to manipulate compound objects as units, which separates how data is represented and manipulated
    • constructors build abstract data values
    • selectors work with parts of the abstract data values
  • a list can be unpacked, ex: x,y = [1,2] where x=1 and y=2
  • abstraction barriers allow parts of the program to take advantage of other parts of the program without anything causing errors between them — certain parts only use certain functions…


  • data types guarantee that the constructor and selectors will work together to show the right behavior
  • data abstraction can be implemented as functions
  • dictionaries are a built-in data type that assigns a value to a key — sequence of keys
    • created using curly brackets, ex: {key:value}
    • look up values by looking up the name of the key between square brackets (indexing with key names)
    • the value in a dictionary can be any object
    • keys cannot be repeated and the key itself can’t be a list or dictionary
  • dictionary comprehensions can generate dictionaries given a ruleset
    {<key exp>: <value exp> for <name> in <iter exp> if <filter exp>}
    {x * x: x for x in [1,2,3,4,5] if x > 2}
    # {9: 3, 16: 4, 25: 5}


  • trees represent hierarchical relationships
    • a tree has a root and a list of branches (which are subtrees)
    • a leaf is a tree without any branches

tree diagram

def tree(label, branches = [])
    for branch in branches:
        assert is_tree(branch), "branches must be trees!"
    return [label] + list(branches)
def label(tree):
    return tree[0]
def branches(tree):
    return tree[1:]
def is_tree(tree):
    if type(tree) != list or len(tree) < 1:
        return False
    for branch in branches(tree):
        if not is_tree(branch):
            return False
    return True
def is_leaf(tree)
		return not branches(tree)
  • functions that take trees as inputs or returns trees as outputs are tree-recursive
    • example with a function that counts the leaves of a tree
      def count_leaves(t):
          """Count the leaves of a tree."""
          if is_leaf(t):
              return 1
              branch_counts = [count_leaves(b) for b in branches(t)]
              return sum(branch_counts)
  • information can either be passed through recursive calls as arguments or they can be manipulated as return values


  • an object is supposed to behave like what it represents (information)
    • it has attributes, which are like details of the object
    • methods are accessed using a dot expression and are applied on the object
    • a type of object is called a class
  • functions are meant to do one thing; objects are meant to do many related things
  • strings are objects, with methods .upper .lower, attributes len
  • an object’s value can change over time
    • lists can be mutated (changed) using .remove .pop .append etc, which will be reflected in any copies of that list
    • mutable objects include lists and dictionaries
  • tuples are immutable sequences and are created using parentheses ()
    • tuples can be added and sliced like lists
    • they are immutable, so they can be used as keys (unless they contain lists or dicts)
  • an immutable sequence can still change if it has a mutable value as an element
  • the identity operator is is and will evaluate to true if both expressions evaluate to the same object — this is different from equality (==) which is true when both expressions evaluate to the same value
    • when two things aren’t identical, changes in one won’t affect the other


  • syntax is like the rules for how a language works
  • read plaintext files in Python using open and readlines
  • useful string methods: .strip .split .replace
  • language models describe how likely some text would appear in a sentence or next to some words (generating sentences by looking at huge samples of data)


  • iterators represent sequential data, which provides access to elements in some order
    • iter returns an iterator of some iterable value
    • next returns the next value in an iterator
  • after Python 3.6, the order of items in a dictionary is the order which they were added
  • useful dictionary methods: .keys returns a list of keys, .values returns a list of values, .items returns a list of tuples containing key and value
  • if a dictionary key is changed while it’s being iterated over, then the iterator is now invalid — doesn’t apply if a dictionary value is changed
  • for statements can iterate over iterators
  • built-in functions for iteration
    • map(func, iterable) applies func to x for x in iterable
    • filter(func, iterable) iterates through x in iterable if func is true
    • zip(iter_1, iter_2) iterates through pairs
    • reversed(seq) iterates in reverse order
    • list sorted tuple
  • lazy computation is useful if you need to calculate lots of values but don’t need all the values immediately
  • calling iter on an iterable just returns that iterable object


  • a generator is a special kind of iterator, returned from a generator function which uses the yield keyword instead of return
    • the generator object can yield (return) multiple values and the generator function iterates through them
    def plus_minus(x):
        yield x
        yield -x
    t = plus_minus(3) # t is a generator object
    next(t) #  3
    next(t) # -3
    • the body of the generator function isn’t called until next is called
  • yield from just yields all the values in an iterator — is shorthand for using for statements
  • example of finding all substrings of a string… looks like a competition problem
    def prefixes(s):
        if s:
            yield from prefixes(s[:-1])
            yield s
    def substrings(s):
        if s:
            yield from prefixes(s)
            yield from substrings(s[1:])
  • if there is a return statement in a generator, it won’t yield anything after
  • repeating the partitions problem but using yield
    def partitions(n, m):
        if n > 0 or m > 0:
            if n == m:
                yield str(m)
            for p in partitions(n-m, m):
                yield p + " + " + str(m)
            yield from partitions(n, m-1)


  • object-oriented programming (OOP) is a way of organizing programs so that similar information and behavior are grouped together, and can be changed without affecting other parts of the program (abstraction)
  • a class is a template for its instances, which are objects of that class
    • all objects part of a class will have the same attributes and behaviors
  • class statements let you create a new class, which means you can create your own objects
    class <name>:
    • assignments and def statements within the <suite> create attributes of the class
  • when a class is called, a new instance of the class is created (a new object)
    • the __init__ method is first called with an argument self and any other specified arguments
    class Account:
        def __init__(self, account_holder):
            self.balance = 0
            self.holder = account_holder
  • binding an object to a new name using assignment does not create a new object…
  • methods are functions that are defined in a class
    class Account: 
        def deposit(self, amount):
            self.balance = self.balance + amount
        def withdraw(self, amount):
            if amount > self.balance:
                return "Insufficient funds."
            self.balance = self.balance - amount
            return self.balance
  • self is referring to an (arbitrary?) instance of the class, similar to this in Java
  • any object has access to its attributes (via the self keyword) — they can be accessed using dot notation <expression>.<name>
    • can also get attributes using function getattr(obj, attr)
  • a method is an attribute that’s a function
    • bound methods group together the function and the object which the method is called on

instance and class methods

  • class attributes are shared across the class — if it changes, then it changes for every instance of the class
    class Account:
        interest = 0.02 # class attribute


  • all objects, including classes, have attributes
    • an attribute of an instance is called an instance attribute, ex: <instance>.attribute =
    • attribute of a class of an instance is called a class attribute, ex: Class.attribute =
      • changing class attributes doesn’t change individual attributes
  • inheritance is a method for relating classes together
    class <name>(<base class>):
    • the subclass can share attributes with its base class
    • methods from base classes can be called by calling the base class’s attribute
  • composition is when one object has another object as an attribute
  • inheritance: is-a relationship, ex: CheckingAccount is a Account; composition: has-a relationship, ex: Bank has a Account
  • multiple inheritance is when a subclass has multiple base classes — should be used sparingly


  • the str string representation is designed for human readability, while the repr string representation is designed for the Python interpreter
    • calling repr on a value will show what would print out in an interactive session, ex: repr(min) shows '<built-in function min>'
  • string interpolation is when you evaluate a string literal with some expressions
    • add f before the string and enclose any expressions in curly braces, ex: f'pi starts with {pi'
  • a polymorphic function is a function that applies to many types of data (such as str and repr)
  • an interface is a set of shared messages (attributes look-ups that elicit similar behaviors even on different classes/types)
  • certain method names are special because they have a built-in behavior — denoted by two underscores, like __init__, __repr__
    • adding two instances of user-defined classes: __add__ or __radd__ but you have to define it

recursive objects

  • a linked list is either empty or it just holds a single value with a reference to the rest of the list — it’s just like a number line thing

linked list diagram

  • the rest attribute of a linked list can be assigned to an earlier element in that list, which creates a loop in the list
  • rerouting in a linked list is reassigning the rest attribute which would change the list (either when you’re adding or removing instances)
  • a path (for a tree data structure) is a sequence of nodes that leads to a certain node
  • pruning is removing subtrees from a tree


  • it’s important for programs to not take up too many resources while running

  • memoization is the idea that you should remember the results that have been computed previously (so they can be used later)

    def memo(f):
        cache = {}
        def memoized(n):
            if n not in cache:
                cache[n] = f(n)
            return cache[n]
        return memoized
    • only pure functions can be memoized
  • complexity can sometimes mean better efficiency

  • there is linear and logarithmic orders of growth, or how long the function takes to run as the numbers get larger — also quadratic for pairs of inputs, or exponential for recursion, and constant growth means the input doesn’t affect the time

    • there is a notation for each order of growth, called big-theta (or big-O for upper bound) notation
    • exponential: ; quadratic: ; linear: ; logarithmic: ; constant:
  • the length of objects/programs take up space (memory), but so do active frames and environments

    • an active environment includes current active function calls, including their parents (this might be why recursion is slow?)


  • modular design is when a big program is broken up into smaller, independent parts — parts can be swapped out and implement abstraction barriers
    • a component is meant to do one thing and can be developed and tested independently
    • one part should know as little as possible about the other parts, so changes in one component won’t break everything else
  • read json files in Python by importing the json module and then opening the file using open and reading the lines
  • given two, non-repeating sorted lists, advance the iterator over the smaller value until a pair is found, then iterate both, until the end of the list is reached (linear time)

users - todo


  • scheme is a dialect of lisp

  • programs consists of expressions

    • primitive: 2, 3.3, true, +
    • combinations: (quotient 10 2) (not true)
  • procedures = functions

  • the built-in ? operator can evaluate if something is of a certain type — (zero? 0) is #t, (zero? 1) is #f

  • special forms

    • (if <predicate> <consequent> <alternative>)
    • (and <e1> ... <en>), (or <e1> ... <en>)
    • symbols: (define <symbol> <expression>)
    • procedures: (define (<symbol> <formal parameters>) body)
      (define (sqrt x)
          (define (update guess)
              (if (= (square guess) x)
                  (update (average guess (/ x guess)))))
          (update 1)
    • (lambda (<formal-parameters>) <body)
  • cond is like an if/else or a switch statement

    (cond ((> x 10) (print 'big)) ; only one is executed
          ((> x 5)  (print 'medium))
          (else     (print 'small)))
  • begin allows you to add multiple subexpressions to be evaluated if a condition evaluates to true…

  • let binds a temporary symbol to a value, which is gone after it is used — define is used for permanent things

  • every scheme list is a linked list

    • cons creates a linked list
    • car returns the first element of the list
    • cdr returns the rest of the list — usually returns a list too?
    • nil is the empty list
  • list just builds a list without needing to use cons but the underlying car cdr is still the same

  • symbols refer to values, but how do we refer to symbols? by using ' quotation, ex: (list 'a 'b) makes (a b)

    (define a 1)
    (define b 2)
    (list a b)
    ; (1 2)
    (list 'a 'b)
    ; (a b)
    (list 'a b)
    ; (a 2)
    • a symbol can be used as a part of the code without calling the actual function


  • an example of how symbols can be used
    (list 'quotient 10 2)
    ; (quotient 10 2)
    (eval (list 'quotient 10 2))
    ; 5
  • build lists to write constructed code and just call eval when you need to run the code
    • using symbols tells scheme that we don’t want to evaluate the expression yet
  • quasiquotation is when you can use a special backtick quote symbol ``` and parts of the quote can be unquoted with ,
    • quote: '(a ,(+ 3 1)) > (a (unquote (+ 3 1))
    • quasiquote: “(a ,(+ 3 1))>(a 4)`
  • while statements don’t exist in scheme so you have to iterate and you recursion
  • quoting, unquoting, and the structure of lisp/scheme allow for the computer to easily generate programs
  • Python raises exceptions when errors occur, which can also be handled — unhandled exceptions will halt Python and print stack traces
    • assert statements — ignore assertions using the -O flag
    • raise statements are exceptions with custom debug messages
  • try/except suites can handle exceptions when they are expected
    • the try suite is executed first, and if an unhandled exception is raised and inherited from the exception class in the exception suite, then the exception suite is executed
        <try suite>
    except <exception class> as <name>:
        <except suite>


  • an interpreter is a program that takes code as an input and executes the code to get the desired output
  • machine languages are languages that are interpreted by the hardware — instructions based on the circuitry of the CPU
    • hard to program, no abstraction, usually refer to specific memory addresses
  • high-level languages are statements and expressions that are translated into another language to be executed later
    • provides abstraction, functions, objects
    • no hardware designed for these languages
  • some languages are designed for a specific application — Erlang was designed for concurrent communication, MediaWiki was designed for static web pages
  • languages have syntax (statements/expressions) and semantics (execution/evaluation)
    • need to have specification or a canonical implementation
  • a parser takes text and returns expressions

parse order

  • recursive syntactic analysis is a process of inspecting k tokens to decide how to proceed, for a fixed k
    • the base case is symbols and numbers, any other calls are sub-expressions
  • the Pair class represents Scheme pairs and lists — has first and second attributes
    • will be a well-formed list if second is nil or a well-formed list
  • primitive (numbers) expressions evaluate to themselves while call expressions evaluate to its arguments modified by an operator
  • read-eval-print loop allows a person to interact with the code, ie Python interactive interpreter
    • exceptions are handled in one place and should not stop the interactive interpreter


  • an eval evaluates both primitive and combined expressions, but will call a function apply on the combined expressions
    • apply will also call eval to evaluate the body of custom functions which makes mutually recursive functions


disc 01: control, environment diagrams

  • conditional statements let programs execute different lines of code depending on what conditions are true or false
    • general form of an if statement
      if <conditional expression>:
          <suite of statements>
      elif <conditional expression>:
          <suite of statements>
          <suite of statements>
    • general form of a while loop
      while <conditional clause>:
          <statements body>
  • not and or are boolean operators that manipulate boolean expressions
  • a def statement defines a function object
    • call expressions apply functions to arguments

lab 01: variables & functions, cont

  • >>> True and 12 displays 12
  • >>> False or 0 displays 0 (I assume because the statement evaluates to False and 0 is the last evaluated expression?)
  • >>> not 10 displays False because 10 is a truthy value
  • >>> not None displays True because None is a falsey value
  • >>> True and 0 displays 0 (because last evaluated expression is 0?)
  • >>> 0 or False or 2 or 1/0 displays 2 because 2 is the expression that makes the statement be true
  • I think that what gets printed by the interpreter is the last evaluated value that makes the expression be true or false!
  • use python3 ok -q ["question"] -i to open an interactive terminal for the question
  • use python3 ok -q ["question"] --trace to look at an environment diagram for the question

lab 02: higher-order functions, lambda expressions

  • transforming a function f(x,y) into g(x)(y) is known as currying

    def lambda_curry2(func):
        return lambda x: lambda y: func(x,y)
  • sometimes, trying to refer to a variable in the parent frame won’t work — use the nonlocal keyword to reframe the variable

    • idk why it doesn’t work
  • Church numerals…

disc 02: higher-order functions, self reference

  • a lambda expression doesn’t return anything until the lambda is called
  • the parent of any function is the frame where the function is defined — variables can be included in the parent frame, which can also be accessed in the function’s frame (sometimes use nonlocal)
  • self-reference is when a function returns itself, but doesn’t call itself

disc 03: recursion

  • three parts to a recursive function
    • base case: the stopping condition, the simplest case, ex:
    • recurse onto smaller problems: to recursively call on a simpler problem than the current one and breaking it into parts
    • solve the big problem in parts: since we can solve many small parts, use that to solve the bigger parts


  • *args is a parameter will take a bunch of arguments and pass them all as a group

lab 04: recursion, tree recursion, python lists

  • if/else can be done in a list comprehension — just an ordering issue

    [ [true action] if [condition] else [false action] for x in [sequence] ]
  • ternary statements in python

    value_if_true if condition else value_if_false

disc 04: tree recursion, python lists

  • tree recursion is used for problems where there can be multiple possibilities to deal with, such as Fibonacci numbers needing to calculate n-1 and n-2
  • recursive calls are made for a group of choices

disc 05: trees, data abstraction, sequences

  • constructors build abstract data type — also called constructors in Java?
  • selectors retrieve information from a data type — probably getters
  • tree language:
    • parent node: a node that has at least one branch (child)
    • child node: node with a parent
    • root: the top node
    • label: the value at a node
    • leaf: a node with no children (branches)
    • depth: how far the node is from the root
    • height: the depth of the lowest leaf

disc 08: linked lists, trees

  • unpack a list of elements into a zip function by adding * before the list
    • zip(*[[1,2],[3,4],[5,6]])

lab 10: scheme

  • (or 1 #t) evaluates to 1

hw 07:

  • (let ((bindings)) (body))
    • SchemeError: badly formed expression:
      • probably missed the extra parentheses around the bindings

unfinished/review q’s

  • hw01: review quine
  • hog: finish problem 12
  • hw02: finish church numerals
  • hw03: finish towers of hanoi; review anonymous factorial
  • disc04: finish max product
  • disc06: finish mystery reverse environment diagram
  • hw06 VirFib is_bst
  • disc08: Multiply Links Find Paths
  • ants: EC, optional 1 & 2