%
% This is the LaTeX template file for lecture notes for CS267,
% Applications of Parallel Computing.  When preparing
% LaTeX notes for this class, please use this template.
%
% To familiarize yourself with this template, the body contains
% some examples of its use.  Look them over.  Then you can
% run LaTeX on this file.  After you have LaTeXed this file then
% you can look over the result either by printing it out with
% dvips or using xdvi.
%

\documentclass{article}
%% \setlength{\oddsidemargin}{-0.25 in}
%% %% \setlength{\evensidemargin}{-0.25 in}
%% \setlength{\topmargin}{-0.6 in}
%% \setlength{\textwidth}{6.5 in}
%% \setlength{\textheight}{8.5 in}
\usepackage[margin=1in]{geometry}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}

%
% ADD PACKAGES here:
%

\usepackage{amsmath,amsfonts,graphicx}

%
% The following commands set up the lecnum (lecture number)
% counter and make various numbering schemes work relative
% to the lecture number.
%
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}
\usepackage{color}
\newcommand{\todo}[1]{\textcolor{red}{[TODO: #1]}}

%
% The following macro is used to generate the header.
%
\newcommand{\lecture}[4]{
  \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{lecnum}{#1}
   \setcounter{page}{1}
   \noindent
   \begin{center}
     \framebox{
       \vbox{\vspace{2mm}
     \hbox to 6.28in { {\bf CMPSCI 311: Introduction to Algorithms
                \hfill Spring 2018} }
       \vspace{4mm}
       \hbox to 6.28in { {\Large \hfill Homework #1  \hfill} }
       \vspace{2mm}
       \hbox to 6.28in { \textbf{Name:} \todo{Your name} \hfill \textbf{Collaborators}: \todo{Your Collaborators}} 
       %% \hbox to 6.28in { Released 1/24/2018 \hfill Due 11:59pm 2/7/2018 in Gradescope}
       %% \hbox to 6.28in { {\it Lecturer: #3 \hfill Scribes: #4} }
      \vspace{2mm}}
    }
   \end{center}
   \markboth{Homework #1}{Homework #1}

   \vspace*{4mm}
 }
 %
 % Convention for citations is authors' initials followed by the year.
 % For example, to cite a paper by Leighton and Maggs you would type
 % \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}.
 % (To avoid bibliography problems, for now we redefine the \cite command.)
 % Also commands that create a suitable format for the reference list.
\renewcommand{\cite}[1]{[#1]}
\def\beginrefs{\begin{list}%
  {[\arabic{equation}]}{\usecounter{equation}
         \setlength{\leftmargin}{2.0truecm}\setlength{\labelsep}{0.4truecm}%
         \setlength{\labelwidth}{1.6truecm}}}
\def\endrefs{\end{list}}
\def\bibentry#1{\item[\hbox{[#1]}]}

  %Use this command for a figure; it puts a figure in wherever you want it.
  %usage: \fig{NUMBER}{SPACE-IN-INCHES}{CAPTION}
  \newcommand{\fig}[3]{
    \vspace{#2}
                        \begin{center}
                          Figure \thelecnum.#1:~#3
                        \end{center}
        }
        % Use these for theorems, lemmas, proofs, etc.
\newtheorem{theorem}{Theorem}[lecnum]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}

% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM HERE:

\newcommand\E{\mathbb{E}}

\begin{document}
%FILL IN THE RIGHT INFO.
%\lecture{**LECTURE-NUMBER**}{**DATE**}{**LECTURER**}{**SCRIBE**}
\lecture{1}
%\footnotetext{These notes are partially based on those of Nigel Mansell.}

% **** YOUR NOTES GO HERE:

% Some general latex examples and examples making use of the
% macros follow.
%**** IN GENERAL, BE BRIEF. LONG SCRIBE NOTES, NO MATTER HOW WELL WRITTEN,
%**** ARE NEVER READ BY ANYBODY.

\textbf{Instructions.} You may work in groups, but you must individually write your solutions yourself.
List your collaborators on your submission.

If you are asked to design an algorithm as part of a homework problem, please provide: (a) the pseudocode for the algorithm, (b) an explanation of the intuition for the algorithm, (c) a proof of correctness, (d) the running time of your algorithm and (e) justification for your running time analysis.

There are four questions, each worth 25 points total.


\textbf{Submission instructions.} This assignment is by 11:59pm on 2/7/2018 in Gradescope.
Please submit a pdf file.
You may submit a scanned handwritten document, but a typed submission is preferred.
It will be extremely helpful if in your submission, you start each question on a new page. 

\begin{enumerate}
    % Q1
  \item \textbf{Stable Marriages}
    \begin{enumerate}
      % \item \textbf{Stable Marriage Running Time}
       \item \textbf{Stable Marriages: K\&T Ch 1, Ex 5.}
         \begin{enumerate}
          \item \textbf{Strong Instability.}
          \item \textbf{Weak Instability.}
         \end{enumerate}
    \end{enumerate}
\newpage
    % Q2
  \item \textbf{Big-Oh and Asymptotics}
    \begin{enumerate}
      \item \textbf{Big-Oh}
         \begin{enumerate}
           \item
           \item
           \item
           \item
           \item
         \end{enumerate}
       \item \textbf{Asymptotics. K\&T Ch 2, Ex 6.}
          \begin{enumerate}
          \item
          \item
        \end{enumerate}
    \end{enumerate}
\newpage
    %Q3 Graphs 1
  \item \textbf{Disrupting Communication Networks.}
  \begin{enumerate}
    \item
    \item
    \item
    \item
    \item
    \item
  \end{enumerate}

\newpage
  % Q4 Graphs 2
\item \textbf{Graphs}
  \begin{enumerate}
    % \item \textbf{Directed Graphs.}
    \item \textbf{K\&T Ch3.Ex12.}
  \end{enumerate}


\item \textbf{(0 points).} How long did it take you to complete this assignment?

\end{enumerate}

% **** THIS ENDS THE EXAMPLES. DON'T DELETE THE FOLLOWING LINE:

\end{document}





