Skip to content
- Reading Ch. 2.1: Introduction (15, 18/06/22)
- Every Python value has a class that determines its type of value
- Same class, same behavior
- Native data types: integers (int), real numbers (float), complex numbers
(complex)
- Literals: expressions that evaluate to values of native types
- There are built-in functions and operators to manipulate values of native
types
- Floats are represented in Python as a “floating point”
- int objects represent integers exactly
- float objects represent a wide range of fractional numbers, but not all
can be represented exactly, and there are minimum and maximum values →
float values should be treated as approximations
- Programmers must define most values’ types other than native ones through
means of combination and abstraction
- Reading Ch. 2.3: Sequences (15-16, 21, 23/06/22)
- Sequence: an ordered collection of values
- A fundamental abstraction in computer science
- A collection of behaviors that are shared among several different types of
data
- Length
- Element selection
- Membership
- Slicing
- <sequence>[<starting index>: <ending index >: <step size>]
- Addition and multiplication do not add or multiply elements, but instead,
combine and replicate the sequences
- List: native data type, sequence, arbitrary length
- Iteration through a sequence
- for <name> in <expression>:
- <suite>
- Evaluate <expression>, must yield an iterable value
- Bind <name> to corresponding value
- Execute <suite>
- As such, <name> will be bound to the last element after the for
statement has been executed
- Sequences are iterable values
- Sequence unpacking: the pattern of binding multiple names to multiple
values in a fixed-length sequence
- Range: a built-in sequence that represents a range of integer
- range(1, 10) # Includes 1, not 10
- Calling the list constructor on a range evaluates to a list
- for _ in range(3): # _ does not appear in the suite, runs from 0 → 2
- Sequence processing operations:
- List comprehensions: evaluate a fixed expression for each element in a
sequence and store the values in a result sequence or select a subset of
values that satisfy some condition
- [<map expression> for <name> in <sequence expression> if <filter
expression>]
- Aggregation: aggregate all values in a sequence into a single value
(sum, min, max, all)
- Higher order functions: apply_to_all (Common name: map), keep_if
(Common name: filter), reduce
- The richness of an abstraction (how many behaviors) has consequences.
- Additional behaviors can be helpful, but satisfying the requirements of a
rich abstraction with a new data type becomes harder. They also take users
longer to learn
- Most user-defined abstractions should be kept as simple as possible
- Strings: sequences of characters
- Unlike other programming languages, Python characters do not have a
separate type, they are strings of length 1
- String coercion: a string can be created from any Python object by calling
the str constructor on an object value → constructing descriptive strings
from objects of various types
- Closure property of a data type: The result of the combination of data
values can be combined using the same method → create hierarchical
structures
- Trees: A tree has a root label and a list of branches
- Each branch is a tree
- A tree with zero branches is called a leaf
- Each location in a tree is called a node, each has a label
- One node can be the parent/child of another
- A tree constructor, label and branches selectors, is_tree and is_leaf
validators
- Binary trees have two branches
- Linked Lists: a sequence constructed from nested pairs
- A pair contains the first element of the sequence and the rest. The second
element is also a linked list
- A linked list can be ‘empty’
- A linked list constructor, first and rest selectors, and is_link validator
- Lab 04: Recursion, Tree Recursion (16/06/22)
- Project 2: CS 61A Autocorrected Typing Software (17/06/22)
- Lecture 11: Containers (18/06/22)
- Reading Ch. 2.2: Data Abstraction (21/06/22)
- Data abstraction: A methodology by which functions enforce an
abstraction barrier between representation and use. These two parts are
connected by a set of functions that implement abstract data in terms of the
concrete representation
- Example: Implement rational numbers (abstract data) using the built-in
list type (concrete representation)
- Wishful thinking: assume that we already have some functions with known
input and output, we can use those function names in the implementation of
other functions before even actually implementing them
- Abstraction barriers: functions are called by a higher level and
implemented using a lower level of abstraction. A violation occurs when part
of the program that can use a higher-level function instead uses a function
in a lower level.
- Make programs easier to maintain and modify
- In general, abstract data can be expressed using a collection of selectors,
constructors, and some behavior conditions.
- Lecture 12: Data Abstraction (21/06/22)
- Data abstraction uses selectors and constructors to define behavior
- If behavior conditions are met, then the representation is valid
- Dictionaries: unordered collections of key-value pairs
- {<key>: <value>,…}
- <dictionary name>[<key>] → <value>
- <dictionary name>.keys()
- <dictionary name>.values()
- <dictionary name>.items()
- dict() → Constructor constructs a dictionary
- <dictionary name>.get(<key>, <default value>) → Returns <default
value> if there is no value associated with <key>
- {<key map expression>:<value map expression> for <name> in
<sequence expression> if <filter expression>} → Dictionary
comprehension
- Cannot use list and dictionary as keys or any mutable type
- Two keys cannot be equal, there can be at most one value for a key
- Lecture 13: Trees (23/06/22)
- Tree processing uses recursion
- Processing a leaf is often the base case of a tree processing function
- Examples: Function that counts leaves, functions that act based on the
leaves’ labels,…
- The recursive case typically makes a recursive call on each branch,
then aggregates
- A function that creates a tree from another tree is typically recursive
- Discussion 04: Python Lists, Tree Recursion (15/07/22)
- Guerrilla 01: Python Lists, Recursion, Tree Recursion (15/07/22)