# Homework 1

Distributed on Monday, September 1.
Exercise #0 on paper at the beginning of class,
Exercise #1 via email to ziegler@tclab.kaist.ac.kr.

### Exercise #0: Big-Oh Calculus

1. Recall the formal definitions, e.g. in Wikipedia.
2. Does nlog(n) grow polynomially or exponentially?
3. Simplify the following expression asymptotically: nloglog(n)/log(n).
4. Which choice of k=k(n) yields the least asymptotic growth of f(n,k)=nk+2n/k ?

### 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.
1. I recommend the following resources:
2. 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.
3. 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.