\documentclass[10pt,a4paper]{article}

% Packages
\usepackage{fancyhdr}           % For header and footer
\usepackage{multicol}           % Allows multicols in tables
\usepackage{tabularx}           % Intelligent column widths
\usepackage{tabulary}           % Used in header and footer
\usepackage{hhline}             % Border under tables
\usepackage{graphicx}           % For images
\usepackage{xcolor}             % For hex colours
%\usepackage[utf8x]{inputenc}    % For unicode character support
\usepackage[T1]{fontenc}        % Without this we get weird character replacements
\usepackage{colortbl}           % For coloured tables
\usepackage{setspace}           % For line height
\usepackage{lastpage}           % Needed for total page number
\usepackage{seqsplit}           % Splits long words.
%\usepackage{opensans}          % Can't make this work so far. Shame. Would be lovely.
\usepackage[normalem]{ulem}     % For underlining links
% Most of the following are not required for the majority
% of cheat sheets but are needed for some symbol support.
\usepackage{amsmath}            % Symbols
\usepackage{MnSymbol}           % Symbols
\usepackage{wasysym}            % Symbols
%\usepackage[english,german,french,spanish,italian]{babel}              % Languages

% Document Info
\author{kwo}
\pdfinfo{
  /Title (python-midterm-2.pdf)
  /Creator (Cheatography)
  /Author (kwo)
  /Subject (python midterm 2 Cheat Sheet)
}

% Lengths and widths
\addtolength{\textwidth}{6cm}
\addtolength{\textheight}{-1cm}
\addtolength{\hoffset}{-3cm}
\addtolength{\voffset}{-2cm}
\setlength{\tabcolsep}{0.2cm} % Space between columns
\setlength{\headsep}{-12pt} % Reduce space between header and content
\setlength{\headheight}{85pt} % If less, LaTeX automatically increases it
\renewcommand{\footrulewidth}{0pt} % Remove footer line
\renewcommand{\headrulewidth}{0pt} % Remove header line
\renewcommand{\seqinsert}{\ifmmode\allowbreak\else\-\fi} % Hyphens in seqsplit
% This two commands together give roughly
% the right line height in the tables
\renewcommand{\arraystretch}{1.3}
\onehalfspacing

