Homec4science
Diffusion Master-cycle (master) Browse

master-raffo/algorithm/homework/Homework-Template.tex
f72f0429dcd1master

Last Change
Raw File

Homework-Template.tex
View Options

\documentclass{article}
\usepackage[margin=1in,a4paper]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[fleqn]{amsmath}
\usepackage{gensymb}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{mathtools}
\usepackage{array}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{tabularx}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{nicefrac}
\usepackage[boxed,vlined]{algorithm2e}
\usepackage{cleveref}
\pagestyle{fancy}
\fancyhf{}
\rhead{CS-250}
\chead{Homework 1}
\lhead{Ancarola, Raffaele (287031)}
\rfoot{Page \thepage}
\begin{document}
\begin{flushleft}
%\begin{algorithm}
%\DontPrintSemicolon
%
% Let $d$ be something... \;
% \For{i = 1 to 100} {
% \For{j = 1 to 100}{
% \If{something is true} {
% d[i,j] $\gets$ $\texttt{random()}$ \;
% }\Else{
% d[i,j] $\gets 0$ \;
% }
% }
% }
%
%\end{algorithm}
%
\subsection*{Problem 1}
\subsubsection*{1a}
This algorithm returns the product over all elements of an array, then for an input array $A$ and index boundaries $l$, $r$:
\begin{equation}
\text{UNKNOWN}(A, l, r) = \prod_{i=l}^r A_i
\end{equation}
For the given array $A$, $\text{UNKNOWN}(A, 1, 8) = 241920$.
\subsubsection*{1b}
The expression of $q$ suggests that the recursion splits the array into $\frac{n}{4}$ on the left side
and $\frac{3n}{4}$ on the right side. The other operations take constant time, then
\begin{equation}
T(n) = \Theta(1) + T(\frac{n}{4}) + T(\frac{3n}{4})
\end{equation}
\subsubsection*{1c}
\paragraph{Guess:} $T(n) = \Theta(n)$
\paragraph{Upper bound:} prove that it exists $C_u$ such that $\forall m < n : T(m) \le C_u m - 1$, then
\begin{align}
T(n) &= 1 + T(\frac{n}{4}) + T(\frac{3n}{4}) \\
& \le 1 + C_u \frac{m}{4} - 1 + C_u \frac{3m}{4} - 1 \\
& = C_u m - 1
\end{align}
thus $T(n) = \mathcal{O}(n)$.
\paragraph{Lower bound:} prove that it exists $C_l$ such that $\forall m < n : T(m) \ge C_l m$, then
\begin{align}
T(n) &= 1 + T(\frac{n}{4}) + T(\frac{3n}{4}) \\
& \ge 1 + C_l \frac{m}{4} + C_l \frac{3m}{4} \\
& \ge C_l m
\end{align}
thus $T(n) = \Omega(n)$, which finally proves the initial guess.
\newpage
\subsection*{Problem 2}
For a given weight limit $m$ and number of categories $k$, the choise
of the gift over the last category depends on which one maximizes happiness
with respect to previous configurations allowing less weight.
More specifically, let $h_{ki}$ and $w_{ki}$ be the happiness and respectively the weight of the $i^{th}$ gift over the category $k$.
Because the problem imposes that the weight is limited to $m$, for any $i^{th}$ gift the happiness should be maximized
considering that it takes a weight of $w_{ki}$, thus the optimal solution for $k-1$ should be evaluated with a weight limit of $m - w_{ki}$.
This way the $k^{th}$ never exceedes the weight limits and in case there's no gift maximing the happiness,
the previous $(k-1)^{th}$ optimal solution is taken allowing the weight $m$.
Let $H(k,m)$ be the optimal solution for given $k$ and $m$, then the recurrence relation could be written as follow:
\begin{equation}
H(k,m) =
\begin{cases}
0 & \text{if } k = 0 \text{ or } m = 0 \\
\forall \; 1 \le i \le k_i : \max\limits_{w_{ki} \le m} (h_{ki} + H(k-1, m - w_{ki}), H(k-1, m)) & \text{otherwise}
\end{cases}
\end{equation}
Here is supposed that neither $k$ nor $m$ can be negative. The $\forall \; 1 \le i \le k_i$ instruction indicates
that the maximum must be evaluated over all $i$ and over $H(k-1,m)$ too.
\newpage
\subsection*{Problem 3}
The algorithm (\ref{sumleast}) computes the sum of the $k$ smallest elements of $A$.
The main strategy consists in passing through a min. priority queue $S$ and iteratively allocate it with
the smallest elements of $A$.
\paragraph{Recall, min. priority queue}: a structure which the following functionalities are defined for:
\begin{itemize}
\item \texttt{minimum}$(S)$: get the minimum element
\item \texttt{extract\_min}$(S)$: get the minimum element and delete it from the queue
\item \texttt{insert}$(S, x)$: insert an element $x$ into the queue
\end{itemize}
Taking a heap implementation of the min. priority queue, there would be an addictional
parameter $k$ corresponding to the size of $S$ but it's implicitly stocked within the object.
About the time complexity, both \texttt{extract\_min} and \texttt{insert} take are supposed to take $\theta(\log(k))$.
\paragraph{Elements of $S$}
In this case, an element of $S$ is a couple of values $(m, i)$ such that $m = A[i]$.
The comparison between two elements is defined as $(m_1, i_1) < (m_2, i_2) \iff m_1 < m_2$.
\paragraph{Correctness}
The principle of a min. heap is that the parent node is smaller than the children.
The initialization inserts $A[0]$ into the empty $S$, then $S$ contains only the minimum value of $A$.
Concearning the loop, $(m, i)$ always corresponds the minimum over $S$, so verify that it's really the next minimum of $A$.
To ensure that the next minimum is taken, the children $A[right(i)]$ and $A[left(i)]$ are inserted into $S$ and
the priority queue will then min-heapify in order to get the minimum over its elements to the top.
This way there's no possibility of skipping minimums because children are pre-selected as candidates and so
$S$ is always holding at its top the next minimum of $A$.
Finalisation: as $sum$ collects the sum over all $m$ inside the loop, then it corresponds to the sum over the $k$ smallest values of $A$.
\paragraph{Efficiency}
As iterating $k$ times and performing $\theta(\log(k))$ operations inside the loop, then
the it results in $\theta(k\log(k))$.
\begin{algorithm}
\DontPrintSemicolon
\caption{SumLeast(A, k, n)}
\label{sumleast}
%\Require $A$ as min heap, $k \ge 0$, $n \ge 0$
%\Ensure Sum over the least $k$ elements of $A$
\If {$k == 0$ or $n == 0$} {
\Return $0$ %\\\\ Base case
} \ElseIf {k > n} {
\textbf{Error} "Heap underflow"
}
Let $S$ be a min priority queue
$sum = 0$
\For {$j = k$ downto $1$} {
\If {j == k} {
$(m, i) = \text{extract\_min}(S)$
} \Else {
$(m, i) = (A[1], 1)$ %\Comment{First index, S is still empty}
}
sum = sum + m
r = right(i) %\Comment{Evaluate children of A}
l = left(i)
\If {$r \le n$} {
insert$(S, (A[r], r))$
}
\If {$l \le n$} {
insert$(S, (A[l], l))$
}
}
\Return sum
\end{algorithm}
% YOUR ANSWER
\end{flushleft}
\end{document}
c4science · Help