Rudolf Adamkovič

• thinking through writing
• improving free software
• playing table tennis
• exploring by folding bike
• cooking and baking simply

Master of Science (MSc) in Artificial Intelligence
2024–2026, EU-accredited degree, remote
Munster Technological University, Cork, Munster, Ireland, EU

Bachelor of Science (BSc) in Computer Science, Summa Cum Laude
2018–2023, US-accredited degree, remote
University of the People, Pasadena, California, USA

Add support for LaTeX mathematics to Texinfo exports
Org mode, GNU Emacs, Free Software Foundation
https://list.orgmode.org/m2wngizda3.fsf@me.com/
org-mode.git/commit/?id=c940b460c

Upgrade from MathJax 2 to MathJax 3+
Org mode, GNU Emacs, Free Software Foundation
https://list.orgmode.org/orgmode/m2a667n4ax.fsf@me.com/
org-mode.git/commit/?id=62e1513b5

• formal science
• empirical science

• basic science
• applied science

• “hard” or “real” science
• behavioral science

• inductive
• deductive

• mathematics
• computer science

• natural sciences
• social sciences

If the test results match objective reality,

the hypothesis becomes a scientific fact,

possibly supporting a scientific theory.

Not to be confused with mathematical induction.

See deductive reasoning.

Observing pea plants to discover Mendelian inheritance.

Predicting phenotypes of pea plants using Mendelian inheritance.

See inductive reasoning.

Alexander Fleming found mold on his dish killing bacteria, discovering penicillin, the antibiotic produced by the fungus Penicillium.

Often solves real-world problems anyway.

See applied science.

See basic science.

• physical sciences
• life sciences

Also cross-disciplines, e.g. environmental science.

• physics
• chemistry

Requires rigorous statistical analysis, or it decays to pseudoscience.

• psychology
• pre-Galilean physics

(defun my-within-order-of-magnitude-p (x y &optional n b)
  "Return t if X is within N orders of base-B magnitudes of Y.

By default, check for 1 order of base-10 magnitude."
  (let ((n (or n 1))
        (b (or b 10)))
    (and (> (/ (float x) y) (expt b (- 0 n)))
         (< (/ (float x) y) (expt b (+ 0 n))))))

(and (my-within-order-of-magnitude-p 1.00 1.01)
     (my-within-order-of-magnitude-p 1000 1010))

t

(seq-map (lambda (number)
           (list number
                 (my-within-order-of-magnitude-p 1 number)))
         (number-sequence 1 15))

• physics
• chemistry
• medicine
• economics
• literature
• peace

• Turing award in computer science
• Fields medal in mathematics

Each paper has a title and the sections

1. Abstract
2. Introduction (with Research aim and Research questions)
3. Methodology
4. Results and Discussion
5. Conclusion

where each section motivates the next.

Typically 150–300 words, one paragraph.

High-level, yet technical; not coupled to methodology.

Typically one complex sentence.

High-level, yet technical; not coupled to methodology.

Typically 3 to 4 per research paper.

See research objectives.

Typically written in simple past tense, either active or passive voice.

Documents results from most to least important.

Typically written in

• past simple for actions performed
• present simple for standing facts

without interpretation, which is reserved for Discussion.

Discusses each result from specific findings to broad implications.

Typically written in present tense.

Addresses research questions, covering

• evidence
• surprises
• limitations
• comparisons
• speculations
• …

Typically written in present tense.

Presented at academic conferences.

Light on text, heavy on figures and whitespace.

There is no science without mathematics, hence

“Mathematics is the queen of all sciences.”

— Carl Friedrich Gauss

Ethically licensed reliable sources, alphabetically:

The set of all reals \(\mathbb{R}\).

Conceptually, continuous is the opposite of discrete.

Conceptually, continuous is synonymous to “analog” in electronics.

The set of all integers \(\mathbb{Z}\).

Conceptually, discrete is the opposite of continuous.

Conceptually, discrete is synonymous to “digital” in electronics.

World-smartest pre-university, pre-calculus students.

Every year in a different country.

https://www.imo-official.org/

Given every 4 years, starting 1936.

Nobel prize of mathematics, like the Turing award in computer science.

The standard form of a monomial is

where

• \(a\) is a constant or coefficient
• \(x_i\) is the \(i\)-th variable or indeterminate
• \(n_i\) is the non-negative integer exponent of \(x_i\).

Monomials include:

• \(42\)
• \(42 x\)
• \(42 x^2\)
• \(42 x y\)
• \(42 x^1 y^2\)

The standard form of a univariate polynomial is

Polynomials include:

• \(42\)
• \(42 x\)
• \(42 x^2\)
• \(x + 1\)
• \(x^2 + 2 x + 1\)
• \(3 x^2 y + 2 x y - 7\)

Compute whether a given molecular statement is a tautology.

Compute a truth table for the given molecular statement.

Most tightly to least tightly binding:

Parentheses set the precedence to zero, like in arithmetic.

The truth table for the statement \(\lnot P\) is

<<scheme/truth-table>>
(define (org-truth-table procedure headers)
  (append (list (map (lambda (header)
                       (string-append "\\(" header "\\)"))
                     headers))
          (list (list))
          (list (append (list "/")
                        (make-list (- (length headers) 2) "")
                        (list "<")))
          (map (lambda (row)
                 (map (lambda (value)
                        (if value
                            "true"
                            "false"))
                      row))
               (truth-table procedure
                            (- (length headers)
                               1)))))