% Commands
\newcommand{\SetRowColor}[1]{\noalign{\gdef\RowColorName{#1}}\rowcolor{\RowColorName}} % Shortcut for row colour
\newcommand{\mymulticolumn}[3]{\multicolumn{#1}{>{\columncolor{\RowColorName}}#2}{#3}} % For coloured multi-cols
\newcolumntype{x}[1]{>{\raggedright}p{#1}} % New column types for ragged-right paragraph columns
\newcommand{\tn}{\tabularnewline} % Required as custom column type in use

% Font and Colours
\definecolor{HeadBackground}{HTML}{333333}
\definecolor{FootBackground}{HTML}{666666}
\definecolor{TextColor}{HTML}{333333}
\definecolor{DarkBackground}{HTML}{A3A3A3}
\definecolor{LightBackground}{HTML}{F3F3F3}
\renewcommand{\familydefault}{\sfdefault}
\color{TextColor}

% Header and Footer
\pagestyle{fancy}
\fancyhead{} % Set header to blank
\fancyfoot{} % Set footer to blank
\fancyhead[L]{
\noindent
\begin{multicols}{3}
\begin{tabulary}{5.8cm}{C}
    \SetRowColor{DarkBackground}
    \vspace{-7pt}
    {\parbox{\dimexpr\textwidth-2\fboxsep\relax}{\noindent
        \hspace*{-6pt}\includegraphics[width=5.8cm]{/web/www.cheatography.com/public/images/cheatography_logo.pdf}}
    }
\end{tabulary}
\columnbreak
\begin{tabulary}{11cm}{L}
    \vspace{-2pt}\large{\bf{\textcolor{DarkBackground}{\textrm{python midterm 2 Cheat Sheet}}}} \\
    \normalsize{by \textcolor{DarkBackground}{kwo} via \textcolor{DarkBackground}{\uline{cheatography.com/32105/cs/9832/}}}
\end{tabulary}
\end{multicols}}

\fancyfoot[L]{ \footnotesize
\noindent
\begin{multicols}{3}
\begin{tabulary}{5.8cm}{LL}
  \SetRowColor{FootBackground}
  \mymulticolumn{2}{p{5.377cm}}{\bf\textcolor{white}{Cheatographer}}  \\
  \vspace{-2pt}kwo \\
  \uline{cheatography.com/kwo} \\
  \end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Cheat Sheet}}  \\
   \vspace{-2pt}Not Yet Published.\\
   Updated 14th November, 2016.\\
   Page {\thepage} of \pageref{LastPage}.
\end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Sponsor}}  \\
  \SetRowColor{white}
  \vspace{-5pt}
  %\includegraphics[width=48px,height=48px]{dave.jpeg}
  Measure your website readability!\\
  www.readability-score.com
\end{tabulary}
\end{multicols}}




\begin{document}
\raggedright
\raggedcolumns

% Set font size to small. Switch to any value
% from this page to resize cheat sheet text:
% www.emerson.emory.edu/services/latex/latex_169.html
\footnotesize % Small font.

\begin{multicols*}{3}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{recursion}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\bf{GCD}} \newline def rec\_find\_gcd(a, b): \newline     if a\%b == 0: \newline         return b \newline     return rec\_find\_gcd(b, a\%b) \newline {\bf{reverse string}} \newline def reverse\_string(s): \newline     if len(s) \textless{}= 1: \newline         return s \newline     return s{[}-1{]}+reverse\_string(s{[}:-1{]}) \newline {\bf{recursive function returning a tuple with quotient and remainder of 2 integers}} \newline def rec\_div(a, b): \newline     if a \textless{} b: \newline         return 0, a \newline     new\_tuple = rec\_div(a-b, b) \newline     return new\_tuple{[}0{]}+1, new\_tuple{[}1{]} \newline {\bf{takes in string of positive numbers and letters and returns a string of all the numbers in order}} \newline def rec\_num\_find(s): \newline     if len(s) == 0: \newline         return '' \newline     if s{[}0{]}.isdigit(): \newline         return s{[}0{]} + rec\_num\_find(s{[}1:{]}) \newline     else: \newline         return rec\_num\_find(s{[}1:{]}) \newline {\bf{OR}} \newline def rec\_num\_find2(s): \newline     if len(s) \textless{}= 1: \newline         if s.isdigit(): \newline             return s \newline         return '' \newline     a = rec\_num\_find2(s{[}: len(s)/2{]}) \newline     b = rec\_num\_find2(s{[}len(s)/2 :{]}) \newline     return a + b \newline {\bf{Takes a string and a pattern and determines if pattern is in string(no in operator)}} \newline def rec\_detect(s, pat): \newline     if len(pat) \textgreater{} len(s): \newline         return False \newline     return pat==s{[}:len(pat){]} or rec\_detect(s{[}1:{]}, pat) \newline {\bf{counts periods in the string argument}} \newline def rec\_period(s): \newline     if len(s) == 0: \newline         return 0 \newline     if s{[}0{]} == '.': \newline         return 1 + rec\_period(s{[}1:{]}) \newline     return rec\_period(s{[}1:{]}) \newline {\bf{takes a string of characters and prints all combinations = original length}} \newline def rec\_all\_strings(s, result=''): \newline     if len(result) == len(s): \newline         print result \newline         return None \newline     for char in s: \newline         rec\_all\_strings(s, result+char)} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Recursion Continued}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\bf{power function that raises a to the power of b}} \newline def power(a, b): \newline     if b == 0: \newline         return 1 \newline     return a * power(a, b-1) \newline {\bf{function that takes an integer and returns binary representation in list}} \newline def bin\_rep(n): \newline     if n \textless{}= 1: \newline         return {[}n{]} \newline     return bin\_rep(n/2) + {[}n \% 2{]} \newline {\bf{takes in tuple, returns set of all possible tuples using the original elements}} \newline def power\_set(atuple): \newline     if len(atuple) == 0: \newline         return \{atuple\} \newline     temp = power\_set(atuple{[}1:{]}) \newline     result = set() \newline     result.update(temp) \newline     for item in temp: \newline         new\_tuple = (atuple{[}0{]}, ) + item \newline         result.add(new\_tuple) \newline     return result \newline {\bf{super digit is sum of digits continuously until it is a single number ie. 9875 = 2}} \newline def super\_digit(n): \newline     if n \textless{} 10: \newline         return n \newline     temp = 0 \newline     for digit in str(n): \newline         temp = temp + int(digit) \newline     return super\_digit(temp)} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Basic Recursion}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{def recursive\_sum(n): \newline     if n == 1: \newline         return 1 \newline     return n + recursive\_sum(n-1) \newline def recursive\_factorial(n): \newline     if n == 0: \newline         return 1 \newline     return n{\emph{recursive\_sum(n-1) \newline def multiplication(x,n): \newline     if n == 0: \newline         return 0 \newline     return x + multiplication(x, n-1) \newline def reverse\_string(s): \newline     if len(s) \textless{}= 1: \newline         return s \newline     return s{[}-1{]}+reverse\_string(s{[}:-1{]}) \newline def is\_palindrome(s): \newline     s=s.lower() \newline     if len(s)\textless{}=1: \newline         return True \newline     return s{[}0{]} == s{[}-1{]} and is\_palindrome(s{[}1:-1{]}) \newline def min\_list(list1): \newline     if len(list1) == 1: \newline         return list1{[}0{]} \newline     min\_rest = min\_list{[}1:{]} \newline     if min\_list{[}0{]} \textless{} min\_rest: \newline         return list1{[}0{]} \newline     return min\_rest \newline def product(list1): \newline     if len(list1) == 1: \newline         return list1{[}0{]} \newline     return list1{[}0{]} }} product(list1{[}1:{]}) \newline def rotate\_right(list1, n): \newline     if n == 0 or len(list1) == 0: \newline         return list1 \newline     list1.insert(0,list1.pop()) \newline     return rotate\_right(list1, n-1) \newline def \seqsplit{rec\_flatten(nested\_list):} \newline     if len(nested\_list) == 1: \newline         return nested\_list{[}0{]} \newline     return nested\_list{[}0{]} + rec\_flatten(nested\_list{[}1:{]}) \newline def rec\_fib(n): \newline     if n\textless{}=1: \newline         return n \newline     return rec\_fib(n-1) + rec\_fib(n-2) \newline def rec\_fib\_efficient(n, d): \newline     \#use a dictionary to store values in the sequence \newline     if n in d: \newline         return d{[}n{]} \newline     x = rec\_fib\_efficient(n-q, d) +rec\_fib\_efficient(n-2, d) \newline     d{[}n{]} = x \newline     return x} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Tuples}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{Defining a tuple with one value \newline % Row Count 1 (+ 1)
singleton = (3,) \newline % Row Count 2 (+ 1)
Tuple packing \newline % Row Count 3 (+ 1)
=a, b... or return a, b... \newline % Row Count 4 (+ 1)
Tuple Operators \newline % Row Count 5 (+ 1)
+, *, 'in' \newline % Row Count 6 (+ 1)
Tuple Methods \newline % Row Count 7 (+ 1)
tuple.count(a) will count the number of times a is in the tuple \newline % Row Count 9 (+ 2)
tuple.index(a) will give the index of a \newline % Row Count 10 (+ 1)
{\bf{for i in range(len(tuple))}} iterates over the {\emph{indicies}} of the items \newline % Row Count 12 (+ 2)
thus you will \newline % Row Count 13 (+ 1)
{\bf{print tuple{[}i{]}}} \newline % Row Count 14 (+ 1)
{\bf{for i in tuple}} will iterate over the items directly \newline % Row Count 16 (+ 2)
thus you will \newline % Row Count 17 (+ 1)
{\bf{print i}} \newline % Row Count 18 (+ 1)
sequence unpacking \newline % Row Count 19 (+ 1)
t = (1, 10, 100) \newline % Row Count 20 (+ 1)
first, second, third = t% Row Count 21 (+ 1)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Dictionaries}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{dictionary = dict() OR dictionary = \{\} \newline % Row Count 1 (+ 1)
to add key-value.... dictionary{[}12345{]} = 'John' \newline % Row Count 2 (+ 1)
{\bf{dictionary{[}12345{]}}} will print 'John' \newline % Row Count 3 (+ 1)
{\bf{Operators}} \newline % Row Count 4 (+ 1)
in \newline % Row Count 5 (+ 1)
get retrieves value associated with a certain key(returns None if not in dictionary) \newline % Row Count 7 (+ 2)
{\bf{Methods}} \newline % Row Count 8 (+ 1)
get dictionary.get(key) gives the value associated with key \newline % Row Count 10 (+ 2)
keys  dictionary.keys() gives all keys \newline % Row Count 11 (+ 1)
values  dictionary.values() gives all values \newline % Row Count 12 (+ 1)
items dictionary.values() gives a list of key-value pairs% Row Count 14 (+ 2)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Dictionary Code}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\bf{Reverse Lookup}} \newline def find\_key(d, value\_to\_find): \newline     for key in d: \newline         if d{[}key{]} == value\_to\_find: \newline             return key \newline     return None \newline  \newline {\bf{grouping grades}} \newline grade\_list = {[}100, 98, 76, 65, 61, 80, 75, 96, 90, 67, 87{]} \newline  \newline hist = \{\} \newline for i in range(1, 5): \newline     hist{[}'bucket '+str(i){]} = 0 \newline      \newline for grade in grade\_list: \newline     if grade \textgreater{}= 90: \newline         hist{[}'bucket 1'{]} += 1 \newline     elif grade \textgreater{}= 80: \newline         hist{[}'bucket 2'{]} += 1 \newline     elif grade \textgreater{}= 70: \newline         hist{[}'bucket 3'{]} += 1 \newline     else: \newline         hist{[}'bucket 4'{]} += 1 \newline  \newline for i in range(1, 5): \newline     print 'There are', hist{[}'bucket '+str(i){]}, 'grades in bucket', i} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Sets}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{Set is an unordered collection of unique elements. All elements are immutable \newline % Row Count 2 (+ 2)
defining an empty set \newline % Row Count 3 (+ 1)
empty = set() \newline % Row Count 4 (+ 1)
using \{\} gives a dict \newline % Row Count 5 (+ 1)
sets are good for fast membership testing regardless of how many elements are in the set \newline % Row Count 7 (+ 2)
IE. set1 = \{'BC', 'BU', 'NEU', 'BC', 'BC'\} \newline % Row Count 8 (+ 1)
len(set1) \newline % Row Count 9 (+ 1)
3 \newline % Row Count 10 (+ 1)
Set methods \newline % Row Count 11 (+ 1)
set.add(a) adds element a to the set \newline % Row Count 12 (+ 1)
red.intersection(blue) gives the intersection of blue and red \newline % Row Count 14 (+ 2)
red.update(blue) updates red with the union of itself and blue \newline % Row Count 16 (+ 2)
red -= \{1, 2\} is set difference. It is set red - 1 and 2% Row Count 18 (+ 2)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Search Algorithms}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{def \seqsplit{lin\_search\_general(input\_list}, value): \newline  \newline     """Implementation of the Linear Search Algorithm for an arbitrary list \newline     {\bf{Determine whether a given value (number) exists in a list of numbers that is ordered in an ascending (increasing) fashion.}} \newline     Input arguments input\_list-{}-any list of numbers (sorted or not sorted)value-{}-any number""" \newline  \newline     if len(input\_list) == 0: \newline         return False \newline     for i in range(len(input\_list)): \newline         if value == input\_list{[}i{]}: \newline             return True \newline     return False \newline  \newline def \seqsplit{lin\_search(ordered\_list}, value): \newline  \newline     """Implementation of the Linear Search Algorithm. \newline     Input arguments ordered\_list-{}-any list of numbers that is sorted in an ascending fashion value-{}-any number""" \newline  \newline     if len(ordered\_list)==0 or ordered\_list{[}-1{]}\textless{}value: \newline         return False \newline     for i in \seqsplit{range(len(ordered\_list)):} \newline         if value == ordered\_list{[}i{]}: \newline             return True \newline         if value \textless{} ordered\_list{[}i{]}: \newline             return False \newline     return False \newline  \newline def \seqsplit{binary\_search(ordered\_list}, value): \newline  \newline     """Implementation of the Binary Search Algorithm. \newline     Determine whether a given value (number) exists in a list of numbers \newline     that is ordered in an ascending (increasing) fashion. \newline  \newline     Input arguments \newline     ordered\_list-{}-any list of numbers that is sorted in an ascending fashion \newline     value-{}-any number""" \newline  \newline     if len(ordered\_list)==0 or ordered\_list{[}-1{]}\textless{}value or value\textless{}ordered\_list{[}0{]}: \newline         return False \newline     low = 0 \newline     high = len(ordered\_list) - 1 \newline     while low \textless{}= high: \newline         mid = (low + high) / 2 \newline         if value == ordered\_list{[}mid{]}: \newline             return True \newline         if value \textless{} ordered\_list{[}mid{]}: \newline             high = mid - 1 \newline         else: \newline             low = mid + 1 \newline     return False \newline  \newline def \seqsplit{binary\_search\_rec(ordered\_list}, value): \newline     if len(ordered\_list)==0 or value\textless{}ordered\_list{[}0{]} or ordered\_list{[}-1{]}\textless{}value: \newline         return False \newline     return \seqsplit{binary\_search\_helper(ordered\_list}, value) \newline  \newline def \seqsplit{binary\_search\_helper(ordered\_list}, value): \newline     if len(ordered\_list) == 0: \newline         return False \newline     mid = (len(ordered\_list)-1) / 2 \newline     if value == ordered\_list{[}mid{]}: \newline         return True \newline     if value \textless{} ordered\_list{[}mid{]}: \newline         return binary\_search\_helper(ordered\_list{[}:mid{]}, value) \newline     return binary\_search\_helper(ordered\_list{[}mid+1:{]}, value)} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Sort Algorithms}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{def \seqsplit{selection\_sort(in\_list):} \newline     """Implementation of the Selection Sort algorithm (in-place).""" \newline     n = len(in\_list) \newline     for i in range(n-1): \newline         \# finding the min value in a portion of the list \newline         min\_value = in\_list{[}i{]} \newline         min\_index = i \newline         for j in range(i+1, n): \newline             if in\_list{[}j{]} \textless{} min\_value: \newline                 min\_value = in\_list{[}j{]} \newline                 min\_index = j \newline         \# swap the min w/ the current value \newline         in\_list{[}min\_index{]} = in\_list{[}i{]} \newline         in\_list{[}i{]} = min\_value         \newline     return None \newline  \newline def \seqsplit{insertion\_sort(in\_list):} \newline     """Implementation of the Insertion Sort algorithm (in-place).""" \newline     n = len(in\_list) \newline     for i in range(n-1): \newline         j = i + 1 \newline         value = in\_list{[}j{]} \newline         while j\textgreater{}=1 and value\textless{}in\_list{[}j-1{]}: \newline             in\_list{[}j{]} = in\_list{[}j-1{]} \newline             in\_list{[}j-1{]} = value \newline             j -= 1 \newline     return None \newline  \newline def merge\_sort(in\_list): \newline     """Implementation of the Merge Sort algorithm (Return the sorted list).""" \newline     n = len(in\_list) \newline     if n \textless{}= 1: \newline         return in\_list \newline     right\_half\_sorted = merge\_sort(in\_list{[}n/2:{]}) \newline     left\_half\_sorted = merge\_sort(in\_list{[}:n/2{]}) \newline     return merge(left\_half\_sorted, right\_half\_sorted) \newline  \newline def merge(list1, list2): \newline     """Merge two sorted lists such that the merged list is also sorted.""" \newline     merged = {[}{]} \newline     while len(list1)\textgreater{}0 and len(list2)\textgreater{}0: \newline         if list1{[}0{]} \textless{}= list2{[}0{]}: \newline             \seqsplit{merged.append(list1.pop(0))} \newline         else: \newline             \seqsplit{merged.append(list2.pop(0))} \newline     merged.extend(list1) \newline     merged += list2 \newline     return merged} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}


% That's all folks
\end{multicols*}

\end{document}