% percent signs are used to create comments
% \documentclass is used to define the document type, the font size, and other properties of the document
% some examples of document types include article, report, and book
\documentclass[12pt]{article}
% \usepackage is used to import packages -- packages can be included together or separately
% amsmath is a package used for typesetting math
% amsfonts is required for special fonts, e.g. blackboard bold (for denoting real numbers, etc.)
\usepackage{amsmath,amsfonts}
% graphicx is required for images
\usepackage{graphicx}
% enumerate is used for customizing enumerations
\usepackage{enumerate}
% tikz is a package used for drawing many different types of figures and diagrams
% in this course, it will primarily be used for drawing trees and plotting points
\usepackage{tikz}
% miscellaneous other packages
\usepackage{algo,fullpage,url,amssymb,epsfig,color,xspace}
\usepackage[pdftitle={CS240 Tutorial 0},%
pdfsubject={University of Waterloo, CS240, Spring 2020},%
pdfauthor={}]{hyperref}
\renewcommand{\thesubsection}{Problem \arabic{subsection}}
% note: many of the packages above have other uses beyond those used in this document
% this marks the beginning of the document -- everything before this is called the preamble
% this is where the actual content of the document is found
\begin{document}
% every \begin statement has a corresponding \end statement
% in this case, the corresponding \end{document} statement is the last line in the .tex file
% center is used for centering elements of the document -- everything in this block will appear horizontally centered in the document
\begin{center}
% \Large is used to make the corresponding text larger and \bf indicates that a bold font will be used
% \\ is used to start a new line
{\Large\bf University of Waterloo}\\
% \vspace is used to produce additional vertical spacing -- in this case, we have 3mm of additional space
\vspace{3mm}
% some additional large and bold font text, followed by a new line
{\Large\bf CS240, Spring 2020}\\
% here we have an additional 2mm of vertical space
\vspace{2mm}
% some additional large and bold font text
{\Large\bf Tutorial 0}
\end{center}
\definecolor{care}{rgb}{0,0,0}
\def\question#1{\item[\bf #1.]}
\def\part#1{\item[\bf #1)]}
\newcommand{\pc}[1]{\mbox{\textbf{#1}}}
% this creates a new section in the document called "Mathematics"
% by default, latex will automatically number the sections -- this is the section numbered 1
% \section*{Mathematics} can be used instead if you do *not* want latex to produce a numbered section
\section{Mathematics}
% everything between the dollar symbols ($) is interpreted as math instead of ordinary text -- this is called math mode
% this is useful for typesetting mathematical symbols or small equations within a paragraph -- you can easily switch between paragraph mode and math mode
% latex has built-in commands for many mathematical symbols and functions
% ex: \log is used to denote the logarithm
% ex: < and > are used to denote less than and greater than, while \leq and \geq are used to denote less than or equal to and greater than or equal to
% ex: Greek letters can also be produced -- a capital and a small theta can be produced with \Theta and \theta respectively
% ex: \in is used to denote set membership
Write a proof showing that $\log(n!) \in O(n \log n)$. \\ \\
We have that:
% the align environment is used for producing multiple aligned equations, and everything within this block is interpreted as math
% by default, latex will automatically number the equations -- in our case, they are numbered 1 through 4
% \begin{align*} and \end{align*} can be used instead if you do *not* want latex to produce numbered equations
% in this environment, the & symbol is special and indicates where the equations align
% in our PDF, note that all of the equality and inequality symbols are vertically aligned -- to achieve this, we have that & precedes these symbols
\begin{align}
% \lvert and \rvert are used to denote the left and right portions of the absolute value
% \left and \right can be used to automatically adjust the size of the delimiter that comes after it
% in our case, we use them to adjust the size of the absolute values and parentheses -- this is useful when the equation contains larger characters, like the sum and product operators
% _ and ^ are used to denote subscripts and superscripts -- these can be combined together and even nested
% when combined, the relative order of these symbols does not matter -- x_{1}^{3} will produce the same thing as x^{3}_{1}
% curly brackets can be used to avoid ambiguity when nesting (ex: x_{y_{2}})
% \sum and \prod are used to denote the summation and product operators respectively -- these can also include subscripts and superscripts as described above
% \qquad is used to add a fixed amount of horizontal space -- alternatively, \hspace (analogous to \vspace) can also be used
% \forall is used to denote the "for all" quantifier symbol, \exists is used to denote the "there exists" quantifier symbol
\left \lvert \log(n!) \right \rvert &= \left \lvert \log\left(\prod_{i=1}^{n} i \right) \right \rvert \\[2mm] % here (and below) we request an additional 2mm of vertical space
&= \left \lvert \sum^{n}_{i = 1} \log i \right \rvert \\[2mm]
&\leq \left \lvert \sum_{i = 1}^{n} \log n \right \rvert \qquad (\forall n \geq 1) \\[2mm]
&= \left \lvert n \log n \right \rvert
\end{align} % the align environment ends here
\\
Hence picking $c = 1$ and $n_{0} = 1$ gives the desired result.
% here we create a second section called "Trees"
% once again, \section*{Trees} can be used instead if you do *not* want a numbered section
\section{Trees}
We will add the letters Z, A, and B to the tree below. \\
% the tikzpicture environment enables us to use the tikz package -- note that this diagram will be centered
% the first part specifies diagram properties: how nodes are drawn, the distance between two sibling nodes in a particular level, the distance between levels...
% the second part, consisting of node and child statements, draws the resulting tree
\begin{center}\begin{tikzpicture}[
level distance=45 pt,
every node/.style={circle,draw},
level 1/.style={sibling distance=200 pt},
level 2/.style={sibling distance=100 pt},
level 3/.style={sibling distance=60 pt}
]
\node {M$_{0}$} % this is the root node, which is labeled M_0
child {node {F$_{0}$} % everything in this block is the left subtree of the root (i.e. the left child of M_0 is F_0)
child {node {C$_{0}$}} % the left child of F_0 is C_0
child {node {I$_{0}$}} % the right child of F_0 is I_0
}
child {node {T$_{0}$} % everything in this block is the right subtree of the root (i.e. the right child of M_0 is T_0)
child {node {Q$_{0}$}} % the left child of T_0 is Q_0
child {node {W$_{0}$}} % the right child of T_0 is W_0
};
\end{tikzpicture}\end{center} % the tikzpicture environment ends here
% \it is used to produce italic font
% see below for use of child[missing]
{\it Hint: For nodes with only one child, you may wish to use ``child[missing]'' for the non-existent child.}
% here we have another tikzpicture, which will also be centered
\begin{center}\begin{tikzpicture}[
level distance=45 pt,
every node/.style={circle,draw},
level 1/.style={sibling distance=200 pt},
level 2/.style={sibling distance=100 pt},
level 3/.style={sibling distance=60 pt}
]
\node {M$_{0}$} % this is the root node, which is labeled M_0
child {node {F$_{0}$} % everything in this block is the left subtree of the root (i.e. the left child of M_0 is F_0)
child {node {C$_{0}$} % everything in this block is the left subtree of F_0
child {node {A$_{0}$} % everything in this block is the left subtree of C_0
child[missing] % child[missing] is used to specify that A_0 does not have a left child
child {node {B$_{0}$}} % therefore, B_0 will be drawn as a right child of A_0
}
child [missing] % child[missing] is used to specify that C_0 does not have a right child
}
child {node {I$_{0}$}} % everything in this block is the right subtree of F_0
}
child {node {T$_{0}$} % everything in this block is the right subtree of the root (i.e. the right child of M_0 is T_0)
child {node {Q$_{0}$}} % everything in this block is the left subtree of T_0
child {node {W$_{0}$} % everything in this block is the right subtree of T_0
child[missing] % child[missing] is used to specify that W_0 does not have a left child
child{node {Z$_{0}$}} % therefore, Z_0 will be drawn as a right child of W_0
}
};
\end{tikzpicture}\end{center}
% here we create a third section called "Plots"
% once again, \section*{Plots} can be used instead if you do *not* want a numbered section
\section{Plots}
Plot the following points below. Only show the resulting plot.\\
Points: (2,7), (1,3), (3,1), (7,7)
% here we have another tikzpicture, which will also be centered
\begin{center}
\begin{tikzpicture}
% this first part is responsible for drawing the boundary (4 lines) of our plot
% ex: the first \draw statement draws a thick line from coordinate (0,9) to coordinate (0,0) and positions the label 0 to the left of (0,0)
\draw[thick,] (0,9) -- (0,0) node[left] {0};
\draw[thick,] (0,0) -- (9,0) node[below] {9};
\draw[thick,] (9,9) -- (9,0) node[left] {};
\draw[thick,] (9,9) -- (0,9) node[left] {9};
% there are many variations of lines you could draw
% ex: \draw[thick,dashed,blue] (5,0) -- (5,9) node[below] {};
% this second part is responsible for drawing the points themselves
% ex: \fill (x, y) circle[radius=2.5pt] node[right]{LAB} will position a filled circle of radius 2.5pt at the coordinate (x, y),
% with a labeling of LAB positioned to the right of the circle
\fill (2, 7) circle[radius=2.5pt] node[above left]{(2, 7)};
\fill (1, 3) circle[radius=2.5pt] node[above right]{(1, 3)};
\fill (3, 1) circle[radius=2.5pt] node[right]{(3, 1)};
\fill (7, 7) circle[radius=2.5pt] node[below right]{(7, 7)};
\end{tikzpicture}
\end{center}
% here we create a fourth section called "Latex Resources"
\section{Latex Resources}
\LaTeX\ Editors
% the itemize environment is used to create bullet-point lists -- individual bullet-points are specified using \item
% the \url statement can be used to create a clickable URL in the PDF document
\begin{itemize} % a list with 4 bullet-points
\item{MiKTex: \url{https://miktex.org/}}
\item{TeXstudio: \url{https://www.texstudio.org/}}
\item{Overleaf: \url{https://www.overleaf.com/}}
\item{pdflatex: on the student environment}
\end{itemize}
\bigskip
Miscellaneous Resources
\begin{itemize} % another list with 4 bullet-points
\item{\url{http://detexify.kirelabs.org/classify.html}}
\item{\url{https://oeis.org/wiki/List_of_LaTeX_mathematical_symbols}}
\item{\url{https://en.wikibooks.org/wiki/LaTeX}}
\item{\url{https://tex.stackexchange.com/}}
\end{itemize}
\end{document}