Page Menu
Home
c4science
Search
Configure Global Search
Log In
Files
F103022408
homework1.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, Feb 26, 14:13
Size
17 KB
Mime Type
text/x-tex
Expires
Fri, Feb 28, 14:13 (2 d)
Engine
blob
Format
Raw Data
Handle
24480816
Attached To
rMARAFFO Master-cycle
homework1.tex
View Options
\documentclass{article}
% Change "article" to "report" to get rid of page number on title page
\usepackage{amsmath,amsfonts,amsthm,amssymb}
\usepackage{setspace}
\usepackage{fancyhdr}
\usepackage{lastpage}
\usepackage{extramarks}
\usepackage{chngpage}
\usepackage{soul}
\usepackage[usenames,dvipsnames]{color}
\usepackage{graphicx,float,wrapfig}
\usepackage{ifthen}
\usepackage{listings}
\usepackage{courier}
\usepackage{makecell}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{wrapfig}
\usepackage{multicol}
\usepackage{float}
\usepackage{verbatim}
\usepackage[T1]{fontenc}
\usepackage{comment}
\usepackage{systeme}
\usepackage[table,xcdraw]{xcolor}
\usepackage{array}
\usepackage{physics}
% !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
%
% Here put your info (name, due date, title etc).
% the rest should be left unchanged.
%
%
%
% !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
% Homework Specific Information
\newcommand{\hmwkTitle}{Homework 1}
\newcommand{\hmwkSubTitle}{}
\newcommand{\hmwkDueDate}{\today}
\newcommand{\hmwkClass}{Algorithms}
\newcommand{\hmwkClassTime}{}
%\newcommand{\hmwkClassInstructor}{Prof. Oleg Yazyev}
\newcommand{\hmwkAuthorName}{Raffaele Ancarola}
%
%
% In case you need to adjust margins:
\topmargin=-0.45in %
\evensidemargin=0in %
\oddsidemargin=0in %
\textwidth=6.5in %
\textheight=9.5in %
\headsep=0.25in %
% This is the color used for comments below
\definecolor{MyDarkGreen}{rgb}{0.0,0.4,0.0}
% units of mesure
\usepackage{siunitx}
% comments
\usepackage{comment}
% pgfplots environment
%package setup for graphs
\usepackage{tikz}
\usepackage{pgfplots}
\usepackage{pgfplotstable}
\usetikzlibrary{patterns}
\usepgfplotslibrary{external}
\pgfplotsset{compat=newest}
%pgfplot setup
\makeatletter
\pgfplotsset{
/pgfplots/flexible xticklabels from table/.code n args={3}{%
\pgfplotstableread[#3]{#1}\coordinate@table
\pgfplotstablegetcolumn{#2}\of{\coordinate@table}\to\pgfplots@xticklabels
\let\pgfplots@xticklabel=\pgfplots@user@ticklabel@list@x
},
% layer definition
layers/my layer set/.define layer set={
background,
main,
foreground
}{
% you could state styles here which should be moved to
% corresponding layers, but that is not necessary here.
% That is why we don't state anything here
},
% activate the newly created layer set
set layers=my layer set
}
\makeatother
\IfFileExists{./tikzext.perm}{\tikzexternalize[prefix=tikzext/]}{\tikzexternalize}
% pfgplots add graphics
\makeatletter
\newcommand\addplotgraphicsnatural[2][]{%
\begingroup
% set options in this local group (will be lost afterwards):
\pgfqkeys{/pgfplots/plot graphics}{#1}%
% measure the natural size of the graphics:
\setbox0=\hbox{\includegraphics{#2}}%
%
% compute the required unit vector ratio:
\pgfmathparse{\wd0/(\pgfkeysvalueof{/pgfplots/plot graphics/xmax} - \pgfkeysvalueof{/pgfplots/plot graphics/xmin})}%
\let\xunit=\pgfmathresult
\pgfmathparse{\ht0/(\pgfkeysvalueof{/pgfplots/plot graphics/ymax} - \pgfkeysvalueof{/pgfplots/plot graphics/ymin})}%
\let\yunit=\pgfmathresult
%
% configure pgfplots to use it.
% The \xdef expands all macros except those prefixed by '\noexpand'
% and assigns the result to a global macro named '\marshal'.
\xdef\marshal{%
\noexpand\pgfplotsset{unit vector ratio={\xunit\space \yunit}}%
}%
\endgroup
%
% use our macro here:
\marshal
%
\addplot graphics[#1] {#2};
}
\makeatother
% For faster processing, load Matlab syntax for listings
\lstloadlanguages{Matlab}%
\lstset{language=Matlab, % Use MATLAB
frame=single, % Single frame around code
basicstyle=\small\ttfamily, % Use small true type font
keywordstyle=[1]\color{Blue}\bf, % MATLAB functions bold and blue
keywordstyle=[2]\color{Purple}, % MATLAB function arguments purple
keywordstyle=[3]\color{Blue}\underbar, % User functions underlined and blue
identifierstyle=, % Nothing special about identifiers
% Comments small dark green courier
commentstyle=\usefont{T1}{pcr}{m}{sl}\color{MyDarkGreen}\small,
stringstyle=\color{Purple}, % Strings are purple
showstringspaces=false, % Don't put marks in string spaces
tabsize=3, % 5 spaces per tab
breaklines=True,
%
%%% Put standard MATLAB functions not included in the default
%%% language here
morekeywords={xlim,ylim,var,alpha,factorial,poissrnd,normpdf,normcdf},
%
%%% Put MATLAB function parameters here
morekeywords=[2]{on, off, interp},
%
%%% Put user defined functions here
morekeywords=[3]{FindESS, homework_example},
%
morecomment=[l][\color{Blue}]{...}, % Line continuation (...) like blue comment
numbers=left, % Line numbers on left
firstnumber=1, % Line numbers start with line 1
numberstyle=\tiny\color{Blue}, % Line numbers are blue
stepnumber=1 % Line numbers go in steps of 5
}
% Setup the header and footer
\pagestyle{fancy} %
\lhead{\hmwkAuthorName} %
%\chead{\hmwkClass\ (\hmwkClassInstructor\ \hmwkClassTime): \hmwkTitle} %
\rhead{\hmwkClass\ : \hmwkTitle} %
%\rhead{\firstxmark} %
\lfoot{\lastxmark} %
\cfoot{} %
\rfoot{Page\ \thepage\ of\ \protect\pageref{LastPage}} %
\renewcommand\headrulewidth{0.4pt} %
\renewcommand\footrulewidth{0.4pt} %
% This is used to trace down (pin point) problems
% in latexing a document:
%\tracingall
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Some tools
\newcommand{\enterProblemHeader}[1]{\nobreak\extramarks{#1}{#1 continued on next page\ldots}\nobreak%
\nobreak\extramarks{#1 (continued)}{#1 continued on next page\ldots}\nobreak}%
\newcommand{\exitProblemHeader}[1]{\nobreak\extramarks{#1 (continued)}{#1 continued on next page\ldots}\nobreak%
\nobreak\extramarks{#1}{}\nobreak}%
\newlength{\labelLength}
\newcommand{\labelAnswer}[2]
{\settowidth{\labelLength}{#1}%
\addtolength{\labelLength}{0.25in}%
\changetext{}{-\labelLength}{}{}{}%
\noindent\fbox{\begin{minipage}[c]{\columnwidth}#2\end{minipage}}%
\marginpar{\fbox{#1}}%
% We put the blank space above in order to make sure this
% \marginpar gets correctly placed.
\changetext{}{+\labelLength}{}{}{}}%
\setcounter{secnumdepth}{0}
\newcommand{\homeworkProblemName}{}%
\newcounter{homeworkProblemCounter}%
\newenvironment{homeworkProblem}[1][Problem \arabic{homeworkProblemCounter}]%
{\stepcounter{homeworkProblemCounter}%
\renewcommand{\homeworkProblemName}{#1}%
\section{\homeworkProblemName}%
\enterProblemHeader{\homeworkProblemName}}%
{\exitProblemHeader{\homeworkProblemName}}%
\newcommand{\problemAnswer}[1]
{\noindent\fbox{\begin{minipage}[c]{\columnwidth}#1\end{minipage}}}%
\newcommand{\problemLAnswer}[1]
{\labelAnswer{\homeworkProblemName}{#1}}
\newcommand{\homeworkSectionName}{}%
\newlength{\homeworkSectionLabelLength}{}%
\newenvironment{homeworkSection}[1]%
{% We put this space here to make sure we're not connected to the above.
% Otherwise the changetext can do funny things to the other margin
\renewcommand{\homeworkSectionName}{#1}%
\settowidth{\homeworkSectionLabelLength}{\homeworkSectionName}%
\addtolength{\homeworkSectionLabelLength}{0.25in}%
\changetext{}{-\homeworkSectionLabelLength}{}{}{}%
\subsection{\homeworkSectionName}%
\enterProblemHeader{\homeworkProblemName\ [\homeworkSectionName]}}%
{\enterProblemHeader{\homeworkProblemName}%
% We put the blank space above in order to make sure this margin
% change doesn't happen too soon (otherwise \sectionAnswer's can
% get ugly about their \marginpar placement.
\changetext{}{+\homeworkSectionLabelLength}{}{}{}}%
\newcommand{\sectionAnswer}[1]
{% We put this space here to make sure we're disconnected from the previous
% passage
\noindent\fbox{\begin{minipage}[c]{\columnwidth}#1\end{minipage}}%
\enterProblemHeader{\homeworkProblemName}\exitProblemHeader{\homeworkProblemName}%
\marginpar{\fbox{\homeworkSectionName}}%
% We put the blank space above in order to make sure this
% \marginpar gets correctly placed.
}%
%%% I think \captionwidth (commented out below) can go away
%%%
%% Edits the caption width
%\newcommand{\captionwidth}[1]{%
% \dimen0=\columnwidth \advance\dimen0 by-#1\relax
% \divide\dimen0 by2
% \advance\leftskip by\dimen0
% \advance\rightskip by\dimen0
%}
% Includes a figure
% The first parameter is the label, which is also the name of the figure
% with or without the extension (e.g., .eps, .fig, .png, .gif, etc.)
% IF NO EXTENSION IS GIVEN, LaTeX will look for the most appropriate one.
% This means that if a DVI (or PS) is being produced, it will look for
% an eps. If a PDF is being produced, it will look for nearly anything
% else (gif, jpg, png, et cetera). Because of this, when I generate figures
% I typically generate an eps and a png to allow me the most flexibility
% when rendering my document.
% The second parameter is the width of the figure normalized to column width
% (e.g. 0.5 for half a column, 0.75 for 75% of the column)
% The third parameter is the caption.
\newcommand{\scalefig}[3]{
\begin{figure}[ht!]
% Requires \usepackage{graphicx}
\centering
\includegraphics[width=#2\columnwidth]{#1}
%%% I think \captionwidth (see above) can go away as long as
%%% \centering is above
%\captionwidth{#2\columnwidth}%
\caption{#3}
\label{#1}
\end{figure}}
% Includes a MATLAB script.
% The first parameter is the label, which also is the name of the script
% without the .m.
% The second parameter is the optional caption.
\newcommand{\matlabscript}[2]
{\begin{itemize}\item[]\lstinputlisting[caption=#2,label=#1]{#1.m}\end{itemize}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Make title
%\title{\vspace{2in}\textmd{\textbf{\hmwkClass:\ \hmwkTitle\ifthenelse{\equal{\hmwkSubTitle}{}}{}{\\\hmwkSubTitle}}}\\\normalsize\vspace{0.1in}\small{Due\ on\ \hmwkDueDate}\\\vspace{0.1in}\large{\textit{\hmwkClassInstructor\ \hmwkClassTime}}\vspace{3in}}
%\title{\vspace{2in}\textmd{\textbf{\hmwkClass:\ \hmwkTitle\ifthenelse{\equal{\hmwkSubTitle}{}}{}{\\\hmwkSubTitle}}}\\\normalsize\vspace{0.1in}\small{Due\ on\ \hmwkDueDate}\\\vspace{0.1in}\large{\textit{ \hmwkClassTime}}\vspace{3in}}
\title{\textmd{\textbf{\hmwkClass:\ \hmwkTitle\ifthenelse{\equal{\hmwkSubTitle}{}}{}{\\\hmwkSubTitle}}}\\\normalsize\vspace{0.1in}\small{Due\ on\ \hmwkDueDate}\\\vspace{0.1in}\large{\textit{ \hmwkClassTime}}}
\date{\today}
\author{\textbf{\hmwkAuthorName}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
%\begin{spacing}{1.1}
\maketitle
% Uncomment the \tableofcontents and \newpage lines to get a Contents page
% Uncomment the \setcounter line as well if you do NOT want subsections
% listed in Contents
%\setcounter{tocdepth}{1}
%\newpage
%\tableofcontents
%\newpage
% When problems are long, it may be desirable to put a \newpage or a
% \clearpage before each homeworkProblem environment
%\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{homeworkProblem}
\begin{homeworkSection}{(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.
\end{homeworkSection}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{homeworkSection}{(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.
\end{homeworkSection}
\begin{homeworkSection}{(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}
\caption{SumLeast}
\label{sumleast}
\begin{algorithmic}
\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$ \Comment{Base case}
\ElsIf {k > n}
\State \textbf{Error} "Heap underflow"
\EndIf
\\
\State Let $S$ be a min priority queue
\\
\State $sum = 0$
\\
\For {$j = k$ downto $1$}
\If {j == k}
\State $(m, i) = \text{extract\_min}(S)$
\Else
\State $(m, i) = (A[1], 1)$ \Comment{First index, S is still empty}
\EndIf
\\
\State sum = sum + m
\\
\State r = right(i) \Comment{Evaluate children of A}
\State l = left(i)
\If {$r \le n$}
\State insert$(S, (A[r], r))$
\EndIf
\If {$l \le n$}
\State insert$(S, (A[l], l))$
\EndIf
\EndFor
\\
\Return sum
\end{algorithmic}
\end{algorithm}
\end{homeworkSection}
\end{homeworkProblem}
%\end{spacing}
\end{document}
Event Timeline
Log In to Comment