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

  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 ?
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.
  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.
Comment your source codes!