1. Sequential composition of multiple queries over the same database. Informally, if you make k independent epsilon differentially private queries over a dataset, in total, you have spent (k \times epsilon) privacy budget.

Let D denote a dataset consisting of multiple records.
Let M_1, M_2, ... , M_k denote k *independent* epsilon-differentially private mechanisms performed on D.
(Independence means that their random coins are independent.)
Let M := M_1 \times M_2 \times ... \times M_k.
In other words, if M_1, M_2, ... M_k give answers o_1, o_2, ..., o_k respectively, the joint mechanism M would give an answer o := (o_1, o_2, ... o_k).
Show that M satisfies (k \times epsilon) differential privacy.

2. Parallel composition or partitioning. Informally, if you make k independent epsilon differentially private queries over k disjoint subsets of a database, the total privacy budget consumption is epsilon.

Let D denote a dataset consisting of multiple records. D_1, D_2, ..., D_k represent a disjoint partitioning of the dataset.
Let M_1, M_2, ... , M_k denote k indepedent epsilon-differentially private mechanisms performed on subsets D_1, D_2, ..., D_k respectively.
Let M := M_1 \times M_2 \times ... \times M_k denote the "joint mechanism" on database D.
Show that M has epsilon differential privacy.