natalie_code/written_hw/npueyo_hw2.tex

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Short Sectioned Assignment
% LaTeX Template
% Version 1.0 (5/5/12)
%
% This template has been downloaded from:
% http://www.LaTeXTemplates.com
%
% Original author:
% Frits Wenneker (http://www.howtotex.com)
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------

\documentclass[paper=a4, fontsize=11pt]{scrartcl} % A4 paper and 11pt font size

\usepackage[colorlinks=true, allcolors=red]{hyperref}
\usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs
%\usepackage{fourier} % Use the Adobe Utopia font for the document - comment this line to return to the LaTeX default
\usepackage[english]{babel} % English language/hyphenation
\usepackage{mathtools}                             % More complete math support in Latex than amsthm
\usepackage{amsmath,amsfonts,amsthm}               % Math packages
\usepackage{amssymb}                               % Additional math symbols.
\usepackage{graphicx}                              % Graphics with e.g. \includegraphics{file.png}.
%\usepackage{subfigures}                            % Have multiple figures in one.
\usepackage{caption}                               % Customize caption formatting.
\usepackage{subcaption}                            % Subfigures.
\usepackage{tabularx}                              % Width controlled tabulars.
\usepackage{enumerate}                             % change appearance of enumerate

\usepackage{sectsty}                               % Allows customizing section commands
\allsectionsfont{\centering \normalfont\scshape}   % Make all sections centered, the default font and small caps

\usepackage{tikz}
\usetikzlibrary{automata,positioning}

\usepackage{fancyhdr} % Custom headers and footers
\pagestyle{fancyplain} % Makes all pages in the document conform to the custom headers and footers
\fancyhead{} % No page header - if you want one, create it in the same way as the footers below
\fancyfoot[L]{} % Empty left footer
\fancyfoot[C]{} % Empty center footer
\fancyfoot[R]{\thepage} % Page numbering for right footer
\renewcommand{\headrulewidth}{0pt} % Remove header underlines
\renewcommand{\footrulewidth}{0pt} % Remove footer underlines
\setlength{\headheight}{13.6pt} % Customize the height of the header

\numberwithin{equation}{section} % Number equations within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)
\numberwithin{figure}{section} % Number figures within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)
\numberwithin{table}{section} % Number tables within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)

\setlength\parindent{0pt} % Removes all indentation from paragraphs - comment this line for an assignment with lots of text

%\usepackage{mathtools}
%\DeclarePairedDe\limiter{\ceil}{\lceil}{\rceil}
%\DeclarePairedDe\limiter{\floor}{\lfloor}{\rfloor}

\newcommand{\heads}{\textsc{h}}
\newcommand{\tails}{\textsc{t}}

\newcommand{\logten}{\log}%\mathrm{\log}\hspace{0.05in}}
\newcommand{\logtwo}{\lg}%\mathrm{lg}\hspace{0.05in}}
\newcommand{\loge}{\ln}%\mathrm{ln}\hspace{0.05in}}

\theoremstyle{definition}
\newtheorem*{solution}{Solution}

\usepackage{algpseudocode, algorithm}

%----------------------------------------------------------------------------------------
% TIKZ SECTION
%----------------------------------------------------------------------------------------
\usetikzlibrary{arrows}

\tikzset{
	treenode/.style = {align=center, inner sep=0pt, text centered,
		font=\sffamily},
	arn_n/.style = {treenode, circle, black, font=\sffamily\bfseries, draw=black,
		text width=1.5em, very thick},% arbre rouge noir, noeud noir
	%arn_r/.style = {treenode, circle, red, draw=red,
	%  text width=1.5em, very thick},% arbre rouge noir, noeud rouge
	arn_x/.style = {treenode, rectangle, draw=white,
		minimum width=0.5em, minimum height=0.5em}% arbre rouge noir, nil
}

%----------------------------------------------------------------------------------------
%	TITLE SECTION
%----------------------------------------------------------------------------------------

\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height

\title{
\normalfont \normalsize
\textsc{ECS 60 \hfill Dept. of Computer Science, UC Davis \hfill Winter 2018} % Your university, school and/or department name(s)
\horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule
\huge Homework \#2 Due 2/4/18 by 11:59pm\footnote{Last updated \today} \\ % The assignment title
\horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule
}


