mynotes_chap00-01.Rmd

---
title: 'Coding the Matrix: Linear Algebra through Computer Science Applications (Coursera)'
author: "Zhiwei YANG (Jerry)"
date: "9 January 2016"
output: html_document
header-includes:
- \usepackage{amsmath,amssym,amsthm}
- \newtheorem{thm}{Theorem}
---

```{r setup, include=FALSE}
if (Sys.info()['sysname'] == "Windows") {
  knitr::opts_chunk$set(engine='python') # Windows
} else {
  knitr::opts_chunk$set(engine='python', engine.path='/usr/bin/python3') # Ubuntu (Linux)
}
```

This is the notes I put together while I was self-studying the Cousera course "Coding the Matrix: Linear Algebra through Computer Science Applications" by Professor Philip Klein from Brown University. 

Like in almost every other subject, it requires practice to gain real and deep understanding of linear algebra. Using linear algebra to think about problems in other domains then addressing these problems are the skills a student needs to continue to study other topics such as graphics and machine learning. To this end, this course and its textbook (also by Prof. Klein) use Python to build vectors and matrices from ground up. Using our own implementations of vector and matrix provides transparency. Python has a variety of built-in collection data structures, i.e. complex numbers, sets, lists (sequences) and dictionaries (which we use to represent functions). In addition, Python provides _comprehensions_, expressions that create collections using a simple but powerful syntax that resembles the mathematical notation for defining sets.

After quickly going through a crash Coursera course - "Programming for Everyone (Python)", I decided to hammer home these freshly acquired Python skills home by revisiting this course. Consequently, this set of notes are organised in a way that resembles the textbook (and roughly the course content), i.e. linear algebra mixed with Python programming.

## Chapter / Week 0: The Function and the Field (and other mathematical and computational preliminaries)
### 0.1 Set terminology and  notatoin
### 0.2 Cartesian product
### 0.3 The function
Loosely speaking, a function is a rule that for each element in some set $D$ of possible inputs, assigns a possible output. 

+ _image_
+ _pre-image_
+ domain

Formally, a _function_ is a (possibly infinite) set of pairs $(a, b)$ no two of which share the first entry.

For a function named $f$, the image of $q$ under $f$ is denoted by $f(q)$. If $r = f(q)$, we say that $q$ maps to $r$ under $f$. The notation for "$q$ maps to $r$" is $q\mapsto r$.

It is convenient when specifying a function to specify a _co-domain_ for the function. The co-domain is a set from which the function's output values are chosen. Note that one has some leeway in choosing the co-domain since not all of its members need to be outputs. The notation
\[
    f: D\longrightarrow F
\]
means that $f$ is a function whose domain is the set $D$ and whose _co-domain_ (the set of possible outputs) is the set $F$. (More briefly: "a function that maps $D$ to $F$.")

The _image_ of a function $f$ is the set of images of all domain elements. That is, the image of $f$ is the set of elements of the co-domain that actually occur as outputs.

#### 0.3.1 Functions versus procedures, versus computational problems
#### 0.3.2 The two computational problems related to a function
#### 0.3.3 Notation for the set of functions with given domain and co-domain 
For sets $D$ and $F$, we use the notation $F^D$ to denote __all functions__ from $D$ to $F$. This notation derives from a mathematical "pun":

__Fact 0.3.9:__ For any finite sets $D$ and $F$, $|F^D| = |F|^{|D|}$ (note that this is different from the textbook)

#### 0.3.4 Identity function
For any domain $D$, there is a function $\text{id}_D: D\longrightarrow D$ called the _identity function_, defined by
\[
    \text{id}_D(d) = d
\]
for every $d\in D$.

#### 0.3.5 Composition of functions
#### 0.3.6 Associativity of function composition
#### 0.3.7 Functional inverse
Not every function has an inverse. A function that has an inverse is said to be _invertible_.

__Definition 0.3.14:__ Consider a function $f: D\longrightarrow F$. We say that $f$ is _one-to-one_ if for every $x, y\in D$, $f(x) = f(y) \implies x = y$. We say that $f$ is _onto_ if, for every $z\in F$, there exists $x\in D: f(x) = z$.

### 0.5 Lab: Introduction to Python - sets, lists, dictionaries, and comprehensions

##### Arithmetic and numbers
+ Negative of a number: `-` as a unary operator
+ Exponentiation: `**` as the binary operator
+ Truncating integer division: `//`
+ Modulo (reminder): `%`

