CSE 525: Randomized Algorithms and Probability Spring 2026 HW1 Submit to gradescope

Instructions

• You should think about each problem by yourself for at least an hour before choosing to collaborate with others.

• You are allowed to collaborate with fellow students taking the class in solving the problems. But you must write your solution on your own.

• You are not allowed to search for answers or hints on the web. You are encouraged to contact the instructor or the TAs for a possible hint.

• You cannot collaborate on Extra credit problems

• Solutions typeset in LATEX are preferred.

• Feel free to use the Discussion Board or email the instructor or the TAs if you have any questions or would like any clarifications about the problems.

• Please upload your solutions to Gradescope.

 

In solving these assignments, feel free to use these approximations:

$$1-x\approx e^{-x},\sqrt{1-x}\approx 1-x/2,n!\approx {(n/e)}^n,{\left(\frac{n}{k}\right)}^k\le \left(\genfrac{}{}{0pt}{}{n}{k}\right)\le {\left(\frac{en}{k}\right)}^k$$

1. Let $ℱ$ be a family of subsets of $[n]:=\{1,2,\mathrm{\dots },n\}$, and suppose there are no $A,B\in ℱ$ satisfying $A\subset B$. Let $\sigma \in S_n$ be a uniformly random permutation of the elements of $[n]$ and consider the random variable

   $$ٓX=|\{i:\{\sigma (1),\mathrm{\dots },\sigma (i)\}\in ℱ\}|$$

   Use expectation of $X$ to show that $|ℱ|\le \left(\genfrac{}{}{0pt}{}{n}{\lfloor n/2\rfloor }\right)$.

2. Let $G=(V,E)$ be a bipartite graph with $n$ vertices and a list $S(v)$ of at least ${\log }_2(n+1)$ colors associated with each vertex $v\in V$. Design a randomized polynomial time algorithm that finds a proper coloring of (vertices) of $G$ assigning to each vertex $v$ a color from its list $S(v)$ with probability at least $1-1/n$.