Martingale differences and Hoeffding's inequality

It is required to pack a knapsack to maximum benefit. Suppose you have $n$ objects, the $i$ th object having volume $V_{i}$ and worth $W_{i}$, where $V_{1}, V_{2}, \ldots , V_{n}, W_{1}, W_{2}, \ldots , W_{n}$ are independent non-negative random variables with finite means, and $W_{i} \leq M$ for all $i$ and some fixed $M$. Your knapsack has volume $c$, and you wish to maximize the total worth of the objects packed in it. That is, you wish to find the vector $z_{1}, z_{2}, \ldots , z_{n}$ of 0 's and 1 's such that $\sum_{1}^{n} z_{i} V_{i} \leq c$ and which maximizes $\sum_{1}^{n} z_{i} W_{i}$. Let $Z$ be the maximal possible worth of the knapsack's contents, and show that $\mathbb {P}\left(|Z-\mathbb {E}\left[Z\right]| \geq x\right) \leq 2 \exp \left\{ -x^{2} /\left(2 n M^{2}\right)\right\}$ for $x > 0$.

Given $n$ vertices $v_{1}, v_{2}, \ldots , v_{n}$, for each $1 \leq i < j \leq n$ we place an edge between $v_{i}$ and $v_{j}$ with probability $p$; different pairs are joined independently of each other. We call $v_{i}$ and $v_{j}$ neighbours if they are joined by an edge. The chromatic number $\chi$ of the ensuing graph is the minimal number of pencils of different colours which are required in order that each vertex may be coloured differently from each of its neighbours. Show that $\mathbb {P}\left(|\chi -\mathbb {E}\left[\chi \right]| \geq x\right) \leq 2 \exp \left\{ -\frac{1}{2} x^{2} / n\right\}$ for $x > 0$.

Let $(M, \mathcal{F})$ be a martingale with $M_{0} = 0$, having differences $D_{r} = M_{r}-M_{r-1}$. The process given by $Q_{n} = \sum_{r = 1}^{n} D_{r}^{2}$ is called the optional quadratic variation of $M$, while $V_{n} = \sum_{r = 1}^{n} \mathbb {E}\left[D_{r}^{2} \mid \mathcal{F}_{r-1}\right]$ is called the predictable quadratic variation of $M$. Show that $X_{n} = M_{n}^{2}-Q_{n}$ and $Y_{n} = M_{n}^{2}-V_{n}$ define martingales with respect to $\mathcal{F}$.