\author{Natalie Pueyo Svoboda, 997466498} % Put your name here

\date{\today}

\begin{document}

\maketitle

Homeworks are to be submitted to Gradescope by the above due date. List your classmate collaborators on the front page. The quiz will occur in-class on Wednesday, 2/7/18. Problems come from:
\begin{description}
	\item[Weiss] "Data Structures and Algorithm Analysis in C++"
	\item[Sedgewick \& Wayne] "Algorithms"
\end{description}

\begin{itemize}
	\item (Weiss) We are given an array that contains N numbers. We want to determine if there are two numbers whose sum equals a given number K. For instance, if the input is 8, 4, 1, 6, and K is 10, then the answer is yes (4 and 6). A number may be used twice. First, give an $O(n^2)$ algorithm to solve this problem. Then give the pseudocode of an $O(n \log n)$ algorithm to solve this problem (Hint: sort first).
	\item (Weiss) Give the pseudocode of a data structure that supports the stack \texttt{push} and \texttt{pop} operations, and a third operation \texttt{findMin}, which returns the smallest element in the data structure, all in $O(1)$ worst-case time.
	\item (Sedgewick \& Wayne) Inserting the keys in the order $A X C S E R H$ into an initially empty binary search tree gives a worst-case tree where every node has one null link, except one at the bottom, which has two null links.  Give five other orderings of these keys that produce worst-case trees.
	\item (Sedgewick \& Wayne) Suppose that a certain binary search tree has keys that are integers between 1 and 10,  and  we search for 5. Which sequence below cannot be the sequence of keys examined?
	\begin{itemize}
		\item[a.] 10, 9, 8, 7, 6, 5
		\item[b.] 4, 10, 8, 7, 5
		\item[c.] 1, 10, 2, 9, 3, 8, 4, 7, 6, 5
		\item[d.] 2, 7, 3, 8, 4, 5
		\item[e.] 1, 2, 10, 4, 8, 5
	\end{itemize}
	\item (Sedgewick \& Wayne) Give pseudocode for a binary search tree method \texttt{height()} that computes the height of the tree. Develop two implementations: the first, a recursive method (which takes linear time and space proportional to the height), and the second, a method that adds a field to each node in the tree (and takes linear space and constant time per query).
\end{itemize}

\section{First Problem}
    \begin{solution}

			\begin{enumerate}[a)]
				\item A $\mathcal{O}(n^2)$ algorithm that could be used to solve this problem would involve two \texttt{for} loops with an \texttt{if} statement.
				The first \texttt{for} loop would be used to through the array one element at a time to get the first number in the sum.
				The second \texttt{for} loop would be nested in the first \texttt{for} loop and would also go through each element in the array to provide the second number in the sum.
				Lastly, there would be an \texttt{if} statement inside the second for loop that would check if each sum is equal to the given $K$ value.
				\item On the other hand, a $\mathcal{O}(n \cdotp log(n))$ algorithm in pseudocode to do the same thing could be:

				\begin{verbatim}
					low := 0;
					high := N - 1;
					sort(array);
					for(i := 0; j < N; j := j + 1)
					   mid = floor((low + high) / 2);
					   if(array[mid] = (K - array[i]))
					      print("A match was found");
					      break;
					   else if(array[mid] < (K - array[i]))
					      low := mid + 1;
					   else
					      high := mid - 1;
				\end{verbatim}
% https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/a/implementing-binary-search-of-an-array

