Page Menu
Home
c4science
Search
Configure Global Search
Log In
Files
F94917504
Homework-Template.tex
No One
Temporary
Actions
Download File
Edit File
Delete File
View Transforms
Subscribe
Mute Notifications
Award Token
Subscribers
None
File Metadata
Details
File Info
Storage
Attached
Created
Wed, Dec 11, 09:34
Size
6 KB
Mime Type
text/x-tex
Expires
Fri, Dec 13, 09:34 (2 d)
Engine
blob
Format
Raw Data
Handle
22899563
Attached To
rMARAFFO Master-cycle
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}
Event Timeline
Log In to Comment