CSE 525: Randomized Algorithms and Probability Spring 2026 HW6 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. Show that the cover time of any unweighted $d$-regular graph $G=(V,E)$ is $O(n^2\log n)$.

   Hint:What is the length of the shortest path between $u,v\in V$?

2. Let $A\in {ℝ}^{n\times n}$ be a random Gaussian matrix where every entry $A_{i,j}$ is distributed as a $𝒩(0,1)$ and $A_{i,j}=A_{j,i}$, and $A_{i,i}=0$ for all . Prove that ${\lambda }_{\max }(A)\le O(\sqrt{n})$ with high probability.