\documentclass{assignment-263}

\usepackage{color}

\usepackage{mathtools}
\anum{2}
\course{CSC263}
\duedate{Thursday, February 27, 2020}
\filename{ps2sol.pdf, ps2sol.tex and triangle.py}

\newcommand{\bigOh}{\mathcal{O}}

\begin{document}
\think

  \begin{enumerate}

%  
\item[1.] \textbf{[total: 6]}
  You are given an array $\texttt{A}$ that contains $n$ \textbf{distinct}
  numbers. The task is to compute another array $\texttt{B}$ such that for all
  $\texttt{j},$ we want $\texttt{B[j]}$ to be the number of elements in
  $\texttt{A}$ that appear after $\texttt{A[j]}$ and are strictly
  smaller than $\texttt{A[j]}.$

  As an example, if you are given the input array
  $\texttt{A = [8, 10, 4, 7, 3, 5, 9, 1]},$ then you want to output
  the array $\texttt{B = [5, 6, 2, 3, 1, 1, 1, 0]}.$ This is because,
  in $\texttt{A},$ there are 5 elements that appear after
  $\texttt{A[0] = 8}$ and are smaller than \texttt{8} (i.e. \texttt{4,
    7, 3, 5, 1}), there are 6 elements that appear after
  $\texttt{A[1] = 10}$ and are smaller than \texttt{10}
  (i.e. \texttt{4, 7, 3, 5, 9, 1}), etc.
  

  Design an algorithm to compute $\texttt{B}$ given $\texttt{A}$ as
  input. The \textbf{worst case} complexity of your algorithm
  \textbf{must be $\bigOh(n\log n)$}.

  This algorithm can be described in brief given what we have learned
  in class. 
  
  Write a clear description of your algorithm (what data structure is
  used and how the algorithm utilizes the data structure) and justify
  its correctness and runtime. As usual, please use learned algorithms
  and analysis results from lectures and tutorials without repeating
  them.

  \item[2.] \textbf{[total: 6]} Suppose that we want to generate a BST by
  inserting the keys 1 through $n$ into an initially empty BST (assume
  $n > 1$). Assume that the insert sequence is a random permutation of
  $[1,2,3,\dots, n]$ and each permutation is equally likely to
  occur. Answer the following questions.
  %
  \begin{enumerate}[(a)]

  \item What is the maximum possible height of the generated BST?
    Describe \textbf{four} different insert sequences that would
    result in a BST with the maximum height.

  \item By picking a random permutation of $[1,2,3,\dots, n]$ as the
    insert sequence, what is the probability that the resulting BST
    has the maximum height? Show detailed steps of your calculation
    with clear justification.
  \end{enumerate}
  
