% Options for packages loaded elsewhere
\PassOptionsToPackage{unicode}{hyperref}
\PassOptionsToPackage{hyphens}{url}
%
\documentclass[
]{article}
\usepackage{amsmath,amssymb}
\usepackage{iftex}
\ifPDFTeX
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
  \usepackage{textcomp} % provide euro and other symbols
\else % if luatex or xetex
  \usepackage{unicode-math} % this also loads fontspec
  \defaultfontfeatures{Scale=MatchLowercase}
  \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
\fi
\usepackage{lmodern}
\ifPDFTeX\else
  % xetex/luatex font selection
\fi
% Use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
\IfFileExists{microtype.sty}{% use microtype if available
  \usepackage[]{microtype}
  \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\makeatletter
\@ifundefined{KOMAClassName}{% if non-KOMA class
  \IfFileExists{parskip.sty}{%
    \usepackage{parskip}
  }{% else
    \setlength{\parindent}{0pt}
    \setlength{\parskip}{6pt plus 2pt minus 1pt}}
}{% if KOMA class
  \KOMAoptions{parskip=half}}
\makeatother
\usepackage{xcolor}
\setlength{\emergencystretch}{3em} % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{-\maxdimen} % remove section numbering
\ifLuaTeX
  \usepackage{selnolig}  % disable illegal ligatures
\fi
\IfFileExists{bookmark.sty}{\usepackage{bookmark}}{\usepackage{hyperref}}
\IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
\urlstyle{same}
\hypersetup{
  pdftitle={pseudo-code-algorithms-with-python},
  hidelinks,
  pdfcreator={LaTeX via pandoc}}

\title{pseudo-code-algorithms-with-python}
\author{}
\date{}

\begin{document}
\maketitle

\hypertarget{pseudo-code-algorithms-with-python}{%
\section{pseudo-code-algorithms-with-python}\label{pseudo-code-algorithms-with-python}}

\hypertarget{pseudo-code-algorithms-with-python-1}{%
\section{Pseudo Code Algorithms with
Python}\label{pseudo-code-algorithms-with-python-1}}

.. contents::

\hypertarget{find-the-largest-number-in-a-list-or-array-of-numbers.}{%
\section{Find the largest number in a list or array of
numbers.}\label{find-the-largest-number-in-a-list-or-array-of-numbers.}}

.. code-block:: python

numbers = {[}5,6,2,7,6,2,0,4{]}

max = numbers{[}0{]}

for number in numbers:

\begin{verbatim}
if number > max:
    max = number
\end{verbatim}

\textbf{The Big-0 of this program is n O(n)}

\hypertarget{search-for-a-number-in-an-array-or-list}{%
\section{Search for a number in an array or
list}\label{search-for-a-number-in-an-array-or-list}}

Try to search and see if the number 0 is in the list or array

.. code-block:: python

numbers = {[}5,6,2,7,6,2,0,4{]}

for number in numbers: if number == 0: return True

\textbf{The Big-0 of this program is n O(n)}

\hypertarget{search-for-a-number-in-a-sorted-array-or-list}{%
\section{Search for a number in a Sorted array or
list}\label{search-for-a-number-in-a-sorted-array-or-list}}

Try to search to see if the number 80 is in the list or array.

the needle is the number we are searching for.

Note We call this algorithm the binary search.

.. code-block:: python

\# binary search haystack = {[}0,11,25,38,41,54,66,79,80,94{]} needle =
80

lo = 0 hi = len( haystack )

while lo \textless{} hi:

\begin{verbatim}
 mid = int( (lo + hi) / 2 )

 if needle > haystack[ mid ]:
     lo = mid + 1
 elif needle < haystack[ mid ]:
     hi = mid
 else:
     print "found %d which is the %d index of the list" % ( haystack[ mid ], mid )
     break
\end{verbatim}

\begin{itemize}
\tightlist
\item
  Worst case in 8 item list is 3 compares.
\item
  Worst case in 16 item list is 4 compares.
\item
  Worst case in 32 item list is 5 compares.
\end{itemize}

\textbf{The Big-0 of this program is n O(logn) - base 2}

This is a very good algorithm!

\hypertarget{bubble-sort-an-array-or-list}{%
\section{Bubble Sort an array or
list}\label{bubble-sort-an-array-or-list}}

This is a bubble sort algo using python, don't use this in production
this is for learning only!

\textbf{BIGO( n\^{}2 )}

.. code-block:: python

def bubsort( mylist ): while True: swapped = False for i in range( 0,
len( mylist ) - 1 ): if mylist{[}i{]} \textgreater{} mylist{[}i+1{]}:
temp = mylist{[}i{]} mylist{[}i{]} = mylist{[}i+1{]} mylist{[}i+1{]} =
temp swapped = True if not swapped: break

\hypertarget{python-recursion}{%
\section{python recursion}\label{python-recursion}}

.. code-block:: python

def gcd( x, y ): ``\,````Find greatest common divisor of two numbers
recursion''``\,''

\begin{verbatim}
 if y == 0: 
     return x
 else:
     return gcd( y, x%y )
\end{verbatim}

def gcd2( x, y ): ``\,````find the greatest common divisor of two
numebrs''``\,'' for i in range( 2, x ): if x \% i == 0 and y \% i == 0:
return i;

if \textbf{name} == ``\textbf{main}'': print gcd( 287, 91 ) print gcd2(
287, 91 )

: )