(org-truth-table not '("P" "\\lnot P"))

Construct the truth table for the statement \(P \land Q\).

<<scheme/org-truth-table>>
(org-truth-table (lambda (p q) (and p q)) '("P" "Q" "P \\land Q"))

Denote \(n\)-nary⁶ conjunction by

or equivalently by

given the set of operands \(S = \{x_1, x_2, \ldots, x_{n - 1}, x_n\}\).

Construct the truth table for the statement \(P \lor Q\).

<<scheme/org-truth-table>>
(org-truth-table (lambda (p q) (or p q))
                 '("P" "Q" "P \\land Q"))

Denote \(n\)-nary⁷ disjunction by

or equivalently by

given the set of operands \(S = \{x_1, x_2, \ldots, x_{n - 1}, x_n\}\).

The law of non-contradiction (LNC) is

the most fundamental law of propositional logic,

without which classical reasoning would collapse.

The law of non-contradiction (LNC) enables proof by contradiction.

The law of excluded middle enables proof by cases.

By the definitions of equivalence and implication,

and those are tautologies, per

<<scheme/tautology?>>
(and (tautology? (lambda (p q)
                   (and (or (not (not (and p q)))
                            (or (not p) (not q)))
                        (or (not (or (not p) (not q)))
                            (not (and p q)))))
                 2)
     (tautology? (lambda (p q)
                   (and (or (not (not (or p q)))
                            (and (not p) (not q)))
                        (or (not (and (not p) (not q)))
                            (not (or p q)))))
                 2))

#t

so De Morgan’s laws are always true. \(\blacksquare\)

Construct the truth table for the statement

<<scheme/org-truth-table>>
(org-truth-table (lambda (p q) (or (not p) q))
                 '("P" "Q" "P \\implies Q"))

[7, Sec. 0.2], [12, Sec. 5.1]

For example, the molecular statement

“if you are dancing, you are sweating”

is equivalent to

“if you not sweating, you are not dancing”.

The statement

“if you are dancing, you are sweating”

is not equivalent to

“if you are sweating, you are dancing”,

as you might be

sweating for a different reason.

Prove the statement

By the definition of the conditional and the biconditional,

which is not a tautology, as per

<<scheme/tautology?>>
(not (tautology? (lambda (p q)
                   (and (or (not (or (not p) q))
                            (or (not q) p))
                        (or (not (or (not q) p))
                            (or (not p) q))))
                 2))

#t

\(\blacksquare\)

Construct the truth table for the statement

<<scheme/org-truth-table>>
(org-truth-table (lambda (p q)
                   (and (or (not p) q)
                        (or (not q) p)))
                 '("P" "Q"
                   "P \\iff Q"))

In conjunctive normal form, exclusive disjunction is

Construct the truth table for the statement

<<scheme/org-truth-table>>
(org-truth-table (lambda (p q)
                   (or (and p (not q))
                       (and (not p) q)))
                 '("P" "Q" "P \\oplus Q"))

mutual exclusivity

at most one statement is true

exclusive disjunction

exactly one statement is true

In conjunctive normal form, mutual exclusivity is

by De Morgan’s laws.

Construct the truth table for the statement

<<scheme/org-truth-table>>
(org-truth-table (lambda (p q) (not (and p q)))
                 '("P" "Q" "\\lnot (P \\land Q)"))

If you are dancing, you are sweating.
You are dancing.
Therefore, you are sweating.

Let \(P(x)\) mean “\(x\) is even”. Then

is a tautology.

Equivalent to the existential quantifier under negation by

which is akin to De Morgan’s laws, with \(\forall\) generalizing conjunction.

There is no smallest integer \(k\) because

that is

for every integer \(k\),
there exists some integer \(\ell\)
smaller than \(k\),

such as \(\ell = k - 1\).

Equivalent to the universal quantifier under negation by

which is akin to De Morgan’s laws, with \(\exists\) generalizing disjunction.

There is no greatest integer \(k\) because

that is

for every integer \(k\),
there exists some integer \(\ell\)
greater than \(k\),

such as \(\ell = k + 1\).

The most fundamental object in mathematics [7].

Either:

• a special set with a standard definition,
• a set derived from another using set operations,
• a set defined in-place, typically by enumeration or set builder notation.

The cardinality of any given set \(S\) is denoted

Cardinality can be

• finite,
  e.g. the Boolean domain, \(|\mathbb{B}|\)
• countably infinite,
  e.g. the set of all integers \(|\mathbb{Z}|\)
• uncountably infinite,
  e.g. the set of all reals \(|\mathbb{R}|\)

Using set enumeration, the empty set is defined as

The set \(S\) is countably infinite iff

The set of all positive integers,

Another common way to define a set is the set builder.

The members can be constrained to a domain on the left-hand side,

The set of all positive integers,

A colon (\(:\)) can be used in place of the vertical bar (\(\vert\)), so

The union \(A \cup B\) in set theory is

analogous to disjunction \(A \lor B\) in logic,

hence the similar symbols.

The big union symbol

with \(\mathcal{U} = \{S_1, \ldots, S_n\}\).

Cardinality of finite sets is given by

The universe is typically denoted \(\mathcal{U}\) or \(\mathbb{D}\).

Declaring \(E\) as a set of sets, has two consequences:

• no two vertices connect more than once, and
• no vertex connects with itself.

Alphabetically:

A linear equation of one variable has the form

and its solution is

Linear systems are one of the key modeling tools of science.

Every linear system is

either consistent or inconsistent,

depending on its solution set.

Every linear system is

either homogeneous or not.

The consistent system is the opposite of the inconsistent system.

Not consistent.

A linear equation or linear system is inconsistent when

the last column of its augmented matrix is a pivot column.

The augmented matrix

represents an inconsistent system, for per the last row

which is impossible, as

The sole link between the two operations is

the distributivity of multiplication over addition.

For all scalars \(\{a, b, c\} \subseteq F\), it

• commutes, so

  \(a + b = b + a\)

• associates, so

  \((a + b) + c = a + (b + c)\),

• has the exactly one additive identity: \(0\), so

  \(a + 0 = a\),

• has the exactly one additive inverse: \(-a\), so

  \(a + (-a) = 0\).

Denote \(n\)-nary⁹ addition with “the big sigma”

or equivalently

given the set of terms \(S = \{x_1, x_2, \ldots, x_{n - 1}, x_n\}\).

For all scalars \(\{a, b, c\} \subseteq F\), it

• commutes, so

  \(ab = ba\),

• associates, so

  \((ab)c = a(bc)\),

• distributes over addition, so

  \(c(a + b) = ca + cb\),

• has the exactly one multiplicative identity: \(1\), so

  \(1a = a\),

• has the exactly one multiplicative inverse: \(1 / a\), so

  \(\frac{1}{a} a = a^{-1} = 1\).

Denote \(n\)-nary¹⁰ multiplication with “the big pi”

or equivalently

given the set of terms \(S = \{x_1, x_2, \ldots, x_{n - 1}, x_n\}\).

The sole link between the two operations is

the distributivity of vector scaling over vector addition.

To communicate that \(\forall \vec{v} \in V\),

\(\vec{v}\) has exactly \(n\) components,

write \(V^n\)

Imagine in the real plane as either

• the point \(P = (v_1, v_2)\) or
• the line segment from the origin to \(P\).

The vector notation

is shorthand for a linear combination of the standard basis

— https://thenumb.at/Functions-are-Vectors/

Geometrically:

1. Draw \(\vec{u}\) and \(\vec{v}\) head to tail.
2. Draw \(\vec{u} + \vec{v}\) from the free tail to the free head.

[14]

For all vectors \(\{\vec{u}, \vec{v}, \vec{w}\} \subseteq V\), it

• commutes, so

  \(\vec{u} + \vec{v} = \vec{v} + \vec{u}\),

• associates, so

  \((\vec{u} + \vec{v}) + \vec{w} = \vec{u} + (\vec{v} + \vec{w})\),

• has exactly one additive identity: the zero vector \(\vec{0}\), so

  \(\vec{v} + \vec{0} = \vec{v}\),

• has exactly one additive inverse: \(-\vec{v}\), so

  \(\vec{v} + (-\vec{v}) = \vec{0}\).

… in Scheme as

… in Scheme as

Draw \(a \vec{v}\) as a copy of \(\vec{v}\) with

• its length \(|a|\) times larger than that of \(\vec{v}\) and
• its direction reversed if \(a < 0\).

Per its algebraic properties,

• for all vectors \(\{\vec{u}, \vec{v}\} \subseteq V\) and
• for all scalars \(\{a, b\} \subseteq F\),

it:

• commutes, so

  \(a \vec{v} = \vec{v} a\);

• associates, so

  \((a b) \vec{v} = a (b \vec{v})\);

• distributes over vector addition, so

  \(a(\vec{u} + \vec{v}) = a \vec{u} + a \vec{v}\); and

• has exactly one multiplicative identity: \(1\), so

  \(1 \vec{v} = \vec{v}\).

In Scheme:

In the real plane \(\mathbb{R}^2\):

1. Draw \(\vec{v}\) as a point \(P\).
2. Measure the length from the origin to \(P\).

The correspondence with Pythagorean theorem:

1. Recall that \(c^2 = a^2 + b^2\) and so \(c = \sqrt{a^2 + b^2}\).
2. Set \(a = v_1\), \(b = v_2\), and \(c = \|\vec{v}\|\).
3. Get \(\|\vec{v}\| = \sqrt{{v_1}^2 + {v_2}^2}\).

For vectors with bounded nonzero components, vector length grows asymptotically in the number of dimensions,

as seen with all-ones vectors

… in Scheme as

The vector equation

is equivalent to the matrix equation

The vector equation

is equivalent to the linear system with the augmented matrix

The vector equation

asserts that

\(\vec{b}\) is a linear combination of \(\vec{a}_1, \ldots, \vec{a_n}\)

if and only if there exists a solution to the equivalent matrix equation

or the equivalent linear system with the augmented matrix

The product of

• the length of \(\vec{u}\) and
• the length of \(\vec{v}\) projected onto \(\vec{u}\).

Its extrema are \(\pm \|\vec{u}\| \|\vec{v}\|\), and it

• Commutes, so

  \(\vec{u} \cdot \vec{v} = \vec{v} \cdot \vec{u}\);

• distributes over vector addition, so

  \(\vec{u} \cdot (\vec{v} + \vec{w}) = \vec{u} \cdot \vec{v} + \vec{u} \cdot \vec{w}\);

• associates with respect to scalar multiplication, so

  \((c \vec{u}) \cdot \vec{v} = c (\vec{u} \cdot \vec{v}) = \vec{u} \cdot (c \vec{v})\).

The dot product

of two vectors

• \(\vec{u} \in \mathbb{R}^{n}\)
• \(\vec{v} \in \mathbb{R}^{n}\)

is a scalar \(a \in \mathbb{R}\).

The dot product, generalized as the inner product,

decreases the number of dimensions,

whereas the outer product increases them.

In Scheme:

The outer product is often

implicit in numerical computing tools,

including NumPy and TensorFlow,

via broadcasting.

The outer product

of two vectors

• \(\vec{u} \in \mathbb{R}^{m}\)
• \(\vec{v} \in \mathbb{R}^{n}\)

is a matrix \(M \in \mathbb{R}^{m \times n}\).

The outer product

increases the number of dimensions,

whereas the inner product decreases them.

In the real plane \(\mathbb{R}^2\):

1. Draw \(\vec{u}, \vec{v}\) as points \(P\) and \(Q\).
2. Measure the length of the line segment \(\overline{PQ}\).

… is

… the closed form as

with

1. by vector,
2. by vector length,
3. by dot product,
4. by exponentiation, and
5. by summation.

… the closed form as

with

1. by vector,
2. by vector length,
3. by the dot product in terms of the matrix transpose,
4. by the matrix transpose,
5. by matrix multiplication, and
6. by exponentiation.

… in Scheme as

For all matrices \(A, B, C\), it

• commutes, so

  \(A + B = B + A\),

• associates, so

  \((A + B) + C = A + (B + C)\),

• has exactly one additive identity: the zero matrix, so

  \(A + 0_{m \times n} = A\),

• has exactly one additive inverse: \(-A\), so

  \(A + (-A) = 0_{m \times n}\).

For all matrices \(A, B\) and scalars \(c, d\), it

• commutes, so

  \(c A = A c\),

• associates, so

  \(c (d A) = (c d) A\),

• distributes over matrix addition, so

  \(c (A + B) = c A + c B\), and

• has exactly one multiplicative identity: \(1\), so

  \(1 A = A\).

Viewing \(A\) by rows and \(B\) by columns, matrix multiplication computes pairwise dot products per

The resulting dimensions are

where

• \(A_{m \times p}, B_{p \times n}\) are the factors
• \(AB\) is the resulting product.

\(A \vec{b}\) and \(AB\) are

undefined if the number of columns in \(A\) does not match

• the number of components in \(\vec{b}\) and
• the number of rows in \(B\),

respectively, as

every column of \(A\) must be scaled

by some weight.

For all matrices \(A, B, C\), vectors \(\vec{u}, \vec{v}\), and scalars \(c\), it

• associates, so

  \((A B) C = A (B C)\),

• associates with respect to matrix scaling and vector scaling, so

  \(c ( A B ) = ( c A ) B = A ( c B )\) \(\qand\) \(c ( A \vec{u} ) = ( c A ) \vec{u} = A ( c \vec{u} )\),

• left-distributes over matrix addition and vector addition, so

  \(A ( B + C ) = A B + A C\) \(\qand\) \(A ( \vec{u} + \vec{v} ) = A \vec{u} + A \vec{v}\)

• and its multiplicative identity is the identity matrix, so

  \(I A = A I = A\) \(\qand\) \(I \vec{u} = \vec{u}\).

For some matrices \((A, B)\), it

• does not commute, so

  \(A B \neq B A\)

• does not cancel, so

  \(\bcancel{A} B = \bcancel{A} C \,\,\,\,\, \not \!\!\!\!\! \iff B = C\)

• does not zero-multiply, so

  \(A B = 0 \,\,\,\,\, \not \!\!\!\!\! \iff A = 0 \lor B = 0\).

Compute by hand:

Compute with NumPy:

import numpy

a = numpy.array([[1, 2],
                 [3, 4]])

b = numpy.array([[5, 6],
                 [7, 8]])

a @ b

[[19 22]
 [43 50]]

The matrix equation

is equivalent to the vector equation

The matrix equation

is equivalent to the linear system with the augmented matrix

If the matrix \(A\) in the matrix equation

is invertible, then a unique solution

exists for each \(\vec{b} \in \mathbb{R}^n\).

Solve \(A \vec{x} = \vec{0}\), given

1. Write the augmented matrix and row-reduce it.

   \begin{align*} \begin{pmatrix} \vphantom{\Big(} A & \vec{0} \, \end{pmatrix} & = \begin{pmatrix} 1 & -2 & 3 & 0 \\ 2 & 1 & -1 & 0 \\ -3 & -4 & 5 & 0 \end{pmatrix} \\[2ex] \operatorname{rref} \begin{pmatrix} \vphantom{\Big(} A & \vec{0} \, \end{pmatrix} & = \begin{pmatrix} 1 & 0 & \frac{1}{5} & 0 \\ 0 & 1 & -\frac{7}{5} & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} \end{align*}

2. Write the solution set in terms of basic variables.

   \begin{equation*} \begin{aligned} x_1 + \frac{1}{5} x_3 & = 0 \\ x_2 - \frac{7}{5} x_3 & = 0 \end{aligned} \quad \iff \quad \begin{aligned} x_1 & = -\frac{1}{5} x_3 \\ x_2 & = \frac{7}{5} x_3 \end{aligned} \end{equation*}

3. Rewrite the solution set in the parametric form.

   \begin{equation*} \vec{x} = \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} -\frac{1}{5} x_3 \\ \frac{7}{5} x_3 \\ x_3 \end{pmatrix} = x_3 \begin{pmatrix} -\frac{1}{5} \\ \frac{7}{5} \\ 1 \end{pmatrix} = x_3 \begin{pmatrix} -1 \\ 7 \\ 5 \end{pmatrix}. \end{equation*}

   Note. This is a line in \(\mathbb{R}^3\).

Solve \(A \vec{x} = \vec{b}\), given

1. Write the augmented matrix and row-reduce it.

   \begin{align*} \begin{pmatrix} \vphantom{\Big(} A & \vec{b} \, \end{pmatrix} & = \begin{pmatrix} 1 & -2 & 3 & 3 \\ 2 & 1 & -1 & 9 \\ -3 & -4 & 5 & -15 \end{pmatrix} \\[2ex] \operatorname{rref} \begin{pmatrix} \vphantom{\Big(} A & \vec{b} \, \end{pmatrix} & = \begin{pmatrix} 1 & 0 & \frac{1}{5} & \frac{21}{5} \\ 0 & 1 & -\frac{7}{5} & \frac{3}{5} \\ 0 & 0 & 0 & 0 \end{pmatrix} \end{align*}

2. Write the solution set in terms of basic variables.

   \begin{equation*} \begin{aligned} x_1 + \frac{1}{5} x_3 & = \frac{21}{5} \\ x_2 - \frac{7}{5} x_3 & = \frac{3}{5} \end{aligned} \quad \iff \quad \begin{aligned} x_1 & = -\frac{1}{5} x_3 + \frac{21}{5} \\ x_2 & = \frac{7}{5} x_3 + \frac{3}{5} \end{aligned} \end{equation*}

3. Rewrite the solution set in the parametric form.

   \begin{equation*} \vec{x} = \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} -\frac{1}{5} x_3 + \frac{21}{5} \\ \frac{7}{5} x_3 + \frac{3}{5} \\ x_3 \end{pmatrix} = x_3 \begin{pmatrix} -\frac{1}{5} \\ \frac{7}{5} \\ 1 \end{pmatrix} + \begin{pmatrix} \frac{25}{5} \\ \frac{3}{5} \\ 0 \end{pmatrix} = x_3 \begin{pmatrix} -1 \\ 7 \\ 5 \end{pmatrix} + \begin{pmatrix} 25 \\ 3 \\ 0 \end{pmatrix} \end{equation*}

Solve \(A \vec{x} = \vec{b}\), given

1. Write the augmented matrix and row-reduce it.

   \begin{align*} \begin{pmatrix} \vphantom{\Big(} A & \vec{b} \, \end{pmatrix} & = \begin{pmatrix} 1 & -2 & 3 & 3 \\ 2 & 1 & -1 & 9 \\ -3 & -4 & 5 & -8 \end{pmatrix} \\[2ex] \operatorname{rref} \begin{pmatrix} \vphantom{\Big(} A & \vec{b} \, \end{pmatrix} & = \begin{pmatrix} 1 & 0 & \frac{1}{5} & 0 \\ 0 & 1 & -\frac{7}{5} & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \end{align*}

   The last column is the pivot column, so the system is inconsistent.

The column vectors of the identity matrix \(I_n\) are

the members of the standard basis \(\{ e_1, \ldots, e_n \}\).

The identity matrix is

the multiplicative identity of matrix multiplication.

The determinant of the identity matrix is one,

The simplest real spaces are

• the real line \(\mathbb{R}\)
• the real plane \(\mathbb{R}^2\)
• the real three-dimensional space \(\mathbb{R}^3\)

in one, two, and three dimensions, respectively.

• \(y = x\) is a subspace of \(\mathbb{R}^2\).
• \(y = x^2\) is a subset but not a subspace of \(\mathbb{R}^2\).

The basis of the zero subspace is the empty set and its dimension is zero.

The real line contains the following subspaces exactly:

The real plane contains the following subspaces exactly:

The real three-dimensional space contains the following subspaces exactly:

The “minimal” set of vectors that spans a subspace.

The augmented matrix

aids solving vector equations and matrix equations

with row reduction.

Per the

Uniqueness of the reduced echelon form

theorem, every matrix is row equivalent to

exactly one matrix in reduced row echelon form.

Performing elementary row operations on the augmented matrix

never changes the solution set

of the associated linear system.

All elementary row operations are reversible.

Solve the linear system

Phase 1. Towards the row echelon form.

1. Write an augmented matrix.

   \begin{equation*} M = \begin{pmatrix} 1 & 2 & 1 & 1 \\ 3 & 1 & 4 & 0 \\ 2 & 2 & 3 & 2 \end{pmatrix}. \end{equation*}

2. Move all zero rows.

   Nothing to do.

3. Enumerating rows, top to bottom:

   For \(M_1\):

   1. Scale the selected row.

      Nothing to do.

   2. Replace the rows below the selected row.

      \(M_2 \gets M_2 + kM_1\) with \(k = -3\), so

      \begin{align*} M & \gets \begin{pmatrix} 1 & 2 & 1 & 1 \\ 3 + (-3) \cdot 1 & 1 + (-3) \cdot 2 & 4 + (-3) \cdot 1 & 0 + (-3) \cdot 1 \\ 2 & 2 & 3 & 2 \end{pmatrix} \\[2ex] & = \begin{pmatrix} 1 & 2 & 1 & 1 \\ 0 & -5 & 1 & -3 \\ 2 & 2 & 3 & 2 \end{pmatrix}. \end{align*}

      \(M_3 \gets M_3 + kM_1\) with \(k = -2\), so

      \begin{align*} M & \gets \begin{pmatrix} 1 & 2 & 1 & 1 \\ 0 & -5 & 1 & -3 \\ 2 + (-2) \cdot 1 & 2 + (-2) \cdot 2 & 3 + (-2) \cdot 1 & 2 + (-2) \cdot 1 \end{pmatrix} \\[2ex] & = \begin{pmatrix} 1 & 2 & 1 & 1 \\ 0 & -5 & 1 & -3 \\ 0 & -2 & 1 & 0 \end{pmatrix}. \end{align*}

   For \(M_2\):

   1. Scale the selected row.

      \(M_2 \gets kM_2\) with \(k = -\frac{1}{5}\), so

      \begin{align*} M & \gets \begin{pmatrix} 1 & 2 & 1 & 1 \\ -\frac{1}{5} \cdot 0 & -\frac{1}{5} \cdot (-5) & -\frac{1}{5} \cdot 1 & -\frac{1}{5} \cdot (-3) \\ 0 & -2 & 1 & 0 \end{pmatrix} \\[2ex] & = \begin{pmatrix} 1 & 2 & 1 & 1 \\ 0 & 1 & -\frac{1}{5} & \frac{3}{5} \\ 0 & -2 & 1 & 0 \end{pmatrix}. \end{align*}

   2. Replace the rows below the selected row.

      \(M_3 \gets M_3 + kM_2\) with \(k = 2\), so

      \begin{align*} M & \gets \begin{pmatrix} 1 & 2 & 1 & 1 \\ 0 & 1 & -\frac{1}{5} & \frac{3}{5} \\ 0 + 2 \cdot 0 & -2 + 2 \cdot 1 & 1 + 2 \cdot (-\frac{1}{5}) & 0 + 2 \cdot \frac{3}{5} \end{pmatrix} \\[2ex] & = \begin{pmatrix} 1 & 2 & 1 & 1 \\ 0 & 1 & -\frac{1}{5} & \frac{3}{5} \\ 0 & 0 & \frac{3}{5} & \frac{6}{5} \end{pmatrix}. \end{align*}

   For \(M_3\):

   1. Scale the selected row.

      \(M_3 \gets kM_3\) with \(k = \frac{5}{3}\), so

      \begin{align*} M & \gets \begin{pmatrix} 1 & 2 & 1 & 1 \\ 0 & 1 & -\frac{1}{5} & \frac{3}{5} \\ \frac{5}{3} \cdot 0 & \frac{5}{3} \cdot 0 & \frac{5}{3} \cdot \frac{3}{5} & \frac{5}{3} \cdot \frac{6}{5} \end{pmatrix} \\[2ex] & = \begin{pmatrix} 1 & 2 & 1 & 1 \\ 0 & 1 & -\frac{1}{5} & \frac{3}{5} \\ 0 & 0 & 1 & 2 \end{pmatrix}. \end{align*}

   2. Replace the rows below the selected row.

      Nothing to do.

Phase 2.

4. Is the last column is a pivot column?

   The system is consistent.

5. Enumerating rows, bottom to top:

   For \(M_3\):

   1. Replace the rows above.

      \(M_2 \gets M_2 + kM_3\) using \(k = \frac{1}{5}\), so

      \begin{align*} M & \gets \begin{pmatrix} 1 & 2 & 1 & 1 \\ 0 + \frac{1}{5} \cdot 0 & 1 + \frac{1}{5} \cdot 0 & -\frac{1}{5} + \frac{1}{5} \cdot 1 & \frac{3}{5} + \frac{1}{5} \cdot 2 \\ 0 & 0 & 1 & 2 \end{pmatrix} \\[2ex] & = \begin{pmatrix} 1 & 2 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 2 \end{pmatrix}. \end{align*}

      \(M_1 \gets M_1 + kM_3\) using \(k = -1\), so

      \begin{align*} M & \gets \begin{pmatrix} 1 + (-1) \cdot 0 & 2 + (-1) \cdot 0 & 1 + (-1) \cdot 1 & 1 + (-1) \cdot 2 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 2 \end{pmatrix} \\ & = \begin{pmatrix} 1 & 2 & 0 & -1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 2 \end{pmatrix}. \end{align*}

   For \(M_2\):

   1. Replace the rows above.

   \(M_1 \gets M_1 + kM_2\) using \(k = -2\), so

   \begin{align*} M & \gets \begin{pmatrix} 1 + (-2) \cdot 0 & 2 + (-2) \cdot 1 & 0 + (-2) \cdot 0 & -1 + (-2) \cdot 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 2 \end{pmatrix} \\ & = \begin{pmatrix} 1 & 0 & 0 & -3 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 2 \end{pmatrix}. \end{align*}

   For \(M_1\):

   1. Replace the rows above.

      Nothing to do.

The only solution is \((x, y, z) = (-3, 1, 2)\).

Probability theory is built on the probability axioms.

Commonly denoted by

• \(\Omega\) read “big omega”
• \(S\).

The sample space \(\Omega\) of the event of

getting two heads or two tails

in an experiment involving a sequence of

two flips of a fair coin

is the set

One possible outcome of the event of

getting two heads or two tails

in an experiment involving a sequence of

two flips of a fair coin

is the ordered pair

An event is commonly denoted with

a capital letter from the beginning of the alphabet,

such as \(A, B, C, D, E\).

The event \(A\) of

getting two heads or two tails

in an experiment involving a sequence of

two flips of a fair coin

is the set

Commonly denoted with

• uppercase calligraphic Roman F \(\mathcal{F}\)
• uppercase Greek sigma \(\Sigma\).

Probability is denoted \(\Pr(A)\) or \(\operatorname{P}(A)\) or \(P(A)\) and read “probability of \(A\)”.

The codomain of probability is the real line \(\mathbb{R}\) and

its image is the real interval \([0, 1]\),

per the probability axioms.

The probability of

getting two heads or two tails

in an experiment involving a sequence of

two flips of a fair coin

is the value

with the event and the sample space

respectively,

Introduced by Russian mathematician Andrey Kolmogorov in the 1930s.

Commonly normalized or standardized.

The set whose parameters are estimated with statistics.

• the population mean
• the population standard deviation

Often denoted \(n\) for the “number” of members.

Often denoted \(X\) or \(x\).

Commonly denoted

• \(n\) for the “number” of members
• \(|X|\) given the sample \(X\) using set cardinality notation

• the sample mean
• the sample standard deviation

Central tendency:

• robust: sample median
• not robust: sample mean

Dispersion:

• robust: interquartile range
• not robust: sample standard deviation

Represents a kind of “typical value”.

• the sample mean
• the population median

Commonly denoted \(\mu\) and read “mew”.

Commonly estimated by the sample mean.

Modeled after the expected value in probability theory.

Denoted \(\bar{x}\) and read “\(x\) bar”.

A common estimator of the population mean.

The sample mean is not a robust statistic.

Modeled after the expected value in probability theory.

Repeatedly increase the sample size from \(n = 1\) to the population size:

set.seed(0)

N <- 1000      # the population size
Z <- 0 : N     # the population
mu <- mean(Z)  # the population mean
D <- rep(0, N) # absolute deviations

for(n in 1 : N)
  D[n] <- mean(sample(Z, n)) - mu

plot(
  D,
  main = "A demonstration of the law of large numbers.",
  type = "l",
  lwd = 2,
  xlab = "Sample size",
  ylab = "Absolute deviation"
)
abline(h = 0)

Drawing multiple samples from a population

makes the statistic into a random variable.

Pertaining to the central limit theorem,

the sampling distribution of the sample mean.

Commonly denoted \(\mu_{\bar{X}}\) read “mew sub bar \(X\)”.

Significant due to the central limit theorem.

The most profound concept in statistics.

The sample mean of \(N = 10^3\) samples taken from a uniformly distributed population should distribute normally.

set.seed(0)

N <- 10^4
Z <- rep(1, N)

for(i in 1 : N) {
  X <- runif(10^3)
  Z[i] <- mean(X)
}

Y <- density(Z)

plot(
  main = "A demonstration of the central limit theorem.",
  Y,
  type = "l",
  lwd = 2,
  xlab = "Sample mean",
  ylab = "Density"
)
abline(v = 0.5)

• the cumulative frequency
• the relative frequency

Relative frequency estimates probability and

connects descriptive statistics to probability theory

under frequentist interpretation.

Ethically licensed resources for computer science (alphabetically):

Typically represented as a

set of inputs to which the answer is “yes”,

such as in SAT.

Recursion consists of

• one or more base cases
• one or more recursive cases.

The first case in

The second case in

The merge sort algorithm is beautiful.

The merge sort algorithm

• divides its input into two halves per recursive call
• enumerates its input during the merge step

which gives

and so

and so

The steps of generic search on \(G = (V, E)\), given

• a starting vertex \(v_1 \in V\) and
• a goal predicate \(g : (v_1, \ldots, v_k) \to \mathbb{B}\)

are:

1. start with the frontier \(F = \{(v_1)\}\) and seen vertices \(S = \{v_1\}\)
2. if \(|F| = 0\), return empty-handed (\(\bot\))
3. remove some path \(p = (v_1, \ldots, v_k)\) from \(F\)
4. when the goal predicate \(g(p)\) is true ¹⁴, return \(p\) as the solution
5. select \(N = \{(v_1, v_2, \ldots, v_k, v^*) : v^* \notin S \land (v_k, v^*) \in E\}\)
6. for each \(n \in N\), insert \(n\) to \(F\)
7. for each \((v_1, v_2, \ldots, v_k, v^*) \in N\), insert \(v^*\) to \(S\)
8. go to step 2.

The synonyms for the generic search include:

A clean-room implementation ¹⁵ of generic search in Elisp:

(defvar my-graph-search-debug nil
  "Print debug information during graphs search.")

(defun my-graph-search (frontier neighbors goalp add &optional seen)
  "Search a directed graph.

FRONTIER is a list of paths to be searched, NEIGHBORS is a function that
takes a path and returns all adjacent vertices to its `car', GOALP is a
function that takes a path and returns non-nil if the path reached the
goal, and ADD is a function that takes a frontier and a list of paths
and adds the paths to the frontier.

SEEN is a set of visited vertices, used internally.

In all paths, the most recently seen vertex is the first element."
  (if (not frontier) nil
    (let ((path (car frontier))
          (seen (or seen
                    (let ((seen (make-hash-table :test #'equal)))
                      (mapc (lambda (vertex) (puthash vertex t seen))
                            (mapcan #'identity frontier))
                      seen))))
      (when my-graph-search-debug
        (princ (format "Search: %s\n" path)))
      (if (funcall goalp path) path
        (my-graph-search
         (funcall add
                  (cdr frontier)
                  (mapcan (lambda (neighbor)
                            (if (gethash neighbor seen) nil
                              (puthash neighbor t seen)
                              (list (copy-sequence (cons neighbor path)))))
                          (funcall neighbors path)))
         neighbors goalp add seen)))))

The space and time complexity of DFS is

\[\mathcal{O}(bm) \qand \mathcal{O}(b^m)\]

respectively ¹⁷,

DFS is implemented as

a generic search with a LIFO queue for the frontier.

A clean-room implementation ¹⁸ of DFS in Elisp:

(defun my-depth-first-graph-search (frontier neighbors goalp)
  "Perform depth-first search (DFS) on a graph.

All arguments are like those for `my-graph-search', which see."
  (let ((lifo (lambda (frontier paths) (nconc paths frontier))))
    (my-graph-search frontier neighbors goalp lifo)))

(defalias 'my-dfs-graph-search #'my-depth-first-graph-search)

Test.

(let ((graph '((a b c d)
               (b a e i)
               (c a f)
               (d a g l)
               (e b i j)
               (f c)
               (g d k l)
               (i b e)
               (j e)
               (k g)
               (l d g)))
      (my-graph-search-debug t))
  (princ (format "Solution: %s\n"
                 (my-bfs-graph-search
                  '((a))
                  (lambda (path) (alist-get (car path) graph))
                  (lambda (path) (eq (car path) 'f))))))

Search: (a)
Search: (b a)
Search: (c a)
Search: (d a)
Search: (e b a)
Search: (i b a)
Search: (f c a)
Solution: (f c a)

Depth-first search is analogous to the existential quantifier ¹⁹.

The space and time complexity of BFS is

\[\mathcal{O}(b^{d + 1}),\]

Statements.

BFS runs in exponential time \(\mathcal{O}(b^{d + 1})\), where

• \(b\) is the branching factor and
• \(d\) is the depth of the shallowest solution.

BFS runs in linear time \(\mathcal{O}(|V| + |E|)\), where

• \(|V|\) is the cardinality of the vertex set and
• \(|E|\) is the cardinality of the edge set.

Objective.

Prove the above statements equivalent for any complete graph \(K_n\).

Proof.

Lemma 1. Given \(|V| = n\), prove \(\mathcal{O}(|V| + |E|) = \mathcal{O}(n^2)\).

For any \(K_n\),

and so

Lemma 2. Given \(|V| = n\), prove \(\mathcal{O}(b^{d + 1}) = \mathcal{O}(n^2)\).

In any \(K_n\), all vertices are of degree \(n - 1\) and adjacent, so

\[b = n - 1 \qand d = 1,\]

respectively, which gives

Given Lemma 1 and Lemma 2,

Breadth-first search is analogous to the universal quantifier ²¹.

BFS is implemented as

a generic search with a FIFO queue for the frontier.

A clean-room implementation ²² of BFS in Elisp:

(defun my-breadth-first-graph-search (frontier neighbors goalp)
  "Perform depth-first search (DFS) on a graph.

All arguments are like those for `my-graph-search', which see."
  (let ((fifo #'nconc))
    (my-graph-search frontier neighbors goalp fifo)))

(defalias 'my-bfs-graph-search #'my-breadth-first-graph-search)

Test.

(let ((graph '((a b c d)
               (b a e i)
               (c a f)
               (d a g l)
               (e b i j)
               (f c)
               (g d k l)
               (i b e)
               (j e)
               (k g)
               (l d g)))
      (my-graph-search-debug t))
  (princ (format "Solution: %s\n"
                 (my-dfs-graph-search
                  '((a))
                  (lambda (path) (alist-get (car path) graph))
                  (lambda (path) (eq (car path) 'f))))))

Search: (a)
Search: (b a)
Search: (e b a)
Search: (j e b a)
Search: (i b a)
Search: (c a)
Search: (f c a)
Solution: (f c a)

Using pure functions aids

• memoization
• parallelization
• composition
• testability

Pure functions are equivalent to mathematical function.

# Memoized results.
ys = {}


def f(n):
    """Return the factorial."""

    # Check preconditions.
    assert int(n) == n, "Factorial of non-integral values is undefined"
    assert n >= 0, "Factorial of negative integers is undefined"

    # Return early in the base case.
    if n == 1:
        return 1

    # Return early with a memoized result.
    if n in ys:
        return n

    # Compute the result.
    y = n * f(n - 1)

    # Memoize the result.
    ys[n] = y

    # Return the result.
    return y


# Try it.
f(5)

120

from functools import lru_cache


@lru_cache(maxsize=None)
def f(n):
    """Return the factorial."""

    # Check preconditions.
    assert int(n) == n, "Factorial of non-integral values is undefined"
    assert n >= 0, "Factorial of negative integers is undefined"

    # Compute the result.
    return n * f(n - 1) if n else 1


# Try it.
f(5)

120

The asymptotic complexity of

in Big O is derived by

Notable complexity classes include

P, NP, NP-hard, and NP-complete.

The hardest problems in NP.

To prove a problem \(L\) is NP-complete,

reduce a known NP-complete problem to \(L\).

in polynomial time.

NP-completeness was discovered by [16]²⁴ who

proved that every problem in NP reduces to SAT,

and applied by [17] who showed it holds to

reduced 21 important combinatorial problems,

both receiving Turing Awards.

NP-hard is not a subset of NP, so its problems are

• not necessarily decision problems
• not necessarily verifiable in polynomial time.

After the discovery of NP-complete, it became apparent that

some problems are just as hard but are not decision problems

such as

• “Does a tour of given maximum length exists?” (in NP and NP-complete)
• “What is the shortest tour?” (not in NP, but just as hard or harder)

which gave birth to NP-hard.

… 3SAT to 3COL, showing NP-completeness of the latter.

Perform a polynomial-time reduction using the graph below.

1. Add three interconnected vertices, colored 1, 2, and 3.
2. For each variable, add two uncolored vertices connected to 2.
3. For each clause, add one Or gadget connected to:
   • the relevant variable vertices and
   • the vertex colored 1.

Given

connect the graph

For example,

reduces to the graph

… that Or gadget implements the 3-way disjunction

The Or gadget:

No coloring exists when \(\ell_1 = \ell_2 = \ell_3 = 0\):