\documentclass[12pt]{article}
\usepackage{hyperref}
\usepackage{times}
\usepackage{enumerate}
\setlength{\parindent}{0in}
\setlength{\parskip}{0ex}
\setlength{\textheight }{9.0in}
\setlength{\textwidth }{6.5in}
\setlength{\oddsidemargin }{0.0in}
\setlength{\evensidemargin}{0.0in}
\setlength{\headheight }{-0.3in}
\setlength{\headsep }{0.0in}
\setlength{\textheight }{9.0in}
\begin{document}
\begin{center}
{\Large \href{https://kgardner.people.amherst.edu/courses/f18/cosc311/}{\textsc{COSC 311: Algorithms}} \\
\href{https://kgardner.people.amherst.edu/courses/f18/cosc311/hw/hw1.pdf}{\textsc{HW1: Sorting and Asymptotic Analysis}} \\ \vspace{0.1in}
}
{\large Due Friday, September 21 in class}
\end{center}
\section{Submission and Collaboration}
Type up your responses to the questions below. I recommend using \LaTeX, which is a typesetting language that makes it easy to make math look good. If you're not already familiar with it, I encourage you to practice! You are also welcome to use your favorite word processor, provided that all equations and formulas are readable. \\
This assignment is due on Friday, September 21 at the start of class; bring a hard copy of your typed responses to submit in class. \textbf{Each problem must be on a separate sheet of paper, with your name and section number at the top of the page.} If you use more than one sheet of paper for an individual problem, please staple together those pages. There is no need for you to rewrite the problems on your submission. \\
In accordance with this course's intellectual responsibility policy, you are welcome to discuss the problems with other students who are currently taking the course, but you must write up your solutions individually. Please note at the top of your submission with whom you discussed each problem.
\section{Problems}
\textbf{Problem 1: Asymptotic analysis.}
(a) Suppose you know that $f(n) \in O(n^2)$ (and you don't know anything else about $f$). Are each of the following claims \textbf{true} for all possible choices of $f$, \textbf{false} for all possible choices of $f$, or \textbf{sometimes true} (i.e., true for some choices of $f$ and false for others)? Briefly explain your reasoning. You do not need to give any formal proofs.
\begin{enumerate}[(i)]
\item $f(n) \in \Omega(n)$
\item $f(n) \in \Theta(n^2)$
\item $f(n) \in O(n^3)$
\item $f(n) \in O(n \lg n)$
\item $f(n) \in \Theta(n^2 \lg n)$
\item $f(n) \in \Omega(n^4)$
\item $f(n) \in O(14n^2 + 74)$
\end{enumerate}
(b) Let $f(n) = 3n^2 + \frac{\lg n}{n}$. Prove that $f(n) \in \Theta(n^2)$. \\
(c) Let $f(n) = 100n - 7$. Is $f(n) \in O(n \lg n)$? Is $f(n) \in \Omega(n \lg n)$? Prove or disprove each. \\
\textbf{Problem 2: Analyzing heapsort.} Here is the heapsort algorithm that we wrote together in class:
\begin{verbatim}
1 Heapsort(A) // A is an unsorted array of length n
2 A.heapify()
3 ans: a new array of length n
4 for i = 0 to n-1
5 ans[i] = A[0]
6 A[0] = A[n-1-i]
7 A.siftDown(0)
8 for i = 0 to n-1
9 A[i] = ans[i]
\end{verbatim}
(a) The \texttt{heapify} that we wrote in class is a bottom-up, iterative method. Rewrite \texttt{heapify} as a top-down, recursive method (you may find that you need an extra parameter; this is fine). \\
(b) Write a recurrence for $T(n)$, the runtime of your \texttt{heapify} method from part (a). You can assume that $n$ is one less than a power of 2, i.e., all levels of the heap are full. \\
(c) Assume $n$ is a power of 2. Prove by induction that $T(n) \in O(n)$. (Hint: show that $T(n) \leq c_1 n - c_1 \lg n$ for the appropriate choices of $c_1$ and $n_0$ (again, you can assume that $n$ is one less than a power of 2). This likely will be somewhat easier to show than trying to show directly that $T(n) \leq c_1 n$.) \\
(d) Put it all together: What is the asymptotic runtime of heapsort? Give your answer in the simplest form possible, i.e., omitting constant factors and lower-order terms. Briefly explain your reasoning (you might find it helpful to refer to the line numbers in the pseudocode above). You may find that you need to review the asymptotic analysis of heaps! \\
\textbf{Problem 3: What do we learn from asymptotic analysis?} In this problem you will explore the value and limitations of asymptotic analysis by experimenting with three sorting algorithms: insertion sort, mergesort, and a new algorithm called bubble sort.
\begin{verbatim}
1 BubbleSort(A) // A is an unsorted array of length n
2 for i = 0 to n-1
3 for j = 1 to n - 1 - i
4 if A[j-1] > A[j]
5 swap(A, j-1, j)
\end{verbatim}
(a) Explain in a short paragraph \underline{what} bubble sort is doing (i.e., what is the sequence of steps it follows?) and \underline{why} it works. Your goal is to help another CS undergrad understand what bubble sort does and convince them that this algorithm will in fact result in a sorted array. \\
(b) What is the asymptotic runtime of bubble sort? Justify your answer in a sentence or so. \\
(c) Based on your answer to (b), how much wall-clock time do you expect bubble sort to take relative to mergesort? What about insertion sort? (``Wall-clock'' time is the amount of time that passes between when you start running your program and when it finishes. This is not the same as the number of operations the computer does while running your code, it instead has to do with the user experience of waiting for your code to finish running.) \\
(d) Download my \texttt{Sort.java} code from: \\ \href{https://kgardner.people.amherst.edu/courses/f18/cosc311/hw/hw1/Sort.java}{https://kgardner.people.amherst.edu/courses/f18/cosc311/hw/hw1/Sort.java}. \\
The file contains implementations of three sorting algorithms: insertion sort, mergesort, and bubble sort. Your job is to run an experiment to compare their performance. Specifically, do the following:
\begin{itemize}
\item Fill an array of length $n$ with randomly generated ints between 0 ant $10^6$.
\item Sort the array using \{insertion sort, mergesort, bubble sort\}. Time how long this takes by recording the system time before and after running the sorting method. You can do this as follows:
\begin{verbatim}
long start_time = System.nanoTime();
// whatever code you want to time
long end_time = System.nanoTime();
long time_my_code_took = end_time - start_time;
\end{verbatim}
\end{itemize}
Repeat the above for each of the three sorting algorithms for many values of $n$. You will want to try some small values of $n$ (less than 1000), some large values of $n$ (greater than 100000), and some in between. Be sure to re-fill your array with a new set of random numbers in between each sorting algorithm---otherwise you will be sorting data that is already in sorted order, which might lead to inaccurate results. \\
Graph your results: make one graph with all three algorithms, with $n$ on the $x$-axis and time on the $y$-axis (you may find that it is easier to see what's going on if you also make separate graphs for small $n$ and large $n$). \\
Discuss your findings. Do your experimental results match up to your predictions in part (b)? Is the asymptotic analysis equally predictive at small $n$ and large $n$? Are there things you learn about the relative performance of the three algorithms from the experimental results that you don't learn from the asymptotic analysis? Any other interesting observations? \\
Note: you \textbf{do not} need to submit your code for this problem.
\end{document}