\hypertarget{python-heap}{%
\section{python heap}\label{python-heap}}

A heap is a binary tree where the parent is always larger than its
children.

Determine the last nodes that are leaves: (total number of items / 2) -
1

.. code-block:: python

def build\_heap( data ): ``\,````Turn any array or list (data) into a
heap tree''``\,'' j = ( len( data ) / 2 ) - 1 i = j while i
\textgreater= 0: current = data{[}i{]} \#insert\_heap( current, i ,
length of subtree i - 1 ) i -= 1

Most operating systems use heap tree to manage memory.

\hypertarget{hash-table}{%
\section{hash table}\label{hash-table}}

Don't use this in production! python has a datatype called dict, use
that instead!!!

This is an example of building a hash table.

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\tightlist
\item
  sparse table or direct address table.
\end{enumerate}

\textbf{Assume that:}

\begin{itemize}
\tightlist
\item
  Totle number of keys \textless= the size or the array.
\item
  no 2 elements have the same keys.
\end{itemize}

\textbf{Algorythm:}

\begin{itemize}
\tightlist
\item
  Create A{[}0, max -1{]}
\item
  put key x into A{[}x{]}
\end{itemize}

\textbf{Example:}

.. code-block:: python

keys = 5,2,3,7

A = list() A{[}2{]} = 2 A{[}5{]} = 5 A{[}3{]} = 3 A{[}7{]} = 7

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\setcounter{enumi}{1}
\tightlist
\item
  Hash table
\end{enumerate}

\textbf{Assume that:}

\begin{itemize}
\tightlist
\item
  keys = \{0,1,2,3,4,n-1\}
\item
  total numebr of keys \textgreater{} the size of the array
\end{itemize}

\textbf{Algorythm:}

\begin{itemize}
\tightlist
\item
  A = list(0, max -1)
\item
  put key x into A{[} hash(x) {]}
\end{itemize}

hash function like md5 or sha256 hash(x) = x mod 6

If you have collisions there could be a problem.

A few `easy' hash functions:

example = 11141874

\begin{itemize}
\tightlist
\item
  Truncation, choose part of the data to use for storage.
\end{itemize}

A{[}874{]} = 11141874

\begin{itemize}
\tightlist
\item
  Folding, split up data and add them up:
\end{itemize}

first 2 chars + last 2 chars

A{[}85{]} = 11141874

\begin{itemize}
\item
  Modular

  k mod m where m is the array size

  example m = 10
\end{itemize}

\hypertarget{extras}{%
\section{Extras}\label{extras}}

Note: Count the total number of comparisons in terms of n.

\hfill\break
\hfill\break

for( int i = 2 ; i\textless= n ; i++ )\{ \} Worst case there will be at
least two comparisons. Or at least n - 1 comparisons.

\hypertarget{big-o-notation-compared-to-complexity}{%
\section{Big-O notation compared to
Complexity}\label{big-o-notation-compared-to-complexity}}

Always look for the worst case when finding the Big-O

\begin{itemize}
\item
  O( 1 )
\item
  Constant complexity
\item
  O( log n )
\item
  Logarithmic complexity
\item
  O( n )
\item
  Linear complexity
\item
  O( n log n )
\item
  n log n complexity
\item
  O( n\^{}b )
\item
  Polynomial complexity
\item
  O( b\^{}n ), where b\textgreater1
\item
  Exponential complexity
\item
  O( n! )
\item
  Factorial complexity
\end{itemize}

\end{document}
