% Exam Template for UMTYMP and Math Department courses
%
% Using Philip Hirschhorn's exam.cls: http://www-math.mit.edu/~psh/#ExamCls
%
% run pdflatex on a finished exam at least three times to do the grading table on front page.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% These lines can probably stay unchanged, although you can remove the last
% two packages if you're not making pictures with tikz.
\documentclass[11pt]{exam}
\RequirePackage{amssymb, amsfonts, amsmath, latexsym, verbatim, xspace, setspace}
\RequirePackage{tikz, pgflibraryplotmarks}

% By default LaTeX uses large margins.  This doesn't work well on exams; problems
% end up in the "middle" of the page, reducing the amount of space for students
% to work on them.
\usepackage[margin=0.5in]{geometry}
\usepackage{multicol}
\usepackage{listings}
\usepackage{color}
\usepackage{qtree}
\usepackage{url}
\usepackage{censor,xcolor}
\censorruledepth=-.2ex
\censorruleheight=.1ex
%\usepackage{framed}
%\usepackage[usenames,dvipsnames]{xcolor}

\definecolor{mygreen}{rgb}{0,.4,0}
\definecolor{mygray}{rgb}{0.5,0.5,0.5}
\definecolor{mymauve}{rgb}{0.58,0,0.82}

\lstset{language=C++,
                basicstyle=\ttfamily,
                keywordstyle=\color{blue}\ttfamily,
                stringstyle=\color{mymauve}\ttfamily,
                commentstyle=\color{mygreen}\ttfamily,
                morecomment=[l][\color{magenta}]{\#},
                frame = single,
                numbers=left,
                numbersep=5pt,
                stepnumber=2
}

%\lstset{ %
%  backgroundcolor=\color{white},   % choose the background color; you must add \usepackage{color} or \usepackage{xcolor}
%  basicstyle=\footnotesize,        % the size of the fonts that are used for the code
%  breakatwhitespace=false,         % sets if automatic breaks should only happen at whitespace
%  breaklines=true,                 % sets automatic line breaking
%  captionpos=b,                    % sets the caption-position to bottom
%  commentstyle=\color{mygreen},    % comment style
%  deletekeywords={...},            % if you want to delete keywords from the given language
%  %escapeinside={\%*}{*)},          % if you want to add LaTeX within your code
%  extendedchars=true,              % lets you use non-ASCII characters; for 8-bits encodings only, does not work with UTF-8
%  frame=single,                    % adds a frame around the code
%  keepspaces=true,                 % keeps spaces in text, useful for keeping indentation of code (possibly needs columns=flexible)
%  keywordstyle=\color{blue},       % keyword style
%  language=Octave,                 % the language of the code
%  morekeywords={*,...},            % if you want to add more keywords to the set
%  numbers=left,                    % where to put the line-numbers; possible values are (none, left, right)
%  numbersep=5pt,                   % how far the line-numbers are from the code
%  numberstyle=\tiny\color{mygray}, % the style that is used for the line-numbers
%  rulecolor=\color{black},         % if not set, the frame-color may be changed on line-breaks within not-black text (e.g. comments (green here))
%  showspaces=false,                % show spaces everywhere adding particular underscores; it overrides 'showstringspaces'
%  showstringspaces=false,          % underline spaces within strings only
%  showtabs=false,                  % show tabs within strings adding particular underscores
%  stepnumber=2,                    % the step between two line-numbers. If it's 1, each line will be numbered
%  stringstyle=\color{mymauve},     % string literal style
%  tabsize=2,                       % sets default tabsize to 2 spaces
%  title=\lstname                   % show the filename of files included with \lstinputlisting; also try caption instead of title
%}
%\lstset{
% morekeywords={typename, template,int,long,char,double,unsigned}
%}

\usetikzlibrary{arrows}
\definecolor{cqcqcq}{rgb}{0.75,0.75,0.75}
\usetikzlibrary{arrows}

% Here's where you edit the Class, Exam, Date, etc.
\newcommand{\class}{CS 7A Final Exam }
\newcommand{\term}{Spring 2016}
\newcommand{\examnum}{Final Exam}
\newcommand{\examdate}{5/24/16}

% For an exam, single spacing is most appropriate
\singlespacing
% \onehalfspacing
% \doublespacing

% For an exam, we generally want to turn off paragraph indentation
\parindent 0ex

\begin{document} 

