# Homework 1

Distributed on Monday, September 1.

Please submit your solutions until Monday, September 8, 11am:

Exercise #0 on paper at the beginning of class,

Exercise #1 via email to
ziegler@tclab.kaist.ac.kr.
###
Exercise #0: Big-Oh Calculus

- Recall the formal definitions, e.g. in
Wikipedia.
- Does
*n*^{log(n)} grow polynomially or exponentially?
- Simplify the following expression asymptotically:
*n*^{loglog(n)/log(n)}.
- Which choice of
*k*=*k*(*n*)
yields the least asymptotic growth of
*f*(*n,k*)=*n*^{k}+2^{n}/*k* ?

Justify/prove your answers!
###
Exercise #1: Becoming familiar with BF-Machines

The Theory of Computation knows many equivalent approaches:
Turing machines, μ-Recursion, λ-calculus,
`WHILE` programs etc.
We take the approach of BF-Machines (BrainFried, Brainf***),
a simple imperative Turing-complete programming system.
It supports 8 operations to control and access an
unbounded sequence of memory cells able to hold
one byte (numbers 0..255) each.
- I recommend the following resources:
- Write a BF program solving the following problem:

Input: one ascii character

Output: the ascii code of this character,
written in binary (least significant bit first: 0, 1, 01, 11, 001, 101, 011, 111, 0001 ...)

Hint: implement a binary counter in 8 consecutive memory cells,
then add decimal 48 (ascii code of "`0`") to each cell and output it.
- Write a BF program solving the following problem:

Input: a string of characters, terminated by a linefeed (ascii code 10)

Output: "`1`" if brackets "`(`" and "`)`"
in the input match; "`0`" otherwise.

Examples: input "`(a(b)ar(y!))(foo())`", output "`1`";
input "`)`", output "`0`".

Hint: implement a binary counter of unbounded length.

Comment your source codes!