Python Programming | Computer Science Study Notes

1 Basic Python Knowledge

1.1 Strings

1.1.1 String Representation

In Python, all objects produce two string representations:

The str is legible to humans.
The repr is legible to Python interpreter.

repr: Provides a string representation that can be used to recreate the object. It's designed for debugging and introspection. It aims for a more precise and detailed description, often including the object's type.
Examples:
class MyClass: def __init__(self, value): self.value = value def __repr__(self): return f"MyClass({self.value})" obj = MyClass(10) print(repr(obj)) # Output: MyClass(10)
repr: Provides a human- readable string representation of the object. It's designed to be easily understood by humans.
Examples:
class MyClass: def __init__(self, value): self.value = value def __str__(self): return f"MyClass with value: {self.value}" obj = MyClass(10) print(str(obj)) # Output: MyClass with value: 10

1.1.2 Strings in Python

For more information on strings, please visit strings in Java.

Examples in Python:

name = "Nate" age = 19 s = "My name is %s and I am %d years old" % (name, age) s1 = "My name is {} and I am {} years old".format(name, age) s2 = f"My name is {name} and I am {age} years old" print(f"2 + 2 = {(lambda x: x + x)(2)}") # 2 + 2 = 4

s = "I have a dream!" print(s[2:6]) # "have" print(s[2:]) # "have a dream!" print(s[-3:-1]) # "am" print(s[-1:-3]) # "" No result! print(s[::-1]) # "!maerd a evah I", -1 refers to the step

s = "dream" s1 = s.captialize() # "Dream" s2 = "i have a dream!" s3 = s2.title() # "I Have A Dream!" s4 = "I HAVE A DREAM!" s5 = s4.lower() # "i have a dream!"

s = " I have a dream! " s1 = s.strip() # "I have a dream!" strip() can remove whitespace, \n, \t s2 = "I have a dream!" s3 = s2.replace("dream", "car") # "I have a car!" s4 = s2.split(" ") # ["I", "have", "a", "dream!"] s5 = "I have a dream!" ret = s5.find("dream") # 9 ret = s5.find("car") # -1 ret = s5.index("dream") # 9 ret = s5.index("car") # ValueError print("I" in s5) # True print(s5.startswith("I")) # True s6 = "123" ret = s6.isdigit() # True

1.2 Lists

Examples:

lst = ["I", "have", "a", "dream!"] s = " ".join(lst) # "I have a dream!" for item in lst: print(item) # I have a dream!

lst = [] lst.append("I") # ["I"] lst.insert(0, "have") # ["have", "I"] lst.extend(["a", "dream!"]) # ["have", "I", "a", "dream!"] lst.pop() # "dream!" lst.pop(0) # "have" lst.remove("I") # ["a"] lst.[0] = "me" # ["me"]

lst = [1, 2, 4, 3, 5] lst.sort() # [1, 2, 3, 4, 5] lst.sort(reverse=True) # [5, 4, 3, 2, 1] lst = ["I", "have", "a", "dream!"] lst[1] = lst[1].upper() # string operations must return a new string print(lst) # ["I", "HAVE", "a", "dream!"]

1.3 Tuple

Examples:

t = () t = (1, 2, 3) t[1] = 4 # TypeError -> Tuple is unchangeable! t = ("I have a dream!") print(type(t)) # <class 'str'> t = ("I have a dream!",) print(type(t)) # <class 'tuple'> t = ("I", "have", ["a", "dream"]) t[2].append("!") print(t) # ("I", "have", ["a", "dream", "!"]) # "Tuple is unchangeable" means the cache address of the tuple is unchangeable.

1.4 Set

s = {} print(type(s)) # <class 'dict'> s = {1, 2, 3} s = set()

Set cannot contain unhashable type aka mutable type.

Hashable type: int, float, string, tuple, bool.
Unhashable type: list, set, dict.

s = {1, 2, 3, []} # TypeError: unhashable type: 'list'

s = set() s.add(1) s.add(2) s.add(3) s.pop() s.remove(2)

