\documentclass[12pt]{article}%
\usepackage{rand}%
\usepackage{rand_extra}

\newcommand{\JL}{\textsf{JL}\xspace}%

\HomeworkStart%
{5} % Homework number
{14} % Week of semester submitted
{1.0} % Version

\SaveIndent%
\HWInstructions{Submission guidelines same as previous homework.}

\medskip%
\hrule %
\medskip

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 


\SaveIndent


\begin{questions}[start=13]
    \item \HWProblemHead{100}{Solving $k$SAT.}%

    \begin{questions}
        \item Using Stirling's formula, give a tight estimate to
        $\binom{ k m}{m}$.

        \item Consider the random walk on the integers that starts at
        $j$, and with probability $1/k$ it goes left (i.e., decreases
        by one), and with probability $(k-1)/k$ it goes right (i.e.,
        increases by $1$). The random walk stops once it arrives to
        $0$.  Provide a lower bound to the probability that after $2j$
        steps (or $3j$ steps, if this is easier or better), the random
        walk is at zero.

        \item In the spirit of the randomized algorithm for $2$SAT,
        provide an algorithm for solving a $k$SAT.  Here, you are
        given a formula with $n$ variables, and every clause has
        exactly $k$ variables in it.

        The algorithm works as follows - it starts with a random
        assignment, and then performs a random walk for $2n$ (or $3n$)
        steps on the random assignment (i.e., find an unsatisfied
        clause, randomly flip one of its variables, repeat). If it
        found a satisfying assignment it stops. Otherwise, it restarts
        the walk.

        What is the expected running time of the algorithm?  (Assuming
        there is at least one satisfying assignment.) In particular,
        what is the running time for $k=3$. Why is this interesting?
    \end{questions}
    
    
    
    \item \HWProblemHead{100}{Total walk.}%
    
    Consider an urn $U$ with $n$ balls, where $\alpha n$ of them are
    red, and $(1-\alpha) n$ are blue. Assume $\alpha$ is a small
    constant (say $0.01$). Consider the following process: In the
    $i$\th step, you randomly pick a set $S_i$ of three balls from the
    urn. Let $C_i$ be the majority of the colors of balls in
    $S_i$. You next put the balls of $S_i$ back into $U$, randomly
    throw away a ball from $U$, and add to $U$ a new ball of color
    $C_i$. The game is repeated till all the balls are of the same
    color.

    Give an upper and lower bounds on the number of rounds you have to
    play this game till all balls have the same color. (The bounds
    should be reasonably tight.)

    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item \HWProblemHead{100}{Random walks.}

    \begin{questions}
        \item \points{50} Show that the expected time for a random walk to visit
        every vertex of a strongly connected directed graph is not
        bounded above by any polynomial function of n. the number of
        vertices. In other words. construct a directed graph that is
        strongly connected and where the expected cover time is super-
        polynomial.

        \item \points{50} (Harder.) Consider a graph $\G$ over
        $\IRX{n}=\{1,\ldots, n\}$. A graph $\G$ is \emphi{straight}
        for $i, j \in \IRX{n}$, with $i < j$, if there is a path
        $i_1 i_2 \ldots i_k$ in $\G$ between $i$ and $j$, such that
        $i = i_1 < i_2 < \ldots< i_k = j$, and
        $i_t i_{t+1} \in \EGX{\G}$, for all $t$.

        Prove, that there exists a graph $\G$ over $\IRX{n}$, such
        that for all sets $D \subseteq \IRX{n}$ of $n/4$ vertices,
        there exists a set $Y \subseteq \IRX{n} \setminus D$ of size
        $\geq n/2$, such that $\G - D$ (i.e., the graph $\G$ after we
        delete all the vertices of $D$ from it) is straight for all
        $i,j \in Y$.

        For credit, your graph $\G$ should have as few edges as
        possible.

        (Hint: Use constant degree expanders.)
    \end{questions}
\end{questions}

\end{document}


% --------------------------------------------------------
% 
% homework 4 - end of file
% --------------------------------------------------------
