UCB CS61A--Part I

大四临近毕业，为了将来留美找工作，我准备跟一些比较著名的CS神课，来打下CS基础。目前在跟的是UCBerkely CS61A，这门课是为CS初学者准备的，不过没一点基础可能接受起来比较吃力，使用语言为Python。现在开始写一些课堂笔记之类的，巩固知识用，主要是一些Python的奇技淫巧。

Lecture 1
What is this course about?
A course about managing complexity:
§ Mastering abstraction: Giving a complex system a name and thinking it as a whole without worrying about details.
§ Programming paradigms

operator (operand, operand)
>>> add (2, 3)

# 长度为四，正反相同的单词
>>> {w for w in words if w == w [::-1] and len(w) ==4}

Lecture 2

# swap(a, b) can be written as:
>>> a, b = 1, 2
>>> a, b = b, a
(a, b) = (2, 1)

Every expression is evaluated in the context of an environment.
So far, the current environment is either:
• The global frame alone, or
• A local frame, followed by the global frame.
An environment is a sequence of frames.
A name evaluates to the value bound to that name in the earliest frame of the current environment in which that name is found.

>>> def square(square):
>>>     return mul(square, square)
>>> square(4)
16

Pure Functions & Non-Pure Functions
Some functions just return values, for which we call Pure-Function. Some not, they have "side effects" like "print", we call them Non-Pure Function.

# print() function returns None
>>> print (print(1), print(2))
1
2
None, None

Lecture 3
In Python, there is an easy way to diff global and local frame:
stuff not indented -> global frame
stuff indented -> local frame

>>> 2 + 3 * 4 + 5
>>> add(add(2, mul(3, 4)), 5)
>>> (2 + 3) * (4 + 5)
>>> mul(add(2, 3), add(4, 5))

Python的一些除法运算：

>>> 2015 / 10 # truediv
201.5
>>> 2015 // 10 # floordiv
201
>>> 2015 % 10 # mod
5

这是一个很好的方法用来展示函数的功能，开头写一串示例，这个蛮神奇的。

def divide_exact(n, d):
    """Return the quotient and remainder of dividing N by D.
    >>> q, r = divide_exact(2015, 10)
    >>> q
    201
    >>> r
    5
    """
    return n // d, n % d

然后在终端调试，如果正确，终端就pass；如果错误，会报错：

''' ex.py is the filename of divide_exact '''
python -i ex.py # Python interactive model
python -m doctest ex.py 

Lecture 4
Fibonacci sequence, which is one of the most famous example for iteration.

''' Compute the nth Fibonacci number, for N >= 1. '''
def fib(n):
    pred, curr = 0, 1
    k = 1
    while k < n:
        pred, curr = curr, pred + curr
    return curr        

A Guide to Designing Function:
•Give each function exactly one job. If a function has two jobs, it should be two functions.
•Don’t repeat yourself (DRY). Implement a process just once, but execute it many times.
•Define functions generally. The function shouldn't solve all problems but problem that are the same kind.

Generalization.
Generalizing patterns with arguments: Finding common structure allows for shared implementation.

def area(r, shape_constant):
    # if r <= 0, the terminal will report error
    assert r > 0, 'A length must be positive' 
    return r * r * shape_constant

def area_square(r):
    return area(r, 1)

def area_circle(r):
    return area(r, pi)

Generalizing over computational processes: The common structure among functions may be a computational process, rather than a number.

def identity(k):
    return k

def cube(k):
    return pow(k, 3)

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

Locally Defined Functions
Functions defined within other function bodies are bound to names in a local frame.

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

>>> f = make_adder(3)
>>> f(4)
7

>>> make_adder(2010)(5)
2015

Lecture 5
Environments Enable Higher-Order Functions
Functions are first-class: Functions are values in our programming language
Higher-order function: A function that takes a function as an argument value or A function that returns a function as a return value

def apply_twice(f, x):
    return f(f(x))

def square(x):
    return x * x

>>> apply_twice(square, 4)
256

Local Names are not Visible to Other (Non-Nested) Functions:

def f(x, y):
    return g(x)

def g(a):
    return a + y

>>> f(1, 2)
Error: 'y' is not defined.

Function Composition

def square(x):
    return x * x

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

def compose(f, g):
    def h(x):
        return f(g(x))
    return h

>>> compose(square, make_adder(2))(3)
25

Lambda Expressions

>>> square = lambda x: x * x
>>> square(10)
100

Lecture 6
Recursion
Sum digits without a while statement

def split(n):
  return n  // 10, n % 10 # split(2015) -> 201, 5

