\documentclass[11pt]{article}
%\usepackage{pstricks,pst-node}
\usepackage{alltt,fullpage,graphics,color,epsfig,amsmath, amssymb}
\usepackage{hyperref}
\usepackage{boxedminipage}
\usepackage[dvipsnames]{xcolor}
\usepackage{accents}
%\newcommand{\edgee}[1]{\begin{math}\stackrel{#1}{\longrightarrow}\end{math}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\renewcommand{\r}[1]{ {\color{BrickRed} #1} }
\newcommand{\ub}[1]{\underbar{#1}}
\begin{document}
\setlength{\parskip}{.1 in}
\begin{center}
\LARGE
\textbf{CS 473: Algorithms, Spring 2018}
\\[0.5ex]
\textbf{HW 3 (due Wednesday, February 14th at 8pm)}
\end{center}
\noindent
This homework contains three problems. {\bf Read the instructions for
submitting homework on the course webpage}.
\noindent {\bf Collaboration Policy:} For this home work, each student
can work in a group with up to three members. Only one solution for
each group needs to be submitted. Follow the submission instructions
carefully.
\begin{enumerate}
%----------------------------------------------------------------------
\item You are part of a team that competes in a challenge to design a robot with the purpose of traversing a
rectangular grid of $M$ rows and $N$ columns. Your team positions the robot at $(1, 1)$, which is the top-left
cell. The goal is for the robot to reach $(M, N)$, i.e. the bottom-right cell. In a single step, the robot
can move only to the cells to its immediate right and bottom directions. More specifically, if the robot
is at position $(i, j)$, then it can move either to position $(i+1, j)$ or to $(i, j+1)$, provided that
both positions are inside the grid.
\par The challenge is that there are $P$ obstacles in random positions on the grid, through which the robot
cannot pass. Given the positions of the blocked cells, your task is to count all the number of paths that the robot
can take to move from $(1, 1)$ to $(M, N)$.
\item Your team lost in the above challenge, thus you resort to stop doing algorithms and find a real job. You
are hired by a lottery company with the purpose of navigating $n$ cities and collecting all the lottery tickets
from the citizens of each city. However, being a true fan of algorithms, you want to traverse the cities in the most
efficient manner.
\par It turns out that some of the cities have roads between them and some do not. Also, some cities have lottery tickets
for you to collect, while some other cities do not. Therefore, the input to your problem can be represented as an undirected
weighted graph $G = (V, E)$, where each node is a city and each edge $\{u, v\}$ represents the road between cities $u$ and
$v$. The weight of this edge is equal to the distance between $u$ and $v$. Furthermore, exactly $k$ cities have lotteries to be collected, and these are given by set $S\subset V$ where $|S|=k$. Consider $k$ being a {\bf constant}. Since you live in city $s\notin S$, starting at $s$, your goal is to design an algorithm that computes the minimum total distance you have to travel to collect all the lottery tickets and return at $s$.
%each node $u$ contains a positive number $t(u)$ of lottery tickets for you to collect. For the cities that do not have lottery tickets,
%$t(u) = 0$. You start at a specific city $s$, and your goal is to design an algorithm that minimizes the total distance
%you have to travel to collect all the lottery tickets.
\item Consider the complete graph $K_n$ on a set $V$ of $n$ vertices. A tournament $T = (V, E)$ is an orientation of the edges
of $K_n$. Thus, for every two distinct nodes $u, v \in V$, either $(u, v) \in E$, or $(v, u) \in E$, but not both. The
name ``tournament" is natural as one can think of the set $V$ as the set of players playing a round-robin tournament, that is every player plays against every other player exactly once, %in which every pair of players participates in a single match
and there is a directed edge $(u, v)$ if and only if $u$ beats $v$ in the single match.
\par We say that $T$ has the property $\mathbf{Beats}$-$k$ if for every set of $k$ players, there exists another player that beats them all. That is, for every subset $S \subset V$ with $|S|=k$, there exists a node $u \in V\setminus S$ such that there is an edge from $u$ to $v$ for each $v \in S$. Note that node $u$ may be different for different $S$. For example, a directed triangle $T_3$ with $V = \{1, 2, 3\}$ and $E = \left\{ (1,2), (2, 3), (3, 1) \right\}$ has {\bf Beats}-$1$.
\begin{enumerate}
\item Starting from $K_n$ suppose we construct $T$ by orienting each edge $\{u, v\}$ either $(u, v)$ with probability
$\frac{1}{2}$ or $(v, u)$ with probability $\frac{1}{2}$.
Give a non-trivial lower for the probability that $T$ satisfies the {\bf Beats}-$k$ property for a fixed $k$?
\item Given $k$, show that there are tournaments with $O(2^k k^2)$ many players that satisfy {\bf Beats}-$k$ property? [{\bf Hint:} Use solution of the first part.]
%what is the minimum number, say $n_{min}$, such that there exists a tournament with $n_{min}$ many players satisfying {\bf Beats}-$k$ property?
\item[\bf Optional] Just to see the power of randomness try proving the second part without using a random graph.
\end{enumerate}
\end{enumerate}
\vspace{2em}
{\bf The remaining problems are for self study. Do \emph{NOT} submit for grading.}
\begin{itemize}
\item You are playing a game with your friend. You both enter a dungeon with the purpose of collecting gold.
The dungeon is represented as a rectangular grid of $N$ rows and $M$ columns, and each cell $(i, j)$ except for the cell
$(1, 1)$ (the top-left one) has a specific number of gold coins $c(i, j)$ on it. You and your friend both enter the
dungeon through cell $(1, 1)$, and your goal is to reach the cell $(N, M)$.
\par You start playing a bizarre game. You and your friend always move together, to the same cells, but you take
turns deciding at which cell to move, given that you can only move to the right and/or bottom. More specifically, there
exists a fixed $K$ such that, if you are at cell $(i, j)$ and it is your turn to select the next cell to move, you can
move to any cell that is at most $K$ cells to the right and $K$ cells to the bottom, i.e. to any cell in the rectangular
grid created by $(i, j)$ and $(i+K, j+K)$, with the restriction that you have to move to a different cell each time.
When you move to a new cell, whoever's turn it was to decide the move takes all the gold of that cell.
\par Suppose you have a map of the dungeon with the amount of gold on each cell, and you start the game by being the first to
decide where you will move. Assuming that your best friend always plays optimally, find a path through the dungeon that will
get you the maximum number of gold possible. Furthermore, if there are more than one paths that get you the maximum number
of gold, pick the one that minimizes the gold that your friend will obtain.
{\em Hint:} You might have to devise a way to combine two recurrence relations in order to solve the problem.
\item Show that quick select takes $O(n)$ time in expectation. See if you can
prove that the number of comparisons is at most $4n$ for an array of size $n$.
\item Solve the first problem on shortest paths via dynamic programming
in the file below. \url{https://courses.engr.illinois.edu/cs374/fa2015/labs/lab16-shortest-path-dynamic-prog.pdf}.
\item Solve the first problem on shortest walks in the file below.
\url{https://courses.engr.illinois.edu/cs374/fa2015/homework/hw8.pdf}.
\item Read Jeff's notes on randomized quick sort but in particular the nuts and bolts problem. Solve some of the basic problems on probability and randomized algorithms at the back of the notes. \url{http://jeffe.cs.illinois.edu/teaching/algorithms/notes/09-nutsbolts.pdf}.
\end{itemize}
\end{document}