\documentclass[12pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Setup and packages (students should ignore)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage[margin=1in]{geometry} 
\usepackage{amsmath,amsthm,amssymb,amsfonts}
\usepackage[usenames,dvipsnames,table]{xcolor}
\usepackage{titlesec}
\usepackage{enumitem}
\usepackage{url}
\usepackage{tcolorbox}
%links
\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,      
    urlcolor=blue,
}
%listings (for pseudocode)
\usepackage{listings}
\usepackage{sourcecodepro}
\definecolor{listing-background}{HTML}{FAFAFA}
\definecolor{listing-rule}{HTML}{B3B2B3}
\definecolor{listing-numbers}{HTML}{B3B2B3}
\definecolor{listing-text-color}{HTML}{000000}
\definecolor{listing-keyword}{HTML}{435489}
\definecolor{listing-keyword-2}{HTML}{1284CA} % additional keywords
\definecolor{listing-keyword-3}{HTML}{6D2998} % additional keywords
\definecolor{listing-identifier}{HTML}{000000}
\definecolor{listing-string}{HTML}{00999A}
\definecolor{listing-comment}{HTML}{606060}
\definecolor{default-linkcolor}{HTML}{A50000}
\definecolor{default-filecolor}{HTML}{A50000}
\definecolor{default-citecolor}{HTML}{4077C0}
\definecolor{default-urlcolor}{HTML}{4077C0}
\lstdefinelanguage{pseudocode}{
  morekeywords={
    % normal keywords (without data types)
    abstract,assert,break,case,catch,class,continue,create,default,
    do,else,end,enum,exports,extends,final,finally,for,if,implements,
    import,instanceof,interface,mark,module,native,package,private,
    procedure,protected,public,requires,return,static,strictfp,super,switch,
    synchronized,this,then,throw,throws,transient,try,volatile,while,
    % var is an identifier
    var
  },
  morekeywords={[2] % data types
    % primitive data types
    boolean,byte,char,double,float,int,long,short,
    % String
    String,
    % primitive wrapper types
    Boolean,Byte,Character,Double,Float,Integer,Long,Short
    % number types
    Number,AtomicInteger,AtomicLong,BigDecimal,BigInteger,DoubleAccumulator,DoubleAdder,LongAccumulator,LongAdder,Short,
    % other
    Object,Void,void
  },
  morekeywords={[3] % literals
    % reserved words for literal values
    null,true,false,True,False,visited,unvisited
  },
  sensitive,
  morecomment  = [l]//,
  morecomment  = [l]\%,
  morecomment  = [s]{/*}{*/},
  morecomment  = [s]{/**}{*/},
  morestring   = [b]",
  morestring   = [b]'
}
\lstdefinestyle{eisvogel_listing_style}{
  language         = pseudocode,
  numbers          = left,
  xleftmargin      = 2.7em,
  framexleftmargin = 2.5em,
  backgroundcolor  = \color{listing-background},
  basicstyle       = \color{listing-text-color}\linespread{1.0}%
                      \lst@ifdisplaystyle%
                      \small%
                      \fi\ttfamily{},
  breaklines       = true,
  frame            = single,
  framesep         = 0.19em,
  rulecolor        = \color{listing-rule},
  frameround       = ffff,
  tabsize          = 4,
  numberstyle      = \color{listing-numbers},
  aboveskip        = 1.0em,
  belowskip        = 0.1em,
  abovecaptionskip = 0em,
  belowcaptionskip = 1.0em,
  keywordstyle     = {\color{listing-keyword}\bfseries},
  keywordstyle     = {[2]\color{listing-keyword-2}\bfseries},
  keywordstyle     = {[3]\color{listing-keyword-3}\bfseries},
  sensitive        = true,
  identifierstyle  = \color{listing-identifier},
  commentstyle     = \color{listing-comment},
  stringstyle      = \color{listing-string},
  showstringspaces = false,
  mathescape = true
}
\lstnewenvironment{pseudo}{
	\lstset{style=eisvogel_listing_style}
}{}
%theorem etc. environments
\usepackage{thmtools}
\newtheorem{claim}{Claim}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{observation}{Observation}
\theoremstyle{definition}
\newtheorem{definition}{Definition}
\newtheorem{question}{Problem}
\newtheorem{problem}{Problem} %
\declaretheoremstyle[
    headfont=\bfseries\sffamily\color{ForestGreen!70!black}, bodyfont=\normalfont,
    mdframed={
        linewidth=2pt,
        rightline=false, topline=false, bottomline=false,
        linecolor=ForestGreen, backgroundcolor=ForestGreen!5,
    }
]{thmgreenbox}
\declaretheorem[style=thmgreenbox, name=Hint,numbered=no]{hint}
\declaretheoremstyle[
    headfont=\bfseries\sffamily\color{Red!70!black}, bodyfont=\normalfont,
    mdframed={
        linewidth=2pt,
        rightline=false, topline=false, bottomline=false,
        linecolor=Red, backgroundcolor=Red!5,
    }
]{thmredbox}
\declaretheorem[style=thmredbox, name=Note,numbered=no]{warning}
\titleformat*{\section}{\large\bfseries}
\newenvironment{solution}{\bigskip\noindent{\em Solution.}  \ignorespaces}{\hfill\qed}
%title etc 
\newcommand{\homework}[6]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf CS256-01:~Algorithm Design and Analysis \hfill} }
       \vspace{6mm}
       \hbox to 6.28in { {\Large \hfill #1 \normalsize{(#2)}  \hfill} }
       \vspace{6mm}
     \hbox to 6.28in { {\it Instructor: #3 \hfill } }
       %\hbox to 6.28in { {\it TA: #4  \hfill #6}}
   %   \vspace{2mm}
   }
   }
   \end{center}
   \markboth{#1}{#1}
   \vspace*{4mm}
}

%%%%%%%%%%%%%%%%%%%%%%
% Begin main document 
%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\homework{Assignment 0}{due 02/07/2024 }{Sam McCauley}{}{}{}

 
\noindent
\paragraph{Note.} This homework will not be graded on correctness but on completion---to get full points, you must attempt all the questions (except the optional feedback question).


The goal of this assignment is for you to check your familiarity with the background material from Data Structures (CS136) and Discrete Math (MATH200), and for you to get comfortable with \LaTeX. It is {your responsibility} to fill in the gaps in your knowledge.  

\noindent
\paragraph{Submission guidelines.} When submitting your solution PDF on Gradescope, you must match questions to pages in the PDF.  This takes less than a minute and is crucial for efficient and anonymous grading. Sometimes, you may need to mark pages approximately, e.g., for multi-part questions such as Problem~\ref{shortanswer}. 

\bigskip
   
\noindent
There is one question per page of this assignment.  Make sure you scroll to see all pages.  

\bigskip
\bigskip

\begin{question}
Please complete the intro form; a link has been included below for convenience.
\end{question}

\bigskip
\bigskip

\textbf{Intro Form:}  \url{https://forms.gle/Le3cj5WA7hKF2mwh9}

\newpage

\begin{question}
Let $A, B$ be sets. Prove by contradiction that $A \cap B = \emptyset \implies A \subseteq \overline{B}$.
\end{question}
%\begin{question}
%Prove that $1 + 2 + 3 + 4 + \ldots + n = n(n+1)/ 2$.
%\end{question}

\begin{solution}
	%TODO: Fill in

\end{solution}

\newpage
\begin{question}
	The following sorting algorithm appears to be riddled with problems.  The inner loop scans the entire array, and it swaps $A[i]$ with $A[j]$ when $A[i]\leq A[j]$---even if $i < j$.

	\begin{pseudo}
TypoSort(A):
	for i = 0 to $|A|$-1:
	   for j = 0 to $|A|$-1:
		   if A[i]<=A[j]: // does not check if i < j
			   swap(A[i],A[j]) 
	\end{pseudo}

	Surprisingly, \texttt{TypoSort} correctly sorts an array (try it!).
	Prove using induction that \texttt{TypoSort} is correct.  

	\begin{hint}
		Use the following invariant: after $k$ iterations of the outer loop, $A[0]$ through $A[k-1]$ are in sorted order.

		You may assume that if $A[0]$ through $A[k-1]$ are already in sorted order, the following algorithm (run on $A$ and $k$) ensures that $A[0]$ through $A[k]$ are in sorted order:
\begin{pseudo}
Subroutine(A,k):
   for j = 0 to k:
	   if A[k]<=A[j]: 
		   swap(A[k],A[j]) 
\end{pseudo}
	\end{hint}

  	\begin{solution}
	%TODO: Fill in
    \end{solution} 

\end{question}


\newpage
\begin{warning}
	Problem~\ref{shortanswer} relies on material we will see on Monday, 02/05/23.
\end{warning}

\begin{question}%
\label{shortanswer}


For each of the following, answer with the tightest upper bound from this list: $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$, $O(2^n)$. Briefly
justify your answer.
  \begin{enumerate}[label=(\alph*)]
  	\item The number of leaves in a complete\footnote{Complete: Every leaf has same depth and every non-leaf node has two children.} binary tree of height $n$:
  	
  	\begin{solution}
	%TODO: Fill in

    \end{solution} 
	\item The depth of a complete binary tree with $n$ nodes:
	
	\begin{solution}
	%TODO: Fill in

    \end{solution} 
    
	\item The worst-case run time to sort $n$ items using merge sort:
	
	\begin{solution}
	%TODO: Fill in

    \end{solution} 
    
	\item The number of distinct subsets of a set of $n$ items:
	
	\begin{solution}
	%TODO: Fill in

    \end{solution} 
    
	\item The number of bits needed to represent the positive integer $n$:
	
	\begin{solution}
	%TODO: Fill in

    \end{solution} 

	\item The time to find the second largest number in a set of $n$ (not necessarily sorted) numbers:
	
	\begin{solution}
	%TODO: Fill in

    \end{solution} 
  \end{enumerate}
  
\end{question}

\end{document}