Task 0.5.1: Use Python to find the number of minutes in a week

```{r task051}
no_of_min_per_wk = 60 * 24 * 7
print(no_of_min_per_wk)
```

Task 0.5.2: Use Python to find the remainder of 2304811 divided by 47 without using the modulo operator `%`. (Hint: Use `//`)

```{r task052}
def remainder(num, den):
    return(num - (num//den) * den)

print(remainder(2304811, 47))
print(2304811%47)
```

Python uses a traditional programming notation for scientific notation. As we will discover, since Python uses limited-precision arithmetic (like every other programming language), there are round-off errors.

```{r roundofferr}
print(6.022e23)
print(6.626e-34)
print(1e16)
print(1e16 + 1)
```

##### Strings
+ A string is a series of characters that starts and ends with a sing-quote mark. We can also use double-quote marks which are useful if the string itself contains a single-quote mark. 
+ Python is doing what it usually does: it _evaluates_ the string expression it is given and prints the value. The value of a string is just the string itself.

```{r strings}
print("So's this one.")
```

##### Comparisons and conditions and Booleans
+ The value of a comparison is a Boolean value (`True` or `False`). An expression whose value is a Boolean is called a Boolean expression.
+ Boolean operators such as `and`, `or` and `not` can be used to form more complicated Boolean expressions.

```{r ccb}
print(5 == 4)
print(4 == 4)
print(True and False)
print(True and not (5 == 4))
```

Task 0.5.3: Enter a Boolean expression to test whether the sum of 673 and 909 is divisible by 3.

```{r task053}
print((673 + 909) - ((673 + 909)//3) * 3 == 0)
print((673 + 909)%3 == 0)
```

#### 0.5.2 Assignment statements
+ A variable name must start with a letter and must exclude certain special symbols such as the dot (period).
+ The underscore `_` is allowed in a variable name. 
+ A variable can be bound to a value of _any type_.

It is important to remember (and second nature to most experienced programmers) that an assignment statement binds a variable to the _value_ of an expression, not to the expression itself. Python first evaluates the right-hand side and only then assigns the resulting value to the left-hand side. This is the behaviour of most programming languages.

```{r 052}
mynum = 4 + 1
print(mynum)
mynum = 'Brown' # rebind
print(mynum)

x = 5 + 4
y = 2 * x # y is assigned to the value of the expression
print(y)

x = 12 # does not change the fact that y is bound to 18
print(y)
```

#### 0.5.3. Conditional expressions
Python evaluates the condition; depending on whether it is `True` or `False`, it then evaluates either the first or second _expression_, and uses the result as the result of the entire conditional expression.

For example, the value of the expression `x if x>0 else -x` is the absolute value of `x`.

Task 0.5.4: Assign the value `-9` to `x` and `1/2` to `y`. Predict the value of the following expression, then enter it to check your prediction.

```{r task054}
x = -9
y = 1/2
print(2**(y+1/2) if x+10<0 else 2**(y-1/2))
```

#### 0.5.4 Sets
Python provides some simple data structures for grouping together multiple values, and integrates them with the rest of the language. These data structure are called _collections_, the simplest of which are sets. 

A set is an _unordered_ collection in which each value occurs at most once. We can use curly braces to give an expression whose value is a set. Python also prints sets using curly braces.

Note that duplicates are eliminated and that the order in which the elements of the output are printed does not necessarily match the order of the input elements.

The _cardinality_ of a set $S$ is the number of elements in the set. We write $|S|$ for the cardinality of set $S$. In Python, the cardinality of a set is obtained using the procedure `len()`.

```{r sets}
s1 = {1+2, 3, "a"}
print(s1)
s2 = {2, 1, 3}
print(s2)
s3 = {'a', 'b', 'c', 'a', 'a'}
print(s3)
print(len(s3))
```

##### 0.5.4.1 Summing
The sum of elements of collection of values is obtained using the procedure `sum()`.

```{r sum}
print(sum({1, 2, 3}))
print(sum({1, 2, 3}, 10)) # start sum at 10
```

##### 0.5.4.2 Testing set membership
Membership in a set can be tested using the `in` and `not in` operator. 

```{r in}
S = {1, 2, 3}
print(2 in S)
print(4 in S)
print(4 not in S)
```

##### 0.5.4.3 Set union and intersection
Python uses the vertical bar `|` and the ampersand `&` as the _union_ and _intersection_ operator respectively.

