Directions: Number of points for each problem is given is square brackets. KT below in every HW after that means

our main textbook Kleinberg, Tardos $($KT$).$ AB means supplemental textbook Arora, Barak.

$[2]$ Give a Turing machine $M$ such that

i$.$ its input alphabet is $0,1$ ;

ii$.,M$ accepts an input string $s$ if and only if $s$ contains twice as many $0$ s as it contains $1s.$

What is the runtime of your TM$?$

You can define $M$ either by the table of its transition function, or by a labeled graph, or by giving precise

description of its operation in plain English.

$[2]$ Take the following list of functions and arrange them in the order of growth rate:

$n^{2\mathrm{.}5},\sqrt[\phantom{2}]{2n},n+10,{10}^n,{100}^n,n^{2logn}$

$[2]$ Given nondecreasing functions $f(n)$ and $g(n)$ such that $f(n)=O(g(n))$ For each of the following

decide whether it is true or false:

i$.,lo{g}_{2}f(n)=O(lo{g}_{2}g(n))$

ii$.,2^{f(n)}=O(2^{g(n)})$

iii. $,f^2(n)=O(g^2(n))$