• Proofs, by induction especially
• CPSC 213 and 221 (kind of)
• Sets, graphs, discrete math, a little bit of linear algebra

• Assignments available on Piazza
• Assignment #1 should take an hour
• In total: 10 assignments
• Typically hard, include bonus questions
• Groups of 2 allowed
• LaTeX, Gradescope

Computational Problems. We want to understand things like: can I solve this problem? can I solve it fast?

1. ex. Given a list, sort it.
2. ex. Given an integer, find its prime factors.
3. ex. Given a polynomial, find its roots.

An alphabet is any finite non-empty set.

It is usually represented as $\Sigma$ or $\Gamma$. Often $\Sigma = \left\{ {0,1} \right\}$, or $\Sigma = \text{ASCII}$, or $\Sigma = \text{Unicode}$.

Computer science.

A string is a finite sequence of $0 +$ characters from an alphabet.

Programming.

A string is a UTF-8…

We often will talk about the empty string, so we have a special symbol for it: $\varepsilon$.

$\Sigma \ast$ is the set of all strings with alphabet $\Sigma$.

A language is any set $L$ (including infinite sets) such that $L \subset \Sigma \ast$. Even $L = \varnothing$ is okay.

A computational problem is a function mapping strings to strings.

Note that the definition of a computational problem does not specify how to produce the outputs from the inputs. There is no algorithm here.

A decision problem is a computational problem with a Boolean / binary / n-ary output.

We can usually tweak computational problems to become decision problems: e.g. given $\left( {x,y} \right)$, does $x$ have a prime factor that is $< y$?

Important Idea: decision problems are equivalent to languages.

$\left\{ {x \in \Sigma \ast :f(x) = \text{Yes}} \right\}$

reads as for all $X$ in $\Sigma \ast$ such that $f(x)$ is equal to “Yes”