s1 = {1, 2, 3} s2 = {3, 4, 5} print(s1 & s2) # {3} print(s1.intersection(s2)) # {3} print(s1 | s2) # {1, 2, 3, 4, 5} print(s1.union(s2)) # {1, 2, 3, 4, 5} print(s1 - s2) # {1, 2} print(s1.difference(s2)) # {1, 2}

1.5 Dictionary

dic = {1: "I", 2: "have", 3: "a", 4: "dream!"}

dic = {} # dic = dict() dic[1] = "I" dic[2] = "have" # {1: "I", 2: "have"} dic.setdefault(3, "a") # {1: "I", 2: "have", 3: "a"} ''' If the key exists, skip; otherwise, add and set the key-value pair to default in dictionary. '''

dict = {1: "I", 2: "have", 3: "a", 4: "dream!"} dict.pop(4) # {1: "I", 2: "have", 3: "a"} print(dict[0]) # KeyError print(dict.get(0)) # None

dict = {1: "I", 2: "have", 3: "a", 4: "dream!"} for key in dict: print(key, dict[key]) print(list(dict.keys())) # [1, 2, 3, 4] print(list(dict.values())) # ["I", "have", "a", "dream!"] for item in dict.items(): print(item) for key, value in dict.items(): print(key, value)

dict = {1: "I", 2: "have", 3: "a", 4: "dream!"} for key in dict: dict.pop(key) # RuntimeError: dictionary changed size during iteration

dict = {1: "I", 2: "have", 3: "a", 4: "dream!"} for key in list(dict.keys()): dict.pop(key) # No error

1.6 Bytes

ASCII: 1 bytes, 8 bits.
ANSI: A standard. 2 bytes, 16 bits.
- Mainland China: GB2312 => GBK (Windows).
- Taiwan, China: Big5.
- Japan: JIS.
Unicode:
- UCS-2: 2 bytes, 16 bits.
- UCS-4: 4 bytes, 32 bits .
UTF: All the same as Unicode, except that the length is changeable.
- English: 1 byte, 8 bits .
- Some of European languages: 2 bytes, 16 bits.
- Chinese: 3 bytes, 24 bits.
UTF-16: Shortest length is 16 bits.

1.7 Logical Operators

Priority:

() => not => and => or

2 Higher-Order Function

Higher-order function: A function that takes a function as an argument value or returns a function as a return value.

2.1 Higher-Order Function (Functions as Arguments)

Examples:

def summation(n, term): total, k = 0, 1 while k <= n: total, k = total + term(k), k + 1 return total def cube(k): return k * k * k def sum_cubes(n): return summation(n, cube)

def apply_twice(f, x): return f(f(x)) def square(x): return x * x result = apply_twice(square, 2)

Apply a User-Defined Function

Create a new frame.
Bind formal parameters (f & x) to arguments.
Execute the body: return f(f(x)).

Environments for Higher
-Order Functions

2.2 Nested Definitions (Functions as Returned Values)

def make_adder(n): def adder(x): return x + n return adder

Propositions:

Every user-defined function has a parent frame (often global).
The parent of a function is the frame in which it was defined.
Every local frame has a parent frame (often global).
The parent of a frame is the parent of function called.

2.3 Lambda Expressions

Important notes:

No "return" keyword!
Lambda expressions are not common in Python, but important in general.
Lambda expressions in Python cannot contain statements at all!

square = lambda x: x * x

auto lambda = [](int x, int y) { int sum = x + y; int product = x * y; return sum + product; }; int result = lambda(5, 7); // result will be 47

