Mathematics.tex

% =============================================	%
%												%
%		            Mathematics               	%
%												%
% =============================================	%

\chapter{Mathematics}
\chapterinfo{}
	%------------------------------
	\section{Common Sums}
	%\sectioninfo{Mathematical formulas for common sums}
	
	$$\sum_{k=1}^{n}k = \frac{n(n+1)}{2}$$
	$$\sum_{k=1}^{n}2k-1 = n^2$$
	$$\sum_{k=1}^{n}k^2 = \frac{n(n+1)(2n+1)}{6}$$
	$$\sum_{k=1}^{n}(2k-1)^2 = \frac{n(4n^2-1)}{3}$$
	$$\sum_{k=1}^{n}k^3 = \frac{n^2(n+1)^2}{4}$$
	$$\sum_{k=1}^{n}(2k-1)^3 = n^2(2n^2-1)$$
	$$\sum_{k=1}^{n}k^4 = \frac{n(n+1)(n+2)(n+3)}{30}$$
	$$\sum_{k=1}^{n}k^5 = \frac{n^2(n+1)^2(2n^2+2n-1)^2}{12}$$
	$$\sum_{k=1}^{n}k(k+1) = \frac{n(n+1)(n+2)}{3}$$
	$$\sum_{k=1}^{n}k(k+1)(k+2) = \frac{n(n+1)(n+2)(n+3)}{4}$$
	$$\sum_{k=1}^{n}k(k+1)(k+2)(k+3) = \frac{n(n+1)(n+2)(n+3)(n+4)}{5}$$
	%$$\sum_{k=1}^{n}k^i = \frac{\sum_{l=0}^{i+1}\frac{(i+1)!}{(i+1-l)!l!}n^l - 1 - \sum_{j=0}^{i-1}}{i+1}$$
	
	%------------------------------
	\section{Factorials}
	%\sectioninfo{C++ and Java code for efficiently calculating factorials}
	    \indent Most of the time you'll have to compute factorials more than once in a 
	    program. Hence in order to save time, it is beneficial to compute all of
	     them at once and store them in an array for future use. \\
		\lstinputlisting[language=C++,label=samplecode,caption=Calculating a factorial (C++)]{Code/calcFactorialC++.txt}
		\ \\
		\indent Note the usage of the {\bf long long} type, a 64-bit type. However, it 
		can only accurately compute factorials until $20!$. After that it will 
		overflow the {\bf long long} type and be horribly wrong. In Java you can
		 use the {\bf long} type to achieve similar results, or you can cheat a 
		 bit and use the built-in {\bf BigInteger} type like so. \\
		 \lstinputlisting[language=Java,label=samplecode,caption=Calculating a factorial with the BigInteger class (Java)]{Code/calcFactorialJava.txt}
		 \ \\
		 {\bf Problem} : How many digits are in the factorial of n? \\
		 {\bf Solution} : Simply add up the logs of the numbers less than or equal to n starting at 1. \\
		 \lstinputlisting[language=Java,label=samplecode,caption=Counting the digits in the factorial of a number (Java)]{Code/countDigitsJava.txt}
		 \ \\
		 {\bf Problem} : How many trailing zeroes does the number $n!$ have? \\
		 \lstinputlisting[language=Java,label=samplecode,caption=Counting the number of trailing zeroes in the factorial of a number (Java)]{Code/countZeroesJava.txt}
		 
	%------------------------------
	\section{Derangements}
	%\sectioninfo{}
	Number of permutations with no fixed points. \\
	\indent $!0 = 1$ and $!1 = 1$ \\
	\indent $!n = (n-1)(!(n-1) + !(n-2))$ for $n \ge 2$
	
	%------------------------------
	\section{Combinations}
	%\sectioninfo{}
	Written as ${_n}C_r$, this represents the number of ways of selecting $r$ 
	objects from $n$ where order is irrelevant.
	
	$$
	{_n}C_r = {{n}\choose{r}} = \frac{n!}{(n-r)!r!}\ \ \ \ \ \ \ \ \ \ 
	{{n}\choose{r}} = {{n-1}\choose{r-1}} + {{n-1}\choose{r}}\ \ \ \ \ \ \ \ \ \ 
	{{n}\choose{r}} = {{n}\choose{n-r}}
	$$
	
	$$
	{{n}\choose{r}} = {{n}\choose{r-1}}\frac{n-r+1}{r}\ \ \ \ \ \ \ \ \ \ 
	{{n}\choose{r}} = {{n-1}\choose{r}}\frac{n}{n-r}\ \ \ \ \ \ \ \ \ 
	{{n}\choose{r}} = {{n-1}\choose{r-1}}\frac{n}{r}\ \ \ \ \ \ \ \ \ 
	$$
	
	\lstinputlisting[language=Java,label=samplecode,caption=Calculating combinations using the BigInteger class (Java)]{Code/calcCombinationsJava.txt}
	\ \\
	\indent However, it is safer to use the second formula in a tabular fashion since 
	it only involves addition. It runs in $O(n^2)$ but most of the time $n$ is
	rather small, so it won't affect the overall performance. \\
	
	\lstinputlisting[language=C++,label=samplecode,caption=Calculating combinations in a tabular fashion (C++)]{Code/calcCombinationsC++.txt}
	
	%------------------------------
	\section{Euclidean Algorithm}
	%\sectioninfo{}
	
	\indent This is an algorithm used to find the greatest common divisor of two numbers.
	Runs in $O(max(\log{A}, \log{B}))$ time. \\
	
	\lstinputlisting[language=Java,label=samplecode,caption=Euclidean Algorithm (Java)]{Code/gcd.txt}
	\ \\
	Note: The LCM (least common multiple) is $$\frac{ab}{gcd(a,b)}$$
	
	%------------------------------
	\section{Extended Euclidean Algorithm}
	%\sectioninfo{}
	
	\indent Given numbers $a$ and $b$, this number returns the $gcd(a,b)$ and it will 
	set the values of $x$ and $y$ such that $ax + by = gcd(a,b)$ is satisfied.
	
	{\bf Uses} : finding the inverse of a number under a certain modulo.\\
	\indent{\bf Note} : When $a$ and $b$ are relatively prime, i.e. $gcd(a,b) = 1$, then 
	$$x = a^{-1} \imod{b}$$
	$$y = b^{-1} \imod{a}$$
	
	\lstinputlisting[language=C++,label=samplecode,caption=Extended Euclidean Algorithm (C++)]{Code/extendedEuclidean.txt}
	
	%------------------------------
	\section{Catalan Numbers}
	%\sectioninfo{}
	
	\indent The Catalan numbers are a sequence of numbers that occur in many counting 
	problems, particularly those that involve recursively defined objects. \\
	
	\indent The $n^(th)$ Catalan number is given by
	$$C_n = \frac{1}{n+1}{{2n}\choose{n}} = 
	\frac{(2n)!}{(n+1)!n!} = 
	\prod_{k = 2}^{n}\frac{n+k}{k} = 
	{{2n}\choose{n}} - {{2n}\choose{n+1}} = 
	\frac{1}{n+1}\sum_{i=0}^{n}{{n}\choose{i}}^2$$
	
	Asymptotically, the Catalan numbers grow as $$C_n \sim \frac{4^n}{n^{\frac{3}{2}}\sqrt{\pi}}$$
	
	\lstinputlisting[language=C++,label=samplecode,caption=Catalan Numbers (C++)]{Code/catalan.txt}
	
	%------------------------------
	\section{Sieve of Eratosthenes}
	%\sectioninfo{}
	An efficient way to find all primes that are less than a certain number.
	It runs in $O(\sqrt{n}\log{n}\log{\log{n}})$ time. \\
	
	\lstinputlisting[language=Java,label=samplecode,caption=Sieve of Eratosthenes (Java)]{Code/primeSieve.txt}
	
	%------------------------------
	\section{Efficient Modular Exponentiation}
	%\sectioninfo{}
	
	Computes $a^b\imod{c}$ quickly using the method of repeated squaring \\
	\ \\
	{\bf Careful} : $0^0$ will return 1. It's up to you to catch this! \\
	{\bf Complexity} : $O\left(\log{b}\right)$ \\
	
	\lstinputlisting[language=Java,label=samplecode,caption=Efficient Modular Exponentiation (Java)]{Code/efficientModExp.txt}
	
	%------------------------------
	\section{Prime Factorization}
	%\sectioninfo{}
	
	Given an {\bf int}, this function returns a vector composed of its prime 
	factors (repetition included) in ascending order. \\
	\ \\
	{\bf Complexity} : $O(\sqrt{n})$ \\
	
	\lstinputlisting[language=C++,label=samplecode,caption=Prime Factorization (C++)]{Code/primeFactorizationC++.txt}
	
	%------------------------------
	\section{Primality Testing}
	%\sectioninfo{}
	{\bf Complexity} : $O(\sqrt{n})$ \\
	
	\lstinputlisting[language=C++,label=samplecode,caption=Primality Testing (C++)]{Code/primalityTesting.txt}
	
	%------------------------------
	\section{Totient Function}
	%\sectioninfo{}
	
	Denoted as $\phi(n)$, is the number of positive integers that are less than 
	or equal to $n$. Mathematically, it it $$\prod_{p_i | n}^{}n\left(1-\frac{1}{p_i}\right)$$
	for all distinct primes $p$ that divide $n$. Also, there is a slight 
	optimization that takes advantage of the fact that other than 2 and 3, all 
	primes are either $1 \imod{6}$ or $5 \imod{6}$.
	
	\lstinputlisting[language=C++,label=samplecode,caption=Totient Function (C++)]{Code/totient.txt}
	%------------------------------
	\section{Chinese Remainder Theorem}
	%\sectioninfo{}
	
	Given two arrays $a$, $n$ where 
	$$x = a[0] \imod{n[0]}$$
	$$x = a[1] \imod{n[1]}$$
	$$.$$
	$$.$$
	$$.$$
	this returns an array $z$, the solution of this system of equations where
	$x = z[0] \imod{z[1]}$.
	
	\lstinputlisting[language=Java,label=samplecode,caption=Chinese Remainder Theorem (Java)]{Code/chineseRemainderTheoremJava.txt}
	
	%------------------------------
	\section{Perfect Power Test}
	%\sectioninfo{}
	
	Efficient method of testing if a number can be written in the form $a^b$.
	
	\lstinputlisting[language=Java,label=samplecode,caption=Perfect Power Test (Java)]{Code/perfectPowerTest.txt}
	
	%------------------------------
	\section{Fraction-Decimal Converter}
	%\sectioninfo{}
	
	When dealing with fractions, it’s sometimes required to print them to a 
	certain precision. You definitely don’t want to convert it to a double and 
	print that out since there might be errors after 10 or so digits. Another 
	way to approach this problem is to repeatedly multiply and mod while 
	maintaining the number in fractional form. Note, this method is similar
	to how people divide by hand. This runs in $O\left(k\right)$ where $k$ is the number of 
	digits of precision.
	
	\lstinputlisting[language=C++,label=samplecode,caption=Fraction-Decimal Converter (C++)]{Code/frac2DecimalConversionC++.txt}
	
	%------------------------------
	\section{Fast Pythagorean Triplet Generator}
	%\sectioninfo{}
	
	This algorithm uses a BFS on the initial triple $\left(3,4,5\right)$ to 
	generate all other triplets. Given an integer {\bf MAX\_N}, this function
	returns a vector of all Pythagorean triplets with sides no bigger than 
	{\bf MAX\_N}. \\
	\ \\
	{\bf Complexity} : $O\left(k\right)$ - This algorithm is output sensitive
	($k$ is the number of answers).\\
	{\bf Note} : All triplets returned are unique. In each triplet 
	$\left(a,b,c\right)$ $a$ is not necessarily less than or equal to $b$. The 
	list includes non-primitive triplets. (This can easily be removed if not needed)\\
	
	\lstinputlisting[language=C++,label=samplecode,caption=Fast Pythagorean Triplet Generator (C++)]{Code/fastPythagoreanTripletGeneratorC++.txt}
	
	%------------------------------
	\section{Matrix Determinant}
	%\sectioninfo{}
	
	\ \ \ \ This uses partial Gaussian elimination to obtain an upper triangular matrix, 
	then the product of the main diagonal is the determinant.\\
	Assume that a Matrix class has already been created that contains:\\
	\indent{\bf int n, m;} (the dimensions)\\
	\indent{\bf double mat[][];} (the entries)\\
	has already been declared. Along with some basic constructors and helper 
	methods. (i.e. {\bf swapRow})
	
	\lstinputlisting[language=Java,label=samplecode,caption=Matrix Determinant (Java)]{Code/matrixDeterminant.txt} 
	
	%------------------------------
	\section{Inverse of a Matrix}
	%\sectioninfo{}
	
	This uses Gaussian elimination\\
	\ \\
	{\bf Note} : Doubles are not very precise. \\
	
	\lstinputlisting[language=Java,label=samplecode,caption=Matrix Inverse (Java)]{Code/matrixInverse.txt}
	
	%------------------------------