%for (j = 0; j < N; j++)
%   perform binary search for (K – array[j])  (O(logN)
%   if found print Yes, stop
%		if no search is successful, print No
			\end{enumerate}
    \end{solution}

		\section{Second Problem}
		    \begin{solution}
					The way to implement a data structure that supports the stack \texttt{push()},\texttt{pop()}, and \texttt{findMin()} is to use to stacks.
					The first is used as the 'normal' stack which saves each new value.
					The second stack, \texttt{minStack}, is used to save the history of the minimum values as they are pushed onto the stack.

					\begin{verbatim}
						class stackWithMin{
						   Stack stack;
						   Stack minStack;
						   void listPrepend(Stack, item);
						   void listRemoveAfter(Stack, int);
						   void push(item);
						   int pop();
						   int findMin();
						}swm;

						push(newItem){
						   swm.listPrepend(swm.stack, newItem);
						   if newItem <= swm.minStack->head then
						      swm.listPrepend(swm.minStack, newItem);
						}

						pop(){
						   poppedItem := swm.stack->head;
						   swm.listRemoveAfter(swm.stack, 0);
						   if poppedItem = swm.minStack->head then
						      swm.listRemoveAfter(swm.minStack, 0);
						   return PoppedItem;
						}

						findMin(){
						   minValue := swm.minStack->head;
						   return minValue;
						}
					\end{verbatim}
% zybooks 2.11
% https://www.geeksforgeeks.org/design-and-implement-special-stack-data-structure/
		    \end{solution}

\section{Third Problem}
    \begin{solution}
			The following are five ways to order the keys $A X C S E R H$ so as to give worst-case BST:

			\begin{enumerate}[a)]
				\item $A C E H R S X$
				\item $A C E X S R H$
				\item $A C X E S H R$
				\item $X S R H E C A$
				\item $X A S C R E H$
			\end{enumerate}
		\end{solution}

\section{Fourth Problem}
    \begin{solution}
			Out of the following sequences, only \textbf{(d)} would not be a possible sequence of examining a BST.
			This is because in case \textbf{(d)}, at the second level node 7 would be parent node to \textbf{both} nodes 3 and 8 according to BST rules.
			In this case, when searching for the value 5, by BST rules, the search would not traverse to another branch (see figure).

			\begin{enumerate}[a)]
				\item 10, 9, 8, 7, 6, 5
				\item 4, 10, 8, 7, 5
				\item 1, 10, 2, 9, 3, 8, 4, 7, 6, 5
				\item 2, 7, 3, 8, 4, 5 (Does not work)
				\item 1, 2, 10, 4, 8, 5
			\end{enumerate}

			\begin{tikzpicture}[->,>=stealth',level/.style={sibling distance = 5cm/#1,
  				level distance = 1.5cm}]
			\node [arn_n] {2}
			    child{ node [arn_x] {}
			            child{ node [arn_x] {}
			            	child{ node [arn_x] {}}
										child{ node [arn_x] {}}
			            }
			            child{ node [arn_x] {}
										child{ node [arn_x] {}}
										child{ node [arn_x] {}}
			            }
			    }
			    child{ node [arn_n] {7}
			            child{ node [arn_n] {3}
										child{ node [arn_x] {}}
										child{ node [arn_n] {4}
											child{ node [arn_x] {}}
											child{ node [arn_n] {5}
											}
										} %for a named pointer
			            }
			            child{ node [arn_n] {8}
										child{ node [arn_x] {}}
										child{ node [arn_x] {}}
			            }
								};
			\end{tikzpicture}

		\end{solution}

\section{Fifth Problem}
    \begin{solution}
			The first implementation with linear time and space proportional to the height:

			\begin{verbatim}
				int height(tree){
				   left, right := 0;
				   if tree = null then
				      return -1;
				   else
				      if tree.leftbranch != null then
				         left = height(tree.leftbranch);
					    if tree.rightbranch != null then
				         right = height(tree.rightbranch);
				 return max(left, right) + 1;
				}
			\end{verbatim}

			The second implementation with linear space and constant time per query.
			This one requires that I also implement a way to add a field to a node.
			In this case, the \texttt{insert()} method recalculates each node height value using recursion after a new node is inserted.
			When the \texttt{height()} method is called, the method returns the value found at the pointer to the height of the root calculated in \texttt{insert()}.

			\begin{verbatim}
				node* insert(node* root, node* newNode){
				   if root = null then
				      newNode->height := 1;
				      return newNode;
				   if root->value < newNode->value then
				      root->right := insert(root->right, newNode);
				   else
				      root->left := insert(root->left, newNode);

				   // height at root starts at 1 so add that to calculation
				   root->height := max(root->left->height, root->right->height) + 1;
				   return root;
				}

				height(tree){
				   heightOfTree->root;
				   return heightOfTree;
				}

			\end{verbatim}
		\end{solution}


\end{document}