%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 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}