% These commands set up the running header on the top of the exam pages
\pagestyle{head}
\firstpageheader{}{}{}
\runningheader{\class}{\examnum\ - Page \thepage\ of \numpages}{\examdate}
\runningheadrule

\textbf{\class} - \textbf{\term} - \textbf{\examnum} \textbf{\examdate} \\
\rule[1ex]{\textwidth}{.1pt}
Write responses to questions 1 and 2 on this paper or attach additional sheets, as necessary.  For all subsequent problems, use separate paper.\\  
Assume the necessary libraries are included and appropriate namespaces are used.
\hfill



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% See http://www-math.mit.edu/~psh/#ExamCls for full documentation, but the questions
% below give an idea of how to write questions [with parts] and have the points
% tracked automatically on the cover page.
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\begin{lstlisting}
%
%\end{lstlisting}


\begin{questions}


%%%%%%%%%%%%%%%%%%
%%% 1

\question Write the number of the definition on the right next to the term it defines.\\  
\vspace*{2mm}
\begin{minipage}{4.5 cm}
\begin{parts}
\part  \textbf{object} \xblackout{number} %(10)
\vspace*{2mm}
\part \textbf{variable} \xblackout{number} %(6)
\vspace*{2mm} 
\part \textbf{function} \xblackout{numb} %(4)
\vspace*{2mm} 
\part \textbf{declaration} \xblackout{number} %(5)
\vspace*{2mm} 
\part \textbf{parameter} \xblackout{number} %(1)
\vspace*{2mm} 
\part \textbf{byte} \xblackout{number}  %(9)
\vspace*{2mm} 
\part \textbf{parser} \xblackout{number}%(8)
\vspace*{2mm} 
\part \textbf{scope} \xblackout{number} %(3)
\vspace*{2mm} 
\part \textbf{overload} \xblackout{num} %(2)
\vspace*{2mm} 
\part \textbf{type} \xblackout{number}%(11)
\vspace*{2mm} 
\part \textbf{reference} \xblackout{number} %(7)

\end{parts}
\end{minipage}
\begin{minipage}{12 cm}
\begin{itemize}
\item[(1)]  Some memory that holds a value of a given type.
\item[(2)]  The region of program text (source code) in which a name can be referred to.
\item[(3)] Defining two functions or operators with the same name but different argument (operand) types.
\item[(4)] A set of possible values and a set of operations (for an object).
\item[(5)] A declaration of an explicit input to a function through which a function can access the arguments passed by name.
\item[(6)] A value describing the location of a typed value in memory. 
\item[(7)] The specification of a name with its type in a program.
\item[(8)] A program that reads a stream of tokens according to a grammar.
\item[(9)] The basic unit of addressing in most computers.
\item[(10)] A named object of a given type; contains a value unless uninitialized.
\item[(11)] A named unit of code that can be invoked (called) from different parts of a program; a logical unit of computation.

\end{itemize}
\end{minipage}

%%%%%%%%%%%%%%%%%
%%% 2
\question Write a C++ program to implement the pseudocode:
\begin{verbatim}
Set total to zero
Set temperature counter to one
While temperature counter is less than or equal to ten
    Input the next temperature
    Add the temperature into the total
Set the average temperature to the total divided by ten
Print the average temperature.
\end{verbatim}

\newpage
%%%%%%%%%%%%%%%%%
%%% 3
\question Consider the following program:
\begin{lstlisting}
void getCoordinates(int&,int&,int&,int&);

int main() {
    int x1 = 1, y1 = 2, x2 = 3, y2 = 4;
    getCoordinates(x1, y1, x2, y2)
    //slope(/*parameters*/); //uncomment: print slope; specify input
}
void getCoordinates(int& x1, int& y1, int& x2, int& y2) 
{   cout << "\nEnter coordinates x1, y1, x2, y2, in that order: ";
    for(int i = 0; i < 4; i++)
    {	switch (i)  {
        case 0:
            cin >> x1; break;
        case 1:  
            cin >> y1; break;
        case 2:
            cin >> x2; break;
        case 3:
            cin >> y2; break;
        }
    }
}

