\documentclass[11pt]{article} \usepackage{epsfig,amssymb} \pagestyle{empty} % \topmargin -2cm % \oddsidemargin -5mm % \evensidemargin -5mm % \textwidth 17cm % \textheight 9.5in % \setlength{\parindent}{0pt} % \newcommand{\be}{\begin{enumerate}} \newcommand{\ee}{\end{enumerate}} \begin{document} \begin{center} {\Large\bf CSE 310\hfill Homework1 \hfill Fall 2010}\\ \vspace{0.1in} \hspace{-0.5in} {\Large \bf (Pretest)}\\ \vspace{0.1in} {\large Due 1:30PM Wednesday, September 15} \end{center} \hrule \vspace{.75cm} \hfill Name\rule{2in}{.001in}\\ \hfill Student ID \rule{2in}{.001in}\\ \textbf{Instructions} Follow instructions \emph{carefully}, failure to do so will result in points being deducted. It is highly recommended that you write your homework using \LaTeX\ or Word. Staple this cover page to the front of your assignment for easier grading. Be sure to submit a hardcopy of your problem answers and your program analysis in class. Clearly label each problem and submit the answers in order. Put your program analysis to the end. In addition, submit your homework including all the program files via the webhandin (\texttt{http://www.cse.unl.edu/\~{}cse310/handin}). Late homework policy specified in course syllabus \emph{will be strictly followed}. Be sure to show \emph{sufficient work} to justify your answer(s). Numerical answers with no explanation will NOT be granted full points. If you are asked to prove something, you must give as formal, rigorous, and complete proof as possible. You are to work individually, and all work should be your own. The CSE academic dishonesty policy is in effect (\texttt{http://cse.unl.edu/undergrads/academic\_integrity.php}). \vspace{0.1in} ~~~~~\begin{tabular}{|l|l||l|} \hline Problem & Points & Score \\ \hline 1 & 10 & ~~ \\ \hline 2 & 10 & ~~ \\ \hline 3 & 5 & ~~ \\ \hline 4 & 10 & ~~ \\ \hline 5 & 15 & ~~ \\ \hline %Program \multicolumn{2}{|l}{Program} & ~\\ \hline Correctness & 30 & ~~ \\ \hline Style/Doc & 10 & ~~ \\ \hline Analysis & 10 & ~~ \\ \hline\hline Total & 100 & \\ \hline \end{tabular}\\ \textbf{Problems} \be \item Use \emph{mathematical induction} to prove that $ 1 \times 2 \times 3 + 2 \times 3 \times 4 + \dots + n(n+1)(n+2) = n (n+1)(n+2)(n+3) / 4. $ \newpage \item How many strings of three decimal digits \be \item do not contain the same digit three times? \item begin with an odd digit? \item have exactly two digits that are 4s? \ee \vspace{7cm} \item There are 38 different time periods during which classes at a university can be scheduled. If there are 677 different classes, how many different rooms will be needed? \newpage \item A computer company is selling 90 PC's with the following optional features: (i) Windows XP (ii) CD-RW (iii) 27-inch monitors. Among these PC,\vspace{-2mm} \begin{itemize} \item 72 have at least one of the options (i) or (ii).\\[-.6cm] \item 18 have both options (i) and (ii).\\[-.6cm] \item 45 have option (iii).\\[-.6cm] \item 36 have at least two of the options (i), (ii) or (iii).\\[-.6cm] \item 72 {\em do not} have at least one of the options (i) or (ii) or (iii). \end{itemize} \be \item How many PC's have options (i) and (ii) but not (iii)? \vspace{7cm} \item How many PC's have at least one of the options (i), (ii) or (iii)? \ee \newpage \item Order the following functions according to their order of growth (from the lowest to the highest). (n-2)!, $5lg(n+100)^{10}$, $2^{2n}$, $0.001n^4+3n^3+1$, $ln^2n$, $\sqrt[3]{n}$, $3^n$. \vspace{3cm} \ee \section*{Program} The goal of the program will be to implement a simulation of a \emph{priority queue} data structure using two stack data structures. You may not implement the priority queue directly. Recall that a priority queue, rather than being FIFO dequeues the element with the highest priority. You must first figure out how to implement the \textbf{enqueue} and \textbf{dequeue} operations of the queue in terms of the \textbf{push} and \textbf{pop} operations of the two stacks. There are clever ways of doing this, but efficiency will not be an issue, only correctness. The queue will only hold data of the \texttt{int} type but should have no maximum size. Further, the maximum priority will be the smallest valued integer. You should define and implement all data structures yourself, \emph{do not use predefined libraries}.\\ Your program must be written in C++, execute correctly on the CSE unix environment, and compile using the \texttt{g++} compiler using a \texttt{makefile}. Specifically, you will hand in the following files: \begin{itemize} \item \texttt{makefile} -- the makefile to compile your program into an executable called \texttt{mypriorityqueue} \item \texttt{main.cpp} -- the main program that will parse an input file (see below) \item \texttt{stack.h} -- the header file for the \texttt{stack} class. \item \texttt{stack.cpp} -- the implementation of your \texttt{stack} class. \item \texttt{Pqueue.h} -- the header file for the \texttt{Pqueue} class. \item \texttt{Pqueue.cpp} -- the implementation file for your \texttt{Pqueue} class. \end{itemize} Be sure to follow the file naming conventions listed above. In addition, you must follow the function naming conventions listed below. These functions are a minimum of what you must include in your class, you may define other member functions as you wish. Your \texttt{stack} class will have the following member functions (note that a default constructor is also required). \begin{itemize} \item \texttt{void push(int x)} -- the push function. \item \texttt{int pop()} -- the pop function. \item \texttt{bool is\_empty} -- a boolean test to see if the stack is empty. \end{itemize} If a \texttt{pop} operation is performed on an empty stack, \emph{no error message should be echoed}, instead it should have no effect at all. Your \texttt{Pqueue} class will have the following member functions, again a default constructor is implied. \begin{itemize} \item \texttt{void enqueue(int x)} -- enqueue the integer x. If x is already in the queue, it should have no effect, thus the priority queue should have \emph{all unique elements} \item \texttt{int dequeue()} -- dequeue the element with the highest priority (the smallest valued integer). \end{itemize} The \texttt{main.cpp} program should take input from a file via the command line (example: \texttt{prompt:>mypriorityqueue inputfile}) with the following structure in the input file (you may assume that all input file will be well structured so you don't have to error check the input). \begin{itemize} \item \texttt{enq x} which should perform the operation \texttt{enqueue(x)} \item \texttt{deq} which should dequeue the first element in the queue. If the queue is empty then the command is ignored (do not echo an error). \item \texttt{print} which should output (to the standard output) the current contents of the queue. Since its a priority queue, the order does not matter but the entire contents should be printed to a single line delimited by single spaces. If the queue is empty then simply output \texttt{empty}. Note, this command should not affect the queue contents, simply print them. \end{itemize} An example of an input file is as follows:\\ \verb"enq 5"\\ \verb"enq 10"\\ \verb"deq"\\ \verb"enq 3"\\ \verb"print"\\ %5, 3 \verb"enq 4"\\ \verb"deq"\\ \verb"enq 50"\\ \verb"print"\\ %50, 4, 3 \verb"deq"\\ \verb"print"\\ %4, 3 \verb"deq"\\ \verb"deq"\\ \verb"print"\\ %empty Proper output should look (something) like:\\ \verb"10 3"\\ \verb"4 10 50"\\ \verb"10 50"\\ \verb"empty"\\ Points will be awarded based on the following categories: \begin{itemize} \item \textbf{Correctness} -- Your code should execute as described above, naming conventions should be followed. You must include a makefile that will compile your code into an executable. \item \textbf{Style/Documentation} -- Your code should be readable, properly indented and spaced with sufficient comments to explain. Generally good Object Oriented style should be followed including separation of header/implementation files, appropriate naming of methods and variables, etc. \item \textbf{Analysis} -- Write a \texttt{brief} analysis of how your program works. In particular you should describe how your priority queue was implemented using the two stacks. Try to discuss how much more complicated the operations are over the usual implementations of priority queues. Discuss any pitfalls that you faced and any other relevant issues. \end{itemize} \end{document}