\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,epsfig}
\setlength{\textwidth}{7in}
\setlength{\topmargin}{-0.575in}
\setlength{\textheight}{9.25in}
\setlength{\oddsidemargin}{-.25in}
\setlength{\evensidemargin}{-.25in}
\reversemarginpar
\setlength{\marginparsep}{-15mm}
\newcommand{\rmv}[1]{}
\newcommand{\bemph}[1]{{\bfseries\itshape#1}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
% Here the user must define certain strings for this homework assignment
%
\def\CourseCode{CS6901} % e.g. COMP2711
\def\AssignmentNo{1} % e.g. 1
\def\DateHandedOut{Fall, 2016} % e.g. September 18, 2002
\def\DateDue{Oct 4, 2016} % e.g. October 1, 2002
\def\TimeDue{7pm at D2L} % e.g. 11 am
\begin{document}
\noindent
Computer Science \CourseCode \hfill \DateHandedOut\\
\begin{center}
Homework Assignment \#\AssignmentNo\\
Due: \DateDue, \TimeDue\\
\end{center}
\hrule\smallskip
\begin{enumerate}
\item \textbf{Asymptotic notation} \marginpar{[10]}\\
List the following functions by increasing $O$-complexity: $2^{n \log n}, 2^{\log n}$, $(\log 2^n)$, $n^2$, $2^{2^n}$, $(\log \log 2^n)^2$, $n^{\sqrt{n}}$, $1000n^{100}$. Here, all logs are base $2$.
\item \textbf{Graphs} \marginpar{[45]}
\begin{enumerate}
\item Let $G=(V,E)$ be any undirected connected graph. Prove that there is a vertex $v \in V$ such that graph $G-\{v\}$ left after removing $v$ is still connected.
\item Suppose that on some social media a "social status" of a person is the number of her friends; if $A$ is a friend of $B$, then $B$ is a friend of $A$. A "well-connectedness" of a person is a sum of social statuses of all of her friends.
Give an algorithm to compute an array containing well-connectedness value for each person \emph{in total linear time}, when the input consists of lists, for each person, of all of her friends.
\item Suppose now that this social media has a "dislike" feature. It is not necessarily symmetric: that is, if $A$ dislikes $B$, that does not mean that $B$ dislikes $A$. They hypothesize that dislikes are due to political preferences: "round" may dislike some "square", but not other "round", and similarly "square" would only dislike "round". To test this hypothesis, they want to check that there is a way to label every person either "round" or "square" in such a way that no "round" dislikes a "round", and no "square" dislikes a "square".
Give a linear-time algorithm to solve this problem. Here, the input consists of lists, for every person, of people she dislikes. You can refer to algorithms we covered in class as subroutines.
\end{enumerate}
\item \textbf{Stable matching with repeating preferences} \marginpar{[45]} \\
In the stable matching problem we considered, every person could potentially have a unique preference list. Now, suppose that there are only several methods people use to rank their matches, and thus only a few possible rankings.
Suppose there are $k$ many possible rankings of men, and also $k$ possible rankings of women. In this case, the input is given as $n, k, M, W, MI, WI$, where $M$ and $W$ are now $n \times k$ matrices, and arrays $MI$ and $WI$ specify, for each man and woman, which row of matrices $M$ and $W$, respectively, he or she uses as ranking.
\begin{enumerate}
\item What will be the length of the input in the $\log n$ word model?
\item What is the running time of the Gale-Shapley stable matching algorithm we covered in class as a function of the input length, if $k$ is constant?
\item You may be wondering how having repeated rankings affects the performance of Gale-Shapley algorithm. To test this, implement the stable matching with repeating preferences variant of Gale-Shapley algorithm, with input given as above. You can use any programming language and any data structures (but do write the code yourself). Then do the testing as follows.
\begin{enumerate}
\item First, as a control, let $k=n$. Generate random inputs for $n=20$ to $n=200$, in increments of 10; produce 10 random inputs for each $n$. Now, run your program on each of these test cases and record the number of rounds as well as the overall running time for each.
\item To test what happens when $k$ is a small constant, repeat the experiment with $k=10$, for the same range of $n$ and number of samples for each $n$.
\item Now, choose several values of $n$, and repeat experiments now varying $k$.
\end{enumerate}
For the first two experiments, produce two plots: one for the average number of rounds as a function of $n$, and another for the average running time as a function of $n$; for the last experiment, produce plots for each $n$ you try as a function of $k$, as well as a function of the length of the input (in words). Submit your plots as well as your code; do not submit the data (but please do not delete it -- I might ask you to give me the raw data files).
\item Summarize what you learned as a result of your experiments. Does having small $k$ make the problem easier or harder for Gale-Shapley algorithm as a function of $n$, or is the average performance of Gale-Shapley algorithm unchanged?
\end{enumerate}
\end{enumerate}
\end{document}