%!TEX TS-program = xelatex
%!TEX encoding = UTF-8 Unicode

\documentclass[a4paper,leqno]{article}

% ========================================================================================
% Packages
% ========================================================================================

\usepackage{amsmath,amssymb,amsthm}
\usepackage{mathtools}
\usepackage{booktabs}
\usepackage{units}

\usepackage{fancyvrb}
\fvset{fontsize=\normalsize}    % default font size for fancy-verbatim environments

\usepackage{graphicx}
\setkeys{Gin}{width=\linewidth,totalheight=\textheight,keepaspectratio}
\graphicspath{{graphics/}}

% ========================================================================================
% Fonts and hyphenation. Change the fonts to suit your needs.
% ========================================================================================

\usepackage{fontspec}
\setmainfont{Times New Roman}
\setmonofont{Courier New}

\usepackage{polyglossia}
\setmainlanguage[variant=usmax]{english}

% ========================================================================================
% Typeset pseudocode in the style of Introduction to Algorithms, Third edition
% ========================================================================================

\usepackage{clrscode3e}

% ========================================================================================
% Theorems and such
% ========================================================================================

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}

% ========================================================================================
% User-defined commands
% ========================================================================================

\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}

% ========================================================================================
% Article data
% ========================================================================================

\title{MEM291 Design and Analysis of Algorithms}
\author{Firstname Lastname}

% ========================================================================================
% Begin
% ========================================================================================

\begin{document}

% ========================================================================================
% Title page
% ========================================================================================

\maketitle

% ========================================================================================
% Main body
% ========================================================================================

\section*{\LaTeX\, sampler}

A simple equation:
\[
 f(x)=(x+a)(x+b)
\]
A numbered equation
\begin{equation}
    k_{n+1} = n^2 + k_n^2 - k_{n-1}
\end{equation}
Greek letters
$$
alpha,  \beta,  \gamma, \Gamma, \pi, \Pi, \phi, \varphi, \mu, \Phi, \xi, \zeta 
$$
Trig functions
$$
\cos(2\theta\phi) = \cos^2 \theta\phi - \sin^2 \theta\phi
$$
Delimiters
\begin{gather*}
\left(a+b\right)\left[1-\frac{b}{a+b}\right]=a\\
\sqrt{|xy|}\leq\left|\frac{x+y}{2}\right|\\
\int_a^bu\frac{d^2v}{dx^2}\,dx =\left.u\frac{dv}{dx}\right|_a^b -\int_a^b\frac{du}{dx}\frac{dv}{dx}\,dx
\end{gather*}
Matrices
$$
\begin{bmatrix}
1 & x & 0 \\
0 & 1 & -1
\end{bmatrix}
\begin{bmatrix}
1\\
y\\
1
\end{bmatrix}
=\begin{bmatrix}
1+xy\\
y-1
\end{bmatrix}.
$$
Case statements
\begin{equation}
|x|=\begin{cases}
x, & \text{if } x\ge 0\\
-x, & \text{if } x < 0
\end{cases}
\end{equation}
Multi-line equations
$$
\begin{aligned}
    F = & \{F_{x} \in  F_{c} : (|S| > |C|) \\
      &\quad \cap (\mathrm{minPixels}  < |S| < \mathrm{maxPixels}) \\
      &\quad \cap (|S_{\mathrm{conected}}| > |S| - \epsilon) \}
\end{aligned}
$$
Theorems and such
\begin{theorem}
For any nonnegative integer $n$, we have
    $$(1+x)^n = \sum_{k=0}^n {n\choose k} x^k$$
\end{theorem}

\section*{Homework problems}
%
\begin{enumerate}
%
\item What are the minimum and maximum number of elements in a heap of size $h$?
%
\item Show with a heap with $n$ elements has height $\floor{\lg n}$.
%
\item Show that in the representation of a heap of $n$ elements using an array the leaf nodes
are in positions with indices $\floor{n/2} + 1, \floor{n/2} + 2, \ldots, n$.
%
\item Describe the process $\proc{Max-Heapify}(A, 3, 14)$
for an array with elements
27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0.
%
\item Describe the process \proc{Build-Max-Heap} for the array with elements
4, 1, 3, 2, 16, 9, 10, 14, 8, 7.
%
\item Show that in a heap of $n$ elements there are at most $\ceil{n / 2^{h+1}}$ nodes of height $h$.
%
\item Show that building a max heap from an unsorted sequence of size  $n$
takes $O(n)$ time.
%
\item Describe the process \proc{Heapsort} for the sequence 5, 13, 2, 25, 7, 17, 20, 8, 4.
%
\item What is the running time of heap sort when applied to an already sorted sequence? What if
the sequence in sorted in decreasing order?
%
\item Describe the process \proc{Extract-Max} for a heap with elements 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1.
%
\item Describe the process $\proc{Insert}(A, 10)$ for a heap with elements 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1.
%
\end{enumerate}

% ========================================================================================
% Done!
% ========================================================================================

\end{document}