```{r setops}
s1 = {1, 2, 3} | {2, 3, 4}
s2 = {1, 2, 3} & {2, 3, 4}
print(s1)
print(s2)
```

##### 0.5.4.4 Mutating a set
A value that can be altered is a _mutable_ value. Sets are mutable; elements can be added and removed using the `add` and `remove` methods. 

The syntax using the dot is exactly the same as in the object-oriented programming languages such as Java and C++. The operations `add()` and `remove()` are _methods_. We can think of a method as a procedure that takes an extra argument, the value of the expression to the left of the dot.

Python provides a method `update()` to add to a set all the elements of another collection (e.g. a set or a list).

Similarly, one can intersect a set with another collection, removing from the set all the elements not in the other collection.

Suppose two variables are bound to the same value. A mutation to the value made through one variable is seen by the other variable. This behaviour reflects the fact that Python stores only one copy of the underlying data structure. After Python executes the assignment statement `T=S`, both `T` and `S` point to the same data structure. This aspect of Python will be important to us: many different variables can point to the same huge set without causing a blow-up of storage requirements. 

Python provides a method for copying a collection such as a set.

```{r mutate}
S = {1, 2, 3}
S.add(4)
S.remove(2)
print(S)

S.update({4, 5, 6})
print(S)

S.intersection_update({5, 6, 7, 8, 9})
print(S)

T = S
T.remove(5)
print(S)

U = S.copy()
U.add(5) # S is not affected
print(U)
print(S)
```

##### 0.5.4.5 Set comprehensions
Python provides `for` expressions called _comprehensions_ that let us build collection out of other collections. We will be using comprehensions a lot because they are useful in constructing an expression whose value is a collection, and they mimic traditional mathematical notation.

```{r setcomp}
comp = {2*x for x in {1, 2, 3}}
print(comp)
```

It is called a set comprehension because the value is a set. The notation is similar to the traditional mathematical notation for expressing sets in terms of other sets, in this case $\{2x: x\in\{1, 2, 3\}\}$. To compute the value, Python iterates over the elements of the set $\{1, 2, 3\}$, temporarily binding the _control variable_ `x` to each element in turn and evaluating the expression `2*x` in the context of that binding. Each of the values obtained is an element of the final set. (The bindings of `x` during the evaluation of the comprehension do no persist after the evaluation completes.)

Task 0.5.5: Write a comprehension over `{1, 2, 3, 4, 5}` whose value is the set consisting of the squares of the first five positive integers.

```{r task055}
sqrs = {x**2 for x in {1, 2, 3, 4, 5}}
print(sqrs)
```

Task 0.5.6: Write a comprehension over `{0, 1, 2, 3, 4}` whose value is the set consisting of the first five powers of two, starting with $2^0$

```{r task056}
powers = {2**x for x in {1, 1, 2, 3, 4}}
print(powers)
```

Using the union operator `|` or the intersection operator `&`, we can write set expressions for the union or intersection of two sets and use such expressions in a comprehension.

By adding the phrase `if` (_condition_) at the end of the comprehension (before the closing brace `}`), we can skip some of the values in the set being iterated over - subsetting. The author calls the conditional clause a _filter_.

We can also write a comprehension that iterates over the Cartesian product of two sets. The comprehension constructs the set of the products of every combination of `x` and `y`, called _double comprehension_.

```{r setcomp2}
S = {1, 3}
print({x**2 for x in S | {5, 7}})
print({x**2 for x in S | {5, 7} if x > 2})
print({x*y for x in {1, 2, 3} for y in {2, 3, 4}})
```

Task 0.5.7 The value of the previous comprehension is a seven-element set. Replace the two input sets with two other three-element sets so that the value become a nine-element set.

```{r task057}
print({x*y for x in {1, 2, 3} for y in {5, 7, 9}})
```

```{r setcomp3}
print({x*y for x in {1, 2, 3} for y in {2, 3, 4} if x != y})
```

Task 0.5.8 Replace `{1, 2, 3}` and `{2, 3, 4}` in the  previous comprehension with two disjoint (i.e. non-overlapping) three-element sets so that the value becomes a five-element set.

```{r task058}
print({x*y for x in {0, 2, 4} for y in {1, 1/2, 1/4} if x != y})
```

