1. 
    1. It takes $|n|$ steps to walk there.
    2. 
        1. Let us choose n=9. Then OPT=9. We see that $\text{ALG}_1=1+2+3+4+6+8+12+16+24=76$, so the ratio becomes $\frac{52}{9}=8\frac{4}{9}$. This is also a lower bound of the connective constant
        2. Let us choos n=-9. Then OPT=9. We see that $\text{ALG}_1=1+2+3+4+6+8+12+16+24+32=108$, so the ratio becomes $\frac{108}{9}=12$. This is also a lower bound of the connective constant
        3. (b) of course
        4. For a given number $n$ let $k$ be the smallest natural number such that such that $2^k\geq N$. We see that if $n$ is positive that $\text{ALG}_1 = |n|+\sum_{j=0}^{k-1}4\cdot 2^{j}$. If $n$ is negative we get $\text{ALG}_1 = |n|+2\cdot 2^k+\sum_{j=0}^{k-1}4\cdot 2^{j}$. Because $\text{ALG}_1$ is bigger when negative and $\text{OPT}$ stays the same, we will only need to consider the negative case. We see that our competitive constant is $$\frac{|n|+2\cdot 2^k+\sum_{j=0}^{k-1}4\cdot 2^{j}}{|n|}=\frac{|n|+2\cdot 2^k+4\cdot (2^k-1)}{|n|}\leq 1+\frac{2\cdot 2^k+4\cdot 2^k}{2^{k-1}} = 13.$$ We know have an upper bound for the competitive ratio. We also need to show that the competitive ratio can not be lower than this. Let us look at the case that $n=-(2^{k-1}+1)$ for a certain $k$. We now see that $$\frac{\text{ALG}_1}{\text{OPT}} = 1+\frac{2\cdot 2^k+4\cdot (2^k-1)}{2^{k-1}+1}=1+4-\frac{4}{2^{k-1}+1}+8-\frac{12}{2^{k-1}+1}.$$ We see that if we take the limit of $k\to \infty$, that it goes to 13.
    3. Better, because it reaches a greater range with less steps
        2. If $n\in (2^{2k},2^{2k+2}]$ for some $k\geq 0$, we see that $$\text{ALG}_2=n+\sum_{i=0}^{2k+1}2\cdot 2^i= n+2\cdot 2^{2k+2}-2.$$If $n\in [-2^{2k+3},-2^{2k+1})$ for some $k\geq 0$, we see that$$\text{ALG}_2 = |n| + \sum_{i=0}^{2k+2} 2\cdot 2^i=|n|+2\cdot 2^{2k+3}-2$$ We see in the first case that $$\frac{\text{ALG}_2}{\text{OPT}} = \frac{n+2\cdot 2^{2k+2}-2}{n}\leq 1+2\cdot \frac{2^{2k+2}}{n}\leq 1+2\cdot \frac{2^{k+2}}{2^k} = 9$$in the second case we see$$\frac{\text{ALG}_2}{\text{OPT}} = \frac{n+2\cdot 2^{2k+3}-2}{n}\leq 1+2\cdot \frac{2^{2k+3}}{n}\leq 1+2\cdot \frac{2^{k+3}}{2^{k+1}} = 9.$$ No we  we need to show it is tight. Let us look at the positive case and $n=2^{2k}+1$. We see that$$\frac{\text{ALG}_2}{\text{OPT}} = \frac{2^{2k}+1+2\cdot 2^{2k+2}-2}{2^{2k}+1}=1+\frac{2\cdot 2^{2k+2}+8-2}{2^{2k}+1}=9-\frac{2}{2^{2k}+1}\stackrel{k\to \infty}{\to}9$$
2. 
    1. We learned earlier that the competitive constant of this algorithm is two. I think what we are supposed to do is prove that $$\text{cost}\leq 2\cdot (B^i-B^{i-1}).$$Let us first look at the case that $i=1$. This is phase zero and starts when the cost is $1$ and ends when the cost is $B-1$. In this time we are only renting, so the cost is a maximum of $B-1$. When $i=2$ we see that the cost becomes $B$, hence we see $$\text{cost}=2B-1\leq B^{i-1}(2B-1)$$
3. 
    1. Let $i$ and $j$ be the consecutive bins and $B_i$ and $B_j$ there contents. By looking at the algorithm we know that $j$ being used implies that the items in $j$ do not all fit in $i$. This means that $B_i+B_j >1$, because otherwise bin $i$ would never have been closed.
    2. Let $\{1,\dots,n\}$ be the set of bins used and $\{B_i\}_{i=1}^n$ be the size of their contents. The ind We know that $$\begin{align}2\cdot \text{OPT}&\geq 2\cdot \text{Total size of items}\\&=\sum_{i=1}^n B_i + \sum_{i=1}^n B_i\\&=B_1+\sum_{i=2}^n B_i + \sum_{i=1}^{n-1} B_i+B_n\\&=B_1+B_n+\sum_{i=1}^{n-1} B_{i+1}+B_i\\&\geq B_1+B_n + n-1\\&\geq n-1.\end{align}$$Hence $n\leq 2\cdot \text{OPT}+1$ 
4.  For some large $k$ and small $\varepsilon$, consider the azdversarial instance $R$ consist of $28k$ size-$(\frac{1}{28}-4\varepsilon)$ items, $28k$ size-$(\frac{1}{14}+\varepsilon)$ items, $28k$ size-$(\frac{1}{7}+\varepsilon)$ items, $28k$ size-$(\frac{1}{4}+\varepsilon)$ items and $28k$ size-$(\frac{1}{2}+\varepsilon)$. The items can be packed such that each bin consists of one item from each of the 5 groups of items and consumes $28k$ bins. Therefore the optimal cost is at most $28k$. First will pack the first group of items in $28$, the second in 13, the third in 6, the fourth in $3$ and the fifth in $1$. In total it uses$$k+2\frac{2}{13}k+4\frac{2}{3}k+9\frac{1}{3}k+28k=45\frac{2}{13}k.$$Therefore it is $$\frac{45\frac{2}{13}}{28} \equiv 1.6126373626373627$$ which is worse
5. 
    1. If job $J_k$ is assigned to machine $i$ the sum of loads of machine $i$ will be greater or equal to $\ell_k$, hence the maximum total load among the machines will be greater or equal to $\ell_k$ .
    2. We see that $$\begin{aligned}\text{cost of assignment}&=\text{max total load}\\&=\frac{\sum_{i=1}^m \text{max total load}}{m}\\&\geq \frac{\sum_{i=1}^m\text{Load of machine }i}{m}=\frac{\sum_{j=1}^n \ell_j}{m}\end{aligned}.$$
    3. Let $M_i$ be the highest load machine and assume it has load $\ell_k+s$ where $s\geq 0$ and $J_k$ is the last job assigned to the machine.  $$\begin{aligned}\text{ALG} &= \ell_k+s \leq \ell_k+\frac{\sum_{j\neq k}\ell_j}{m}&&=\ell_k-\frac{\ell_k}{m}+\frac{\sum_{j=1}^n\ell_j}{m}\\&=\ell_k\left(\frac{m-1}{m}\right)+\frac{\sum_{j=1}^n\ell_j}{m}&&\leq\text{OPT}\frac{m-1}{m}+\text{OPT}\\&=(2-\frac{1}{m})\text{OPT}.\end{aligned}$$
    4.