\end{lstlisting}
\vspace*{6mm}
Remember to write your answers to these on separate paper.  
\begin{parts}
\part Why is the \texttt{\&} symbol used on line 7?  Explain what that means in that context and why it's needed.
\vspace*{6mm}
\part What single \texttt{cin} statement could replace the \texttt{for} loop and \texttt{switch} statement in \texttt{getCoordinates()}?
\vspace*{6mm}
\part Write code to define a \texttt{class Point} with two member variables \texttt{x} and \texttt{y} and a constructor, \texttt{Point(x,y)} to instantiate such a point. This allows you to create a \texttt{vector<Point>} which \texttt{getCoordinate()} can take as a reference parameter.   
\vspace*{6mm}
\part Rewrite \texttt{main()} and \texttt{getCoordinate()} to use a \texttt{vector<Point>} to get a \texttt{vector} of \texttt{100} \texttt{Point}s available for further processing in \texttt{main()}. 
\vspace*{6mm}
\part Write the function \texttt{slope(p1,p2)} to take two \texttt{Point} variables and return the slope of the line between them as a floating point approximation, or print an error message if the slope is undefined.  For instance, if \texttt{Point p1(1,2)} and \texttt{Point p2(3,5)} are passed to the \texttt{slope()} function, then it will print to the console
\begin{verbatim}
     The slope of the line from (1,2) to (3,5) is 1.5
\end{verbatim}
Whereas, if \texttt{Point p1(1,2)} and \texttt{Point p2(1,5)} are passed, it will print 
\begin{verbatim}
     The slope of the line from (1,2) to (1,5) is undefined.
\end{verbatim}
\vspace*{6mm}
\part Write the function \texttt{allSlopes()} that takes a \texttt{vector<Point>} and returns a count of the number of vertical lines and computes a \texttt{vector<double>} that contains all possible slopes between any two \texttt{Points} in the input \texttt{vector<Point>}.  
\end{parts}
%\end{framed}

\newpage
%%%%%%%%%%%%%%%%%
%%% 4
\question In the code below, suppose that \texttt{D=864} and \texttt{primes[1]=2}, etc., so that \texttt{primes[i]} is the ith prime. 
\begin{lstlisting}
int findGreatestSquF(int D) {
    int i = 1, returnVal = 1;
    while(D/primes[i] > sqrt(D)) 
    {   while(D%(primes[i]*primes[i])==0) 
        {   returnVal *= primes[i];
            D /= primes[i]*primes[i];
        }
        ++i;
    }
    return returnVal;
}
\end{lstlisting}
\begin{parts}
\part Complete that table below which threads the values of various quantities as the algorithm is executed:
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline 
\texttt{D} & \texttt{i} & \texttt{primes[i]} & \texttt{returnVal} & \texttt{D/primes[i]} & $\sqrt{D}$ & \texttt{D\%(primes[i]*primes[i])}  \\ 
\hline 
864 & 1 & 2 & 1 & 432 & 29.4 & 0 \\ 
\hline 
216 & 1 & • & • & • & 14.7 & • \\ 
\hline 
54 & 1 & • & • & • & 7.3 & • \\ 
\hline 
54 & • & • & • & • & 7.3 & • \\ 
\hline 
6 & 2 & 3 & • & • & 2.4 & • \\ 
\hline 
$\vdots$ & $\vdots$  & $\vdots$  & $\vdots$  & $\vdots$  & $\vdots$  & $\vdots$  \\ 
\hline 
\end{tabular} 
\part What value will \texttt{findGreatestSquF()} return for \texttt{D=864}?
%\part Write functions to overload the subtraction(-) and division(/) operators.
\end{parts}
\question Consider the following function.
\begin{lstlisting}
/// count the relative frequency of the alphabetic characters in a file 
void letterFreq(vector<double>& charFreqs) {
    ifstream ifs("file.txt");
    char ch;
    double counter{};
    while(ifs>>ch) {
        if(!isalpha(ch)) continue;
        ++counter;
        ch = toupper(ch);
        ++charFreqs[int(ch)-65];
    }
    for(int i = 0; i < charFreqs.size(); ++i)
        charFreqs[i] /= counter;
}
\end{lstlisting}
\begin{parts}
\part Describe the input parameter for this function.  What is it?  How must it be initialized in order to work properly here?
\part Describe what happens in line 3.
\part How will the \texttt{while} loop terminate here?
\part Describe what happens in line 7.
\part Describe what happens in line 10.
\part What will \texttt{vector<double> charFreqs} contain after return to the calling function if \texttt{file.txt} contains the single line\\
\vspace*{-5mm}
\begin{verbatim}
         Pack my box with five dozen liquor jugs.
\end{verbatim}
\vspace*{5mm}
According to Wikipedia, this sentence is used on NASA's Space Shuttle.
\end{parts}
\end{questions}
\end{document}