Task 0.5.9 Assume that `S` and `T` are assigned sets. Without using the _intersection operator_ `&`, write a comprehension over `S` whose value is the intersection of `S` and `T`. Hint: Use a membership test in a filter at the end of the comprehension.

```{r task059}
S = {1, 2, 3, 4}
T = {3, 4, 5, 6}
print({x for x in S if x in T})
print(S & T)
```

##### 0.5.4.6 Remarks
The empty set is represented by `set()`. We would think that `{}` would work out, as we will see, that notation is used for something else.

We cannot make a set that has a set as element. This has nothing to do with Cantor's Paradox - Python imposes the restriction that the elements of a set must not be mutable, and sets are mutable. The reason for this restriction will be clear to a student of data structures from error message like below:

```{r sets2}
# {{1, 2}, 3}
```

There is a nonmutable version of set called _frozenset_. Frozensets can be elements of sets.

#### 0.5.5 Lists
Python represents __sequences__ of values using _lists_. In a list, __order__ is significant and __repeated__ elements are allowed. The notation for lists use square brackets instead of curly braces. The empty list is represented by `[]`.

There are no restrictions on the elements of lists. A list can contain a set or another list.

However, a set cannot contain a list since lists are _mutable_. 

The _length_ of a list, obtained using the procedure `len()`, is the number of elements in the list, even though some of those elements may themselves be lists, and even though some elements might have the same value.

The sum of elements of a collection can be computed using `sum()`.

```{r lists}
print([1, 1+1, 3, 2, 3])
print([[1, 1+1, 4-1], {2*2, 5, 6}, "yo"])
print(len([[1, 1+1, 4-1], {2*2, 5, 6}, "yo", "yo"]))
print(sum([1, 1, 0, 1, 0, 1, 0]))
print(sum([1, 1, 0, 1, 0, 1, 0], -9))
```

Task 0.5.10: Write an expression whose value is the average of the elements of the list `[20, 10, 15, 75]`

```{r task0510}
l = [20, 10, 15, 75]
print("average of the list above is", sum(l)/len(l))
```

##### List concatenation
We can combine the elements in one list with the elements in another list to form a new list (without changing the original lists) using the `+` operator.

We can use `sum()` on a collection of lists, obtaining the _concatenation_ of all the lists, by providing `[]` as the second argument.

```{r lists2}
print([1, 2, 3] + ["my", "word"])
mylist = [4, 8, 12]
print(mylist + ["my", "word"])
print(mylist) # mylist was left alone
print(sum([[1, 2, 3], [4, 5, 6], [7, 8, 9]], []))
```

##### List comprehensions
A list comprehension is a comprehension whose value is a list.

Note that whether the order in the resulting list is significant depends on the collection type, i.e. set and list.

We can also write list comprehensions that iterate over multiple collections using two control variables - "double comprehensions". Hence we can use a comprehension over two sets to form the Cartesian product.

```{r lc}
print([2*x for x in {2, 1, 3, 4, 5}]) # order not significant
print([2*x for x in [2, 1, 3, 4, 5]]) # order significant
print([x*y for x in [1, 2, 3] for y in [10, 20, 30]])
```

Task 0.5.11 Write a double list comprehension over the lists `['A', 'B', 'C']` and `[1, 2, 3]` whose value is the list of all possible two-element lists `[letter, number]`.

```{r task0511}
print([[x, y] for x in ['A', 'B', 'C'] for y in [1, 2, 3]])
```

Task 0.5.12 Write an expression that evaluates to the sum of all the numbers in all the lists

```{r task0512}
LofL = [[.25, .75, .1], [-1, 0], [4, 4, 4, 4]]
print(sum(sum(LofL, [])))
```

There are two ways to obtain an individual element of a list. The first is by indexing. As in some other languages (Java and C++, for example)  indexing is done using square brackets around the index.

```{r lists3}
mylist = [4, 8, 12]
print(mylist[0])
```

__Slices:__ A _slice_ of a list is a new list consisting of consecutive subsequence of elements of the old list, namely those indexed by a range of integers. The range is specified by a colon-separated pair `i:j` consisting of the index `i` as the first element and `j` as one past the index of th last element. 

__Prefxes:__ If the first element `i` of the pair is 0, it can be omitted, so `mylist[:2]` consists of the first 2 elements of `mylist`. This notation is useful for obtaining a prefix of a list.

__Suffixes:__ If the second element `j` of the pair is the length of the list, it can be omitted, so `mylist[1:]` consists of all elements of `mylist` except element 0. 