\item[3.] \textbf{[total: 12]} In this problem, you will design the data
  structure for implementing an ADT called
  \texttt{RESTAURANT-SET}. Below is the description of the ADT.
  \begin{description}
  \item[Objects:] A collection of restaurants in the same city. Each
    \texttt{restaurant} has the following attributes:
    \begin{itemize}
    \item \texttt{restaurant.name}: a string which is the name of the
      restaurant. Each restaurant has a unique name, i.e., no two
      restaurants have the same name.
    \item \texttt{restaurant.cost}: a decimal value such as $22.99$
      that denotes the cost of a 1 person meal at the restaurant.  For
      simplicity, assume that each restaurant's cost is unique,
      i.e., no two restaurants have the same cost.
    \item \texttt{restaurant.rating}: a decimal value between $0.0$ and
      $5.0$, e.g., $0.012$, $3.1415926$. For simplicity, assume that
      each restaurant's rating value is unique, i.e., no two
      restaurants have the same rating value.
    \end{itemize}
  \item[Operations:] \mbox{}
    \begin{itemize}
      %
    \item \texttt{GET-RESTAURANT(R, name)}: returns the restaurant
      with name \texttt{name} if it exists in the
      \texttt{RESTAURANT-SET R}; returns \texttt{NIL} if the restaurant
      does not exist in \texttt{R}.
      %
    \item \texttt{ADD-RESTAURANT(R, restaurant)}: Add a restaurant
      \texttt{restaurant} to the \texttt{RESTAURANT-SET R}. You may
      assume that \texttt{restaurant} has a unique name, a unique
      cost and a unique rating.
    \item \texttt{AVG-COST(R, r1, r2),\ r1 $\le$ r2}: considers all
      restaurants that have a rating $\texttt{r}$ such that
      $\texttt{r1} \le \texttt{r} < \texttt{r2},$ and returns the
      average of the meal costs over all these restaurants.

      e.g. If \texttt{R} contains the following restaurants:
      \texttt{(A, 22, 3), (B, 35, 4.5), (C, 24, 3.9), (D, 30, 4)}
      where each tuple represents \texttt{(name, cost, rating)}, then
      the query \texttt{AVG-COST(R, 3, 4)} must return the average of
      the costs of restaurants that have ratings $\ge 3$ and $< 4,$
      which are \texttt{A} and \texttt{C}. Thus it must return
      $\frac{22 + 24}{2} = 23.$
    \end{itemize}
    %
  \item[Requirements:] Let $n$ be the size of $R$,
    \begin{itemize}
    \item \texttt{GET-RESTAURANT(R, name)} must have average-case runtime
      $\mathcal{O}(1)$.
    \item \texttt{ADD-RESTAURANT(R, restaurant)} must have
      \textbf{\color{red} average-case} runtime $\mathcal{O}(\log n)$.
    \item \texttt{AVG-COST(R, r1, r2)} must have worst-case runtime
      $\mathcal{O}(\log n)$.
    \end{itemize}
  \end{description}

  Give a \emph{detailed} description of the design of your data
  structure by answering the following questions.

  \begin{enumerate}[(a)]
  \item \textbf{[2]} Which data structure(s) do you use in your design? What is the
    key of each data structure? What attributes does each node in your
    data structure(s) keep?

  \item \textbf{[2]} Explain concisely in English how your \texttt{GET-RESTAURANT}
    operation works, and justify its runtime.

  \item \textbf{[2]} Explain concisely in English how your \texttt{ADD-RESTAURANT}
    operation works, and justify its runtime. In particular, explain
    why all the attributes kept in each node can be maintained
    efficiently upon the addition of the new node.

  \item \textbf{[6]} Explain how your \texttt{AVG-COST} operation works and
    \textbf{write the pseudocode} of this operation, then justify its
    runtime.
  \end{enumerate}

  \textbf{Note}: As usual, please do \textbf{not} repeat algorithm
  details or runtime analyses from class or the textbook --- just
  directly refer to known results as needed.


  

\program

\item[4.] \textbf{[total: 12]}
  In this problem, we will deal with the notion
  of \textbf{pseudo-similar} triangles.

  Each triangle is represented by a 3-tuple of positive numbers,
  specifying the sides of the triangle.

  We say that two triangles \texttt{t1} and \texttt{t2} are
  \textbf{pseudo-similar} if triangle \texttt{t2} can be obtained by
  rotating and reflecting triangle \texttt{t1}.

  For example, $\texttt{t1 = (6, 9, 12)}$ is \textbf{pseudo-similar}
  to $\texttt{t2 = (6, 12, 9)}$ since \texttt{t2} can be obtained by
  rotating and reflecting \texttt{t1}.
%
  \[ \texttt{(6, 9, 12)}
    \xrightarrow{\text{rotate}} \texttt{(9, 12, 6)}
    \xrightarrow{\text{reflect}} \texttt{(6, 12, 9)}
  \]

  However, $\texttt{t1 = (6, 9, 6)}$ is not \textbf{pseudo-similar} to
  $\texttt{t2 = (6, 9, 9)}.$

  We say that two triangles are the same {\bf kind} if they are
  \textbf{pseudo-similar}.

  In Python, a triangle will be represented as a 3-tuple of positive
  integers.

  Your task is to write the function \verb|num_triangle_kinds|, which
  determines the \textbf{number} of different kinds of triangles in
  the list. \textbf{(8 points)}


Requirements:
\begin{itemize}
\item Your code must be written in Python 3, and the filename must be \verb|triangle.py|.
\item We will grade only the \verb|num_triangle_kinds| function; please do not change its signature in the starter code. include as many helper functions as you wish.
   \item You are {\bf not} allowed to use the built-in Python
			dictionary or set.
			\item To get full marks, your algorithm must have average-case runtime
				$\mathcal{O}(n)$. You can assume Simple Uniform Random Hashing.
   \end{itemize}

\textbf{Write-up (4 points)}: in your \verb|ps2.pdf/ps2.tex| files, include the following: an explanation of how your code works, justification of correctness, and
 justification of desired $\mathcal{O}(n)$ average-case runtime.

 \end{enumerate}

\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