def sum_digits(n):
  if n < 10: # base case
    return n
  else:
    all_but_last, last = split(n)
    return sum_digits(all_but_last) + last # recursive calls

Iteration vs Recursion
The recursion uses less names than the iteration function

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

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

The Luhn Algorithm
An algorithm to check whether a credit card number is right

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(last * 2)
  if n < 10:
    return luhn_digit
  else:
    return luhn_sum(all_but_last) + luhn_digit

Lecture 7
The Cascade Function: Figure out the orders of function call

def cascade(n):
  if n < 10:
    print(n)
  else:
    print(n)
    cascade(n // 10)
    print(n)

>>> cascade(123)
123
12
1
12
123

Inverse Cascade

def inverse_cascade(n):
  grow(n)
  print(n)
  shrink(n)

def f_then_g(f, g, n):
  if n:
    f(n)
    g(n)

grow = lambda n: f_then_g(grow, print, n // 10)
shrink = lambda n: f_then_g(print, shrink, n //10)

>>> inverse_cascade(123)
1
12
123
12
1

Tree Recursion

from ucb import trace
# This is a function decorator. 
# @trace can show every step when the function calls.
@trace
def fibonacci(n):
  if n == 0:
    return 0
  elif n == 1:
    return 1
  else:
    return fibonacci(n - 1) + fibonacci(n - 2) 

Counting Partitions
The number of partitions of a positive integer n, using parts up to size m, is the number of ways in which n can be expressed as the sum of positive integer parts up to m in increasing order.

def count_partition(n, m):
  if n == 0:
    return 1
  elif n < 0:
    return 0
  elif m == 0:
    return 0
  else:
    with_m = count_partition(n - m, m)
    without_m = count_partition(n, m -1)
    return with_m + without_m

Lecture 10
Sequence Unpacking in For Statements

>>> pairs = [[1, 2], [2, 2], [3, 2], [4, 4]]
for x,y in pairs: # x,y = 1,2; 2,2; 3,2; 4,4
  if x == y:
    count += 1

def cheers():
# '_' tells other programmers that the name doesn't matter
  for _ in range(3): 
    print('Cheers!')

>>>cheers()
'Cheers!'
'Cheers!'
'Cheers!'

List Comprehensions

>>> letters = ['a', 'b', 'c', 'd', 'e', 'f', 'm', 'n', 'o', 'p']
>>> [letters[i] for i in [3, 4, 6, 8]]
['d', 'e', 'm', 'o']

def divisors(n):
  return [1] + [x for x in range(2, n) if n % x == 0]

String

>>> 'curry = lambda f: lambda x: lambda y: f(x, y)'
# 'exec' function:
>>> exec('curry = lambda f: lambda x: lambda y: f(x, y)')
>>> curry(pow)(2)(4)
16

Dictionary

>>> dict([('X', 10), ('V', 5)])
{'X': 10, 'V': 5}

Lecture 11
Tree Abstraction

def tree(root, branches=[]):
  for branch in branches:
    assert is_tree(branch):
  return [root] + list(branches)
>>> tree(3, [tree(1, tree(2, [tree(1), tree(1)])])
>>> [3, [1], [2, [1], [1]]]

def root(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(trees):
    if not is_tree(branch):
      return False
  return True

def is_leaf(tree);
  return not branches(tree)

Fibonacci Tree

def fib_tree(n):
  if n == 0 or n == 1:
    return tree(n)
  else:
    left, right = fib_tree(n-1), fib_tree(n - 2)
    fib_n = root(left) + root(right)
    return tree(fib_n, [left, right])

Tree Processing Using Recursion

def count_leaves(tree):
  """Count the leaves of a tree."""
  if is_leaf(tree):
    return 1
  else:
    branch_counts = [count_leaves(b) for b in tree]
    return sum(branch_counts)

def leaves(tree):
  """Return a list containing the leaves of a tree."""
  if is_leaf(tree):
    return [root(tree)]
  else:
    return sum([leaves(b) for b in branches(tree)], [])

Partition Tree

def partition_tree(n, m):
  if n == 0:
    return tree(True)
  elif n < 0 or m == 0:
    return tree(False)
  else:
    left = partition_tree(n - m, m)
    right = partition_tree(n, m - 1)
    return tree(m, [left, right])

def print_parts(tree, partition= []):
  if is_leaf(tree):
    if root(tree):
      print(partition)
  else:
    left, right = branches(tree)
    print_parts(left, partition+[root(tree)])
    print_parts(right, partition)  

To be continued...