__Slices that skip__ We can use a colon-separated _triple_ `a:b:c` if we want to slice to include every cth element. It's useful when extracting even-indexed and odd-indexed elements of a list.

```{r lists4}
L = [0, 10, 20, 30, 40, 50, 60, 70, 80, 90]
print(L[:5])
print(L[5:])
print(L[::2])
print(L[1::2])
```

__Obtaining elements of a list by unpacking__

The second way to obtain individual elements is by _unpacking_. Instead of assigning a list to a single variable as in `mylist = [4, 8, 12]`, one can assign a list of variables. Note that Python does not allow us to create a value that is a list of variables. The assignment is simply a convenient way to assign to each of the variables appearing in the left-hand side.

```{r lists5}
[x, y, z] = [4*1, 4*2, 4*3]
print(x)
print(y)
```

Task 0.5.13 Find out what happens if the length of the left-hand side list does not match the length of the right-hand side lists.

```{r task0513}
# [x, y, z] = [4*1, 4*2]
# [x, y] = [4*1, 4*2, 4*3]
```

Unpacking can similarly be used in comprehensions. Below the two-element list `[x, y]` iterates over all elements of `listoflists`. This would result in an error message if some elements of `listoflists` were not two-element list.

```{r lists6}
listoflists = [[1, 1], [2, 4], [3, 9]]
print([y for [x, y] in listoflists])
```

__Mutating a list: indexing on the left-hand side of `=`__

We can mutate a list, replacing its $i$th element, using indexing on the left-hand side of the `=`, analogous to an assignment statement.

```{r lists7}
mylist = [30, 20, 10]
mylist[1] = 0
print(mylist)
```

#### 0.5.6 Tuples
List a list, a tuple is an _ordered sequence_ of elements. However, tuples are _immutable_ so they can be elements of sets. The notation for tuples is the same as that for lists except that ordinary parentheses are used instead of square brackets.

```{r tuples}
print((1, 1+1, 3))
print({0, (1, 2)} | {(3, 4, 5)})
```

#### Obtaining elements of a tuple by _indexing_ and _unpacking_. 

Both indexing and unpacking can be used to obtain element(s) of a tuple.

In some contexts, we can get away without the parentheses.

```{r tuples2}
mytuple = ("all", "my", "books")
print(mytuple[1])
print((1, {"A", "B"}, 3.14)[2])

(a, b) = (1, 5-3)
print(a, b)

a, b = (1, 5-3)
a, b = 1, 5-3

print([x for (x, y) in [(1, 'A'), (2, 'B'), (3, 'C')]])
print([y for (x, y) in [(1, 'A'), (2, 'B'), (3, 'C')]])
```

Task 0.5.14: Suppose $S$ is a set of integers, e.g. $\{-4, -2, 1, 2, 5, 0\}$. Write a triple comprehension whose value is a list of all three-element tuples $(i, j, k)$ such that $i, j, k$ are elements of $S$ whose sum is zero.

```{r task0514}
S = {-4, -2, 1, 2, 5, 0}
print(S)
l = [(i, j, k) for i in S for j in S for k in S if i + j + k == 0]
print(l)
```

Task 0.5.15: Modify the comprehension of the previous task so that the resulting list does not include $(0, 0, 0)$. Hint: add a filter.

```{r task0515}
S = {-4, -2, 1, 2, 5, 0}
l1 = [(i, j, k) for i in S for j in S for k in S if i + j + k == 0 and (i != 0 or j != 0 or k != 0)]
l2 = [(i, j, k) for i in S for j in S for k in S if i + j + k == 0 and not (i == 0 and j == 0 and k == 0)]
print(l1)
print(l2)
```

Task 0.5.16: Further modify the expression so that its value is not the list of all such tuples but is the first such tuple.

```{r task0516}
S = {-4, -2, 1, 2, 5, 0}
l2 = [(i, j, k) for i in S for j in S for k in S if i + j + k == 0 and not (i == 0 and j == 0 and k == 0)]
print(l2[0])
```

#### Obtaining a list or set from another collection
Python can compute a set from another collection (e.g. a list) using the constructor `set()`. Similarly, the constructor `list()` computes a list, and the constructor `tuple()` computes a tuple.

```{r constructors}
print(set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]))
print(set([1, 2, 3]))
print(list({1, 2, 3}))
print(tuple({1, 2, 3}))
print(tuple([4, 5, 6]))
```