-
Notifications
You must be signed in to change notification settings - Fork 2
/
notes.tex
119 lines (105 loc) · 3.88 KB
/
notes.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Algorithms Notes
%
% Compiled from the lectures of COMP 3804
% as taught by John Howat, at Carleton University
%
% Started: February 13, 2012
% By: Alexis Beingessner
% Simon Pratt
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt]{book}
\usepackage{geometry}
\geometry{verbose,tmargin=1in,bmargin=1in,lmargin=.5in,rmargin=.5in}
\usepackage[pdftex]{graphicx}
\usepackage{fancyhdr}
\usepackage{fix-cm}
\usepackage{amsmath}
\usepackage{enumerate}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{parskip}
\usepackage{hyperref}
\usepackage{algorithmic}
\usepackage{multicol}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Extra stuff from John Howat
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\renewcommand{\implies}{\rightarrow}
\newcommand{\same}{\leftrightarrow}
\newcommand{\cross}{\times}
\newcommand{\xor}{\oplus}
\newcommand{\zz}{\mathbb{Z}}
\newcommand{\BigOh}[1]{O\!\left(#1\right)}
\newcommand{\LittleOh}[1]{o\!\left(#1\right)}
\newcommand{\BigOmega}[1]{\Omega\!\left(#1\right)}
\newcommand{\LittleOmega}[1]{\omega\!\left(#1\right)}
\newcommand{\BigTheta}[1]{\Theta\!\left(#1\right)}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Theorem, Lemma and Definitions
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{theorem}{Theorem}[chapter]
\newtheorem{lemma}{Lemma}[chapter]
\theoremstyle{definition}
\newtheorem{definition}{Definition}[chapter]
\newtheorem{claim}{Claim}[chapter]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Fix for amsthm and parskip
% URL: http://tex.stackexchange.com/questions/22119/how-can-i-change-the-spacing-before-theorems-with-amsthm
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\makeatletter
\def\thm@space@setup{%
\thm@preskip=\parskip \thm@postskip=0pt
}
\makeatother
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Header/footer
% Mostly taken from:
% https://texblog.wordpress.com/2007/11/07/headerfooter-in-latex-with-fancyhdr/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pagestyle{fancyplain}
\setlength{\headheight}{14pt}
\fancyhead{} % clear header
\fancyfoot{}
\fancyhead[L]{Algorithms Notes}
\fancyhead[C]{Page \thepage }
\fancyhead[R]{Alexis Beingessner \\ Simon Pratt}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Pretty math macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\summ}[2]{\ensuremath{\displaystyle\sum\limits_{#1}^{#2}}}
%pretty summation
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Document
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{Algorithms Notes}
\date{}
\author{Alexis Beingessner\\Simon Pratt}
\begin{document}
\maketitle
\tableofcontents
\part{Deterministic Algorithms}
\begin{multicols}{2}
\include{fibonacci} % done
\include{integer_multiplication} % done
\include{recurrences} % done
\include{heaps} % done
\include{selection} % done
\include{union_find} % done
\include{graphs} % done
\include{dfs} % done
\include{mst} % done
\include{shortest_path} % done
\include{dynamic_programming} % done
\include{complexity_classes} % done
\include{np_complete} % done
\end{multicols}
\part{Probablistic and Randomized Algorithms}
\begin{multicols}{2}
\include{probability}
\appendix
\include{approximation} % done
\include{acknowledgements} % done
\include{license} % done
\end{multicols}
\end{document}