public static void main(String[] args) { IntBinaryOperator addAndMultiply = (x, y) -> { int sum = x + y; int product = x * y; return sum + product; }; int result = addAndMultiply.applyAsInt(5, 7); // result will be 47 System.out.println(result); }

let myFunction = (x, y) => { let sum = x + y; let product = x * y; return sum + product; }; let result = myFunction(5, 7); // result will be 47

2.4 Currying

Examples:

def curry2(f): def g(x): def h(y): return f(x, y) return h return g def add(x, y): return x + y s = curry2(add)(1)(2)

3 Recursion

Recursive Function: A function is called recursive if the body of that function calls itself, either directly or indirectly.

3.1 Self-Reference: Return by its own name

def print_all(x): print(x) return print_all print_all(1)(3)(5)

def print_sums(x): print(x) def next_sum(y): return print_sums(x + y) return next_sum print_sums(1)(3)(5)

3.2 Recursion & Environment Diagrams

Example 1:

def split(n): return n // 10, n % 10 def sum_digits(n): # Base Cases if n < 10: return n else: all_but_last, last = split(n) return sum_digits(all_but_last) + last

Example 2:

def fact(n): if n == 0: return 1 else: return n * fact(n - 1)

3.3 Iteration & Recursion

	Iteration	Recursion
Sample Implementation	Using while: def fact_iter(n): total, k = 1, 1 while k <= n: total, k = total * k, k + 1 return total	Using recursion: def fact(n): if n == 0: return 1 else: return n * fact(n - 1)
Math
Conversion (to another)	More formulaic: The state of an iteration can be passed as arguments.	Can be tricky: Find out what state must be maintained by the iterative function.

Iteration

Recursion

Sample Implementation

Using while:

def fact_iter(n): total, k = 1, 1 while k <= n: total, k = total * k, k + 1 return total

Using recursion:

def fact(n): if n == 0: return 1 else: return n * fact(n - 1)

Math

Conversion

(to another)

More formulaic:

The state of an iteration can be passed as arguments.

Can be tricky:

Find out what state must be maintained by the iterative function.

3.4 Mutual Recursion

Luhn Algorithm - Used to verify credit card numbers.

From the rightmost digit, which is the check digit, moving left, double the value of every second digit; if product of this doubling operation is greater than 9 (e.g., ), then sum the digits of the products (e.g., 10: , 14: ).
Take the sum of all the digits. The Luhn sum of a valid credit card number is a multiple of 10.

                def luhn_sum(n):
                    if n < 10:
                        return n
                    else:
                        all_but_last, last = split(n)
                    return luhn_sum_double(all_but_last) + last

                def luhn_sum_double(n):
                    all_but_last, last = split(n)
                    luhn_digit = sum_digits(2 * last)
                    if n < 10:
                        return luhn_digit
                    else:
                        return luhn_sum(all_but_last) + luhn_digit
            

4 Iterators & Generators

4.1 Iterators

Definitions:

Iterable: An object capable of returning its members one at a time.
Iterator: An object that progressively provides access to each item of a collection, in order.

Types of iterables:

Operations on iterators:

iter (iterable): Return an iterator over the elements of an iterable value.
next (iterable): Return the next element in an iterator.

Example usage:

                s = [5, 2, 0]
                iterator = iter(s)
                item1 = next(iterator) # 5
                item2 = next(iterator) # 2
                item3 = next(iterator) # 0
                item4 = next(iterator) # StopIteration
            

4.2 Iterables

Lists: [1, 2, 3, 4]
Tuples: (10, 20, 30)
Strings: "Hello"
Dictionaries: {"name": "Alice", "age": 30} (iterates over keys by default)
Sets: {1, 2, 3}
Ranges: range(1, 5)
File Objects: Used for reading data from files line by line.

Special case: Dictionaries

The order of items of a dictionary is the order in which they were added (Python 3.6+).
Historically, items appeared in an arbitrary order (Python 3.5 and earlier).

Example usage:

# Iterate keys d = {"MacOS": "Apple", "Windows": "Microsoft", "Linux": "Open Source"} k = iter(d.keys()) # or iter(d) print(next(k)) # MacOS # Iterate values v = iter(d.values()) print(next(v)) # Apple # Iterate items i = iter(d.items()) print(next(i)) # ('MacOS', 'Apple')

                    d = {"MacOS": "Apple", "Windows": "Microsoft", "Linux": "Open Source"}
                    k = iter(d.values())
                    print(next(k)) # Apple
                    d["Android"] = "Google"
                    print(next(k)) # RuntimeError: dictionary changed size during iteration
                

d = {"MacOS": "Apple", "Windows": "Microsoft", "Linux": "Open Source"} k = iter(d.values()) print(next(k)) # Apple d["Windows"] = "Microsoft Corporation" print(next(k)) # Microsoft Corporation

4.3 Generators

Definitions:

Generator: A function that yields value instead of returning them.
Generator: An iterator created automatically by calling a generator function.

Example usage:

def even(start, end): current = start + (start % 2) while current <= end: yield current current += 2 lst1 = list(even(1, 10)) # [2, 4, 6, 8, 10] t = even(1, 10) item1 = next(t) # 2 item2 = next(t) # 4

Generators can yield form iterators:

A yield from statement yields all values from an iterator or iterable (Python 3.3).

Example 1:

                    def a_then_b(a, b):
                        for x in a:
                            yield x
                        for x in b:
                            yield x
                

                    def a_then_b(a, b):
                        yield from a
                        yield from b
                

Example 2:

                    def countdown(k):
                        if k > 0:
                            yield k
                        yield countdown(k - 1)

                    t = countdown(3)
                    item1 = next(t) # 3
                    item2 = next(t) # <generator object countdown at 0x0000021D7D3D3F90>
                

                    def countdown(k):
                        if k > 0:
                            yield k
                        yield from countdown(k - 1)

                    t = countdown(3)
                    item1 = next(t) # 3
                    item2 = next(t) # 2
                

4.4 Built-In Iterator Functions

Many built-in Python sequence operations return iterators that compute results lazily.

To view the contents of an iterator, place the resulting elements into a container.

list (iterable): Create a list containing all x in iterable.
tuple (iterable): Create a tuple containing all x in iterable.
sorted (iterable): Create a sorted list containing x in iterable.

4.4.1 Map

map (func, iterable): Iterate over func(x) for x in iterable.

Example usage:

                    def square(x):
                        return x * x

                    numbers = [1, 2, 3, 4]
                    squared_numbers = map(square, numbers) # map object (iterator)
                    item1 = next(squared_numbers) # 1
                

4.4.2 Filter

filter (func, iterable): Iterate over x in iterable if func(x).

Example usage:

                    def square(x):
                        return x * x

                    def is_even(x):
                        return x % 2 == 0

                    numbers = [1, 2, 3, 4]
                    even_numbers = filter(is_even, numbers) # filter object (iterator)
                

4.4.3 zip

zip (first_iter, second_iter, ...): Iterate over co-indexed (x, y) pairs.

Example usage:

Example 1:

list(zip([1, 2], [3, 4, 5], [6, 7])) # [(1, 3, 6), (2, 4, 7)]

Example 2:

                    def palindrome(s):
                        return all(a == b for a, b in zip(s, reversed(s)))
                

4.4.4 reversed

reversed (sequence): Iterate over x in a sequence in reverse order.

Example usage:

                    t = [1, 2, 3, 2, 1]
                    print(reverse(t) == t) # False
                    # Because reversed(t) is a list_reverseiterator object
                    print(list(reversed(t) == t) # True
                

4.4.5 range iterator

Example usage:

                    r = range(3, 6)
                    ri = iter(r) # range_iterator object
                    for i in ri:
                        print(i)
                    # 3
                    # 4
                    # 5
                

5 Efficiency

5.1 Order of Growth

For more information on order of growth, please refer to Data Structures and Algorithms 1.

5.2 Space

At any moment there is a set of active environments. Values and frames in active environments consume memory.
Memory that is used for other values and frames can be recycled.
Active Environments:
- Environments for any function calls currently being evaluated => call the function but hasn't returned yet.
- Parent environments of functions named in active environments => define a function in another function, so the function defined is not in the global frame, the parent frame is needed.

6 Object-Oriented Programming

6.1 Object-Oriented Programming in Python

For more information about the details of Object-Oriented Programming, refer to Object-Oriented Programming in C++.

                class Account:
                # _init_ is a special method name for the function that constructs
                # an Account instance
                    def __init__(self, account_holder):
                        self.balance = 0
                        self.holder = account_holder

                # self is the instance of the Account class on which deposit was
                # invoked
                    def deposit(self, amount):
                        self.balance = self.balance + amount
                        return self.balance

                    def withdraw(self, amount):
                        if amount > self.balance:
                            return "Insufficient funds"
                        self.balance = self.balance - amount
                        return self.balance


                a = Account("Nate")
                a.deposit(100)
                a.withdraw(50)
                print(a.balance) # 50
            

When a class is called:
- A new instance of that class (aka an object) is created.
- The _init_ method of the class is called with the new object as its first argument (named self), along with any additional arguments provided in the call expression.
- An object's attributes can be accessed and modified using dot expressions.
- Every object that is an instance of a class has a unique identity.
All invoked methods have access to the object via the self parameter, and so they can all access and manipulate the object's attributes.

6.2 Inheritance

For more information about inheritance, please visit Object-Oriented Programming in C++.

6.3 Special Method Functions

Certain names are special because they have built-in behavior.

These names always start and end with two underscores.

__init__ Method invoked automatically when an object is constructed
__repr__ Method invoked to display an object as a Python expression
__add__ Method invoked to add one object to another
__bool__ Method invoked to convert an object to True or False.
__float__ Method invoked to convert an object to a float (real number).

7 Scheme

7.1 Scheme Fundamentals

Scheme programs consist of expressions, which can be:

Primitive expressions: 2, 3.3, true, +, quotient...
Combinations: (quotient 10 2), (not true)...

Numbers are self-evaluating; symbols are bound to values.

Call expressions include an operator and 0 or more operands in parenthesis.

Example:

                (quotient 10 2) ; 5
                (- (* 3 5) (+ 10 1)) ; 14
                (- (* 2 2 3)
                (+ 3 2 1)) ; 9
                (number? 3) ; #t
            

Special forms:

Special forms: A combination taht is not a call expression is a special form:

If statement : (if <predicate> <consequent> <alternative >)
And and or: (and <e ₁ > ... <e _n >), (or <e ₁ > ... <e _n >)
Binding symbols: (define < symbol> <expression>)
New procedures: (define < symbol> <formal parameters>) <body>
Lambda Expressions: (lambda (<formal-parameters>) <body>

Examples:

                (define pi 3.14)
                (define (abs x)
                (if (>= x 0)
                x
                (- x)))
            

(define (plus4 x) (+ x 4))

(define plus4 (lambda (x) (+ x 4)))

Cond & Begin:

Cond

                    if x > 10:
                        print("big")
                    elif x > 5:
                        print("medium")
                    else:
                        print("small")
                

                    (cond ((> x 10) (print 'big))
                    ((> x 5) (print 'medium))
                    (else (print 'small)))
                

Begin

                    if x > 10:
                        print("big")
                        print("guy")
                    else:
                        print("small")
                        print("fry")
                

                    (if (> x 10)
                    (begin
                    (print 'big)
                    (print 'guy))
                    (begin
                    (print 'small)
                    (print 'fry)))
                

Let:

                    a = 3
                    b = 2 + 2
                    c = math.sqrt(a * a + b * b)
                

                    (let ((a 3)
                    (b (+ 2 2)))
                    (sqrt (+ (* a a) (* b b))))
                

7.2 Scheme Lists

cons: Two-argument procedure that creates a linked list.
car: Procedure that returns the first element of the list.
cdr: Procedure that returns the rest of a list.
nil: The empty list.

(cons 1 (cons 2 (cons 3 nil))) ; (1 2 3)

Symbolic programming:

                (define a 1)
                (define b 2)
                (list a b) ; (1 2)
                (list 'a 'b) ; (a b)
            

Built-In List Processing Procedures

(append s t): list the elements of s and t; append can be called on more than 2 lists.
(map f s): call a procedure f on each element of a list s and list the results.
(filter f s): call a procedure f on each element of a list s and list the elements for which a true value is the result.
(apply f s): call a procedure f with the elements of a list as its arguments.