\documentclass[12pt]{amsart}
\usepackage[margin=1in]{geometry} % see geometry.pdf on how to lay out the page. There's lots.
% or letter or a5paper or ... etc
% \geometry{landscape} % rotated page geometry
\usepackage{enumerate}
\usepackage{url}
\usepackage[]{algorithm2e}
% See the ``Article customise'' template for come common customisations
\title{Homework: Complexity and Energy Usage}
\date{} % delete this line to display the current date
%%% BEGIN DOCUMENT
\begin{document}
\maketitle
\noindent \emph{The Python 3 \texttt{energyusage} package needed for this homework only runs on a Linux computer with the RAPL interface (an Intel CPU). The package can be installed by running: \texttt{pip install energyusage}.}
%% Suggestion to instructors: change the below 50,000,000 to be the operations per second of your student lab computers.
\begin{enumerate}[a)]
\item In Python, make functions that have the exact below complexity:
\begin{enumerate}[i)]
\item $50000000 \cdot n$
\item $50000000 \cdot n^2$
\item $50000000 \cdot 2^n$
\end{enumerate}
\item \label{n} Suppose you have a computer that can perform $50,000,000$ operations per second. For each of the functions, determine the largest input size $n$ for which you can determine the result within 5 minutes.
\item Run each of the functions above, varying $n$ from $1$ to the number you determined in part \ref{n}. Run those functions using the \texttt{energyusage} package on a Linux computer with an Intel processor. The package will give you the information you'll need for the graphs in part \ref{graph}. An example run on a simple function $f$ with input $x$ and return value $y$ is:
\begin{verbatim}
secs, kwh, y = energyusage.evaluate(f, x, energyOutput=True)
\end{verbatim}
where \texttt{kwh} is the resulting energy usage in kilowatt hours, and the time used is also returned (in seconds). If you are running on a machine that performs \emph{approximately} $50,000,000$ operations per second, note that you can test your above calculations in this step, but they may not match exactly.
\item \label{graph} Make two graphs for each of the functions above:
\begin{enumerate}[i)]
\item a graph showing $n$ on the x-axis versus time (in seconds) on the y-axis, and
\item a graph showing $n$ on the x-axis versus energy usage (in kilowatt hours) on the y-axis.
\end{enumerate}
You may use whatever graphing software or package you prefer to create these graphs. Make sure you have properly labeled the axes and titled your graphs.
\item \label{co2} The power plants supplying electricity to your computer emit between 2.4 and 1.1 pounds of carbon dioxide per kWh.
Which function minimizes the amount of carbon dioxide emitted for $n=5$? What about in total over $5$ minutes?
\item \label{para} What do you notice about the graphs? Describe any conclusions you have reached about computational complexity and energy ``complexity," along with any caveats to these conclusions.
\end{enumerate}
~\\
\noindent Your handed in solution to this homework should include:
\begin{enumerate}[a)]
\item The functions you wrote.
\item The values of $n$ you determined.
\item[\ref{graph})] Two graphs for each function (a total of 6 graphs).
\item[\ref{co2})] A sentence or two.
\item[\ref{para})] A short paragraph describing your conclusions.
\end{enumerate}
\end{document}