Algorithms.lyx

#LyX 2.0 created this file. For more info see http://www.lyx.org/
\lyxformat 413
\begin_document
\begin_header
\textclass book
\begin_preamble
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\usepackage[perpage]{footmisc}
\end_preamble
\use_default_options true
\begin_modules
theorems-std
\end_modules
\maintain_unincluded_children false
\language english
\language_package default
\inputencoding auto
\fontencoding global
\font_roman default
\font_sans default
\font_typewriter default
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100

\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\float_placement H
\paperfontsize default
\spacing single
\use_hyperref true
\pdf_title "Algorithms"
\pdf_author "Eyal Arubas"
\pdf_bookmarks true
\pdf_bookmarksnumbered false
\pdf_bookmarksopen false
\pdf_bookmarksopenlevel 1
\pdf_breaklinks false
\pdf_pdfborder true
\pdf_colorlinks false
\pdf_backref false
\pdf_pdfusetitle true
\papersize default
\use_geometry false
\use_amsmath 1
\use_esint 1
\use_mhchem 1
\use_mathdots 1
\cite_engine basic
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\use_refstyle 1
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Title
Algorithms
\end_layout

\begin_layout Author
Eyal Arubas
\end_layout

\begin_layout Standard
\begin_inset Box Boxed
position "t"
hor_pos "c"
has_inner_box 1
inner_pos "t"
use_parbox 0
use_makebox 0
width "100col%"
special "none"
height "1in"
height_special "totalheight"
status open

\begin_layout Plain Layout

\series bold
Warning:
\end_layout

\begin_layout Plain Layout
This is a rough, incomplete and inaccurate (probably with many typos) draft.
 Use at your own risk.
\end_layout

\end_inset


\end_layout

\begin_layout Standard
This notebook is based on an algorithms course I took in 2012 at the Hebrew
 University of Jerusalem, Israel.
 The material is based on my notes from the lectures of 
\begin_inset CommandInset href
LatexCommand href
name "Prof. Alex Samorodnitsky"
target "http://www.cs.huji.ac.il/~salex/"

\end_inset

, as well as some entries in 
\begin_inset CommandInset href
LatexCommand href
name "Wikipedia"
target "http://www.wikipedia.com/"

\end_inset

 and more.
\end_layout

\begin_layout Standard
I wrote this notebook because I find the subject interesting, and it helped
 me prepare for my exam.
 Hopefully it will help whoever is reading it as well.
\end_layout

\begin_layout Standard
Needless to say, I take no responsibility for the accuracy, completeness
 and correctness of what is written here.
 I'm not, in any way, an authority on algorithms, so take it as it is.
 That being said, I still wish this book to be as helpful as possible, so
 if you find any mistakes or inaccuracies, please send me an email to 
\series bold

\begin_inset CommandInset href
LatexCommand href
target "EyalArubas@gmail.com"
type "mailto:"

\end_inset


\series default
.
\end_layout

\begin_layout Standard
Also, you are more than welcomed to just tell me what you think of this
 book.
 I like the feedback.
\end_layout

\begin_layout Standard
The structure of the book is such that each chapter will begin with several
 examples of relevant problems.
 These examples will demonstrate a situation in which we need to reach a
 solution by solving a problem of a certain type.
 Then in the rest of the chapter we will discuss methods for solving this
 type of problems, as well as many examples.
 Each chapter is independent, so you can just jump directly to a subject
 of your choice.
\end_layout

\begin_layout Standard
The latest version of this book can be downloaded from my website at 
\series bold

\begin_inset CommandInset href
LatexCommand href
target "http://EyalArubas.com/AlgorithmsBook"

\end_inset


\series default
.
\end_layout

\begin_layout Standard
I encourage you to share this book and pass it along, if you find it useful
 of course.
\end_layout

\begin_layout Standard
\begin_inset CommandInset toc
LatexCommand tableofcontents

\end_inset


\end_layout

\begin_layout Chapter
Greedy Algorithms
\begin_inset Index idx
status open

\begin_layout Plain Layout
Greedy Algorithm
\end_layout

\end_inset


\end_layout

\begin_layout Section
Exchange Lemmas
\begin_inset Index idx
status open

\begin_layout Plain Layout
Exchange Lemma
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Oftentimes we can formulate an algorithm which we theorize solves some optimizat
ion problem.
 If it indeed does solve the problem, we want to be able to prove it.
 Usually we do it by saying that if some optimal solution to the problem
 exists, then it will coincide with the solution of our algorithm.
 Alternatively, we can say that given any other solution to the problem,
 our solution will be better.
 Our goal, then, is to show that we can take the other (optimal or not)
 solution (which is usually not unique), manipulate it without damaging
 its optimality, if it's optimal, or make it better if it's not optimal;
 and reach the solution given by our algorithm; thus showing that it, too,
 is an optimal solution.
\end_layout

\begin_layout Standard
For this purpose we use 
\emph on
exchange lemmas.

\emph default
 What these lemmas actually do is show that we can manipulate the uknown
 solution, i.e.
 
\emph on
exchange
\emph default
 part of it with part of our own solution.
 If we can show that eventually we can replace the 
\series bold
entire
\series default
 uknown solution with our own solution, and be optimal, then we have shown
 that our solution is as good and as optimal as any other.
\end_layout

\begin_layout Standard

\emph on
Unknown optimal solution
\emph default
 sounds like a fallacy.
 How can a solution be optimal without knowing what it is? The fact is that
 we don't need to know exactly what this optimal solution is, but we just
 need to know what characteristics it must hold in order to be optimal.
\end_layout

\begin_layout Standard
To demonstrate, we show several examples.
\end_layout

\begin_layout Subsection
Fractional Knapsack Problem
\begin_inset Index idx
status open

\begin_layout Plain Layout
Fractional Knapsack
\end_layout

\end_inset


\end_layout

\begin_layout Standard
This is a similar problem to the 
\begin_inset Quotes eld
\end_inset

Robbing a bank
\begin_inset Quotes erd
\end_inset

 example given at 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Robbing-a-Bank"

\end_inset

.
 We have a knapsack which can carry a certain amount of weight.
 We also have a list of items; each item has it's own weight and value.
 We want to insert items into the knapsack such that the total value of
 items inside the knapsack is maximal.
 Notice that items needn't be whole, and can be inserted partially into
 the knapsack.
\end_layout

\begin_layout Standard
Our input is:
\end_layout

\begin_layout Enumerate
\begin_inset Formula $W$
\end_inset

 - The maximum wight the knapsack can carry.
\end_layout

\begin_layout Enumerate
A list of 
\begin_inset Formula $n$
\end_inset

 items.
 Item 
\begin_inset Formula $i$
\end_inset

 is represented by the pair 
\begin_inset Formula $\left(v_{i},w_{i}\right)$
\end_inset

, where 
\begin_inset Formula $v_{i}$
\end_inset

 is the value of the item and 
\begin_inset Formula $w_{i}$
\end_inset

 is the weight of the item.
 All values and wights are non negative.
\end_layout

\begin_layout Standard
Our output should be:
\end_layout

\begin_layout Standard
A list of numbers 
\begin_inset Formula $x_{1},x_{2},...,x_{n}$
\end_inset

, where 
\begin_inset Formula $x_{i}$
\end_inset

 is the fractional amount of item 
\begin_inset Formula $i$
\end_inset

 which is inserted into the knapsack (
\begin_inset Formula $0\leq x_{i}\leq1$
\end_inset

).
\end_layout

\begin_layout Standard
The numbers 
\begin_inset Formula $x_{i}$
\end_inset

 adhere to the constraint 
\begin_inset Formula $\sum_{i=1}^{n}x_{i}w_{i}\leq W$
\end_inset

.
\end_layout

\begin_layout Standard
Our goal is to maximize the total value of items in the knapsack 
\begin_inset Formula $\sum_{i=1}^{n}x_{i}v_{i}$
\end_inset

.
\end_layout

\begin_layout Subsubsection
Algorithm
\end_layout

\begin_layout Standard
We propose a greedy algorithm which yields an optimal solution to this problem.
 We notice that greediness is the most natural approach in this case, since
 our goal is to maximal the value of the knapsack, and we can (intuitivly)
 achieve that by grabing as much as possible from the most valued items.
\end_layout

\begin_layout Standard
[TODO]
\end_layout

\begin_layout Subsection
Independent Vectors Set Problem
\begin_inset Index idx
status open

\begin_layout Plain Layout
Independent Vectors Set
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Suppose we have a finite vectors set 
\begin_inset Formula $F$
\end_inset

 of 
\begin_inset Formula $n$
\end_inset

 vectors, in some vector space 
\begin_inset Formula $V$
\end_inset

, and a positive weight functions on these vectors 
\begin_inset Formula $\mu:V\rightarrow R^{+}$
\end_inset

 (this function assigns a positive scalar value to each vector).
\end_layout

\begin_layout Standard
Our goal is to find a subset 
\begin_inset Formula $S$
\end_inset

 of 
\begin_inset Formula $F$
\end_inset

 (
\begin_inset Formula $S\subseteq F$
\end_inset

), such that the vectors in 
\begin_inset Formula $S$
\end_inset

 are linearly independent and the total weight of 
\begin_inset Formula $S$
\end_inset

 is maximized (
\begin_inset Formula $\mu\left(S\right)=\sum_{v\in S}\mu\left(v\right)$
\end_inset

).
\end_layout

\begin_layout Subsubsection
Algorithm
\end_layout

\begin_layout Standard
In this problem, too, it's evident that greediness is the most intuitive
 approach.
 We want to maximize the weight of 
\begin_inset Formula $S$
\end_inset

, so we just add the vectors with the maximal weight, as long as linear
 independence in 
\begin_inset Formula $S$
\end_inset

 is preserved.
\end_layout

\begin_layout Standard
Formally, our algorithm is:
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
placement H
wide false
sideways false
status open

\begin_layout Enumerate
Sort the vectors in 
\begin_inset Formula $F$
\end_inset

 by thier weight in descending order, such that 
\begin_inset Formula $\mu\left(v_{1}\right)\geq\mu\left(v_{2}\right)\geq...\geq\mu\left(v_{n}\right)$
\end_inset


\end_layout

\begin_layout Enumerate
Initialize 
\begin_inset Formula $S$
\end_inset

 as the empty set: 
\begin_inset Formula $S=\emptyset$
\end_inset


\end_layout

\begin_layout Enumerate
For 
\begin_inset Formula $i=1...n$
\end_inset

:
\end_layout

\begin_deeper
\begin_layout Enumerate
If 
\begin_inset Formula $S\cup\left\{ v_{i}\right\} $
\end_inset

 is linearly independent, update: 
\begin_inset Formula $S=S\cup\left\{ v_{i}\right\} $
\end_inset


\end_layout

\end_deeper
\begin_layout Enumerate
Return 
\begin_inset Formula $S$
\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Maximal weight independent vectors set algorithm
\begin_inset CommandInset label
LatexCommand label
name "alg:Maximal-weight-independent"

\end_inset


\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection
Proof
\end_layout

\begin_layout Standard
We want to prove that algorithm 
\begin_inset CommandInset ref
LatexCommand ref
reference "alg:Maximal-weight-independent"

\end_inset

 indeed returns a set of linearly independent vectors with maximal weight.
\end_layout

\begin_layout Standard
For this, we need to use the following lemma:
\end_layout

\begin_layout Lemma
\begin_inset CommandInset label
LatexCommand label
name "lem:Let--two"

\end_inset

Let 
\begin_inset Formula $A,B$
\end_inset

 two finite subsets of linearly independent vectors in vector space 
\begin_inset Formula $V$
\end_inset

.
 Suppose 
\begin_inset Formula $\left|A\right|>\left|B\right|$
\end_inset

.
 Then there is a vector 
\begin_inset Formula $v\in A\backslash B$
\end_inset

 such that 
\begin_inset Formula $B\cup\left\{ v\right\} $
\end_inset

 in linearly independent.
\end_layout

\begin_layout Standard
In others words, if 
\begin_inset Formula $A$
\end_inset

 has more vectors than 
\begin_inset Formula $B$
\end_inset

, then we can find some vector 
\begin_inset Formula $v$
\end_inset

 in 
\begin_inset Formula $A$
\end_inset

 and add it to 
\begin_inset Formula $B$
\end_inset

 such that 
\begin_inset Formula $B\cup\left\{ v\right\} $
\end_inset

 is also linearly independent.
\end_layout

\begin_layout Proof
We need to show that there is a 
\begin_inset Formula $v\in A\backslash B$
\end_inset

 that is linearly independent with 
\begin_inset Formula $B$
\end_inset

.
 We will prove by negation.
 Let's suppose that there is no such vector.
 This means that 
\series bold
all
\series default
 vectors in 
\begin_inset Formula $A$
\end_inset

 are linearly dependent with 
\begin_inset Formula $B$
\end_inset

.
 In other words, 
\begin_inset Formula $\forall v\in A:v\in B$
\end_inset

, which means that 
\begin_inset Formula $span\left(A\right)\subseteq span\left(B\right)$
\end_inset

.
 But then 
\begin_inset Formula $\dim\left(span\left(A\right)\right)\leq\dim\left(span\left(B\right)\right)$
\end_inset

.
\end_layout

\begin_layout Proof
Because 
\begin_inset Formula $A$
\end_inset

 and 
\begin_inset Formula $B$
\end_inset

 are sets of linearly independent vectors, then 
\begin_inset Formula $\left|A\right|=\dim\left(span\left(A\right)\right)$
\end_inset

 and 
\begin_inset Formula $\left|B\right|=\dim\left(span\left(B\right)\right)$
\end_inset

, but this means that 
\begin_inset Formula $\left|A\right|\leq\left|B\right|$
\end_inset

, which is a contradiction to our assumption that 
\begin_inset Formula $\left|A\right|>\left|B\right|$
\end_inset

.
 Thus we conclude that indeed there is a vector 
\begin_inset Formula $v\in A\backslash B$
\end_inset

 such that 
\begin_inset Formula $B\cup\left\{ v\right\} $
\end_inset

 in linearly independent.
\end_layout

\begin_layout Standard
Now we can continue with the proof of the optimality of algorithm 
\begin_inset CommandInset ref
LatexCommand ref
reference "alg:Maximal-weight-independent"

\end_inset

.
\end_layout

\begin_layout Standard
Remember that we want to prove that the set 
\begin_inset Formula $S$
\end_inset

 which is returned by our algorithm has the maximal weight of all linearly
 independent subsets of 
\begin_inset Formula $F$
\end_inset

.
\end_layout

\begin_layout Standard
We will prove by negation.
\end_layout

\begin_layout Standard
Suppose there is some better, optimal, solution 
\begin_inset Formula $T$
\end_inset

 such that 
\begin_inset Formula $\mu\left(T\right)>\mu\left(S\right)$
\end_inset

.
\end_layout

\begin_layout Standard
By lemma 
\begin_inset CommandInset ref
LatexCommand ref
reference "lem:Let--two"

\end_inset

, 
\begin_inset Formula $\left|S\right|=\left|T\right|$
\end_inset

, because:
\end_layout

\begin_layout Enumerate
If 
\begin_inset Formula $\left|S\right|>\left|T\right|$
\end_inset

, then by the lemma, there is a vector 
\begin_inset Formula $v\in S\backslash T$
\end_inset

 such that 
\begin_inset Formula $T\cup\left\{ v\right\} $
\end_inset

 is linearly independent.
 But this contradict the optimality of 
\begin_inset Formula $T$
\end_inset

, thus it's impossible.
\end_layout

\begin_layout Enumerate
If 
\begin_inset Formula $\left|T\right|>\left|S\right|$
\end_inset

, then by the lemma, there is a vector 
\begin_inset Formula $v\in T\backslash S$
\end_inset

 such that 
\begin_inset Formula $S\cup\left\{ v\right\} $
\end_inset

 is linearly independent.
 But this contradicts the operation of our algorithm, which was supposed
 to add this vector 
\begin_inset Formula $v$
\end_inset

 to 
\begin_inset Formula $S$
\end_inset

.
 So this is also impossible.
\end_layout

\begin_layout Standard
Thus indeed 
\begin_inset Formula $\left|S\right|=\left|T\right|$
\end_inset

.
\end_layout

\begin_layout Standard
Let's write the vectors in 
\begin_inset Formula $S$
\end_inset

 and 
\begin_inset Formula $T$
\end_inset

 by descending weight order:
\end_layout

\begin_layout Standard
\begin_inset Formula $\begin{array}{cc}
S=\left\{ v_{1},v_{2},...,v_{k}\right\}  & \mu\left(v_{1}\right)\geq\mu\left(v_{2}\right)\geq...\geq\mu\left(v_{k}\right)\\
T=\left\{ u_{1},u_{2},...,u_{k}\right\}  & \mu\left(u_{1}\right)\geq\mu\left(u_{2}\right)\geq...\geq\mu\left(u_{k}\right)
\end{array}$
\end_inset


\end_layout

\begin_layout Standard
Because 
\begin_inset Formula $\mu\left(T\right)>\mu\left(S\right)$
\end_inset

, then there must be some index 
\begin_inset Formula $i$
\end_inset

 which is the first occurance of 
\begin_inset Formula $\mu\left(u_{i}\right)>\mu\left(v_{i}\right)$
\end_inset

.
\end_layout

\begin_layout Standard
We denote:
\end_layout

\begin_layout Standard
\begin_inset Formula $A=\left\{ v_{1},...,v_{i-1}\right\} $
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $B=\left\{ u_{1},...,u_{i-1},u_{i}\right\} $
\end_inset


\end_layout

\begin_layout Standard
Obviously both 
\begin_inset Formula $A$
\end_inset

 and 
\begin_inset Formula $B$
\end_inset

 are sets of linearly independent vectors, and 
\begin_inset Formula $\left|B\right|>\left|A\right|$
\end_inset

.
 By lemma 
\begin_inset CommandInset ref
LatexCommand ref
reference "lem:Let--two"

\end_inset

, there is a vector 
\begin_inset Formula $u\in B\backslash A$
\end_inset

 such that 
\begin_inset Formula $A\cup\left\{ u\right\} $
\end_inset

 is linearly independent.
 Because 
\begin_inset Formula $S$
\end_inset

 and 
\begin_inset Formula $T$
\end_inset

 are ordered by descending weights, then the weight of this vector 
\begin_inset Formula $u$
\end_inset

 (whichever it may be) is at least as the smallest-weight vector in 
\begin_inset Formula $B,$
\end_inset

 which is 
\begin_inset Formula $u_{i}$
\end_inset

.
 In other words 
\begin_inset Formula $\mu\left(u\right)\geq\mu\left(u_{i}\right)$
\end_inset

.
 And by the definition of 
\begin_inset Formula $i$
\end_inset

, also 
\begin_inset Formula $\mu\left(u_{i}\right)>\mu\left(v_{i}\right)$
\end_inset

, and thus 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $\mu\left(u\right)>\mu\left(v_{i}\right)$
\end_inset

.
\end_layout

\begin_layout Standard
Finally we notice that this contradicts the operation of our algorithm.
 Because, if 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $\mu\left(u\right)>\mu\left(v_{i}\right)$
\end_inset

, then our algorithm should've chosen 
\begin_inset Formula $u$
\end_inset

 before 
\begin_inset Formula $v_{i}$
\end_inset

 (as we have seen, 
\begin_inset Formula $A\cup\left\{ u\right\} $
\end_inset

 is linearly independent).
\end_layout

\begin_layout Standard
We have reached a contradiction, which finishes our proof.
 
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\begin_layout Section
\begin_inset Index idx
status open

\begin_layout Plain Layout
Matroid
\end_layout

\end_inset

Matroids
\end_layout

\begin_layout Subsection
Properties of a Matroid
\end_layout

\begin_layout Standard
We define matroids through their properties.
 A matroid 
\begin_inset Formula $M$
\end_inset

 is a pair of two entities:
\end_layout

\begin_layout Enumerate
A set, 
\begin_inset Formula $S$
\end_inset

, of elements.
\end_layout

\begin_layout Enumerate
A set, 
\begin_inset Formula $I$
\end_inset

, of subsets of 
\begin_inset Formula $S$
\end_inset

.
 More specifically, 
\begin_inset Formula $I$
\end_inset

 is a subset of the power set
\begin_inset Foot
status collapsed

\begin_layout Plain Layout
The power set
\begin_inset Index idx
status open

\begin_layout Plain Layout
Power Set
\end_layout

\end_inset

, 
\begin_inset Formula $P\left(S\right)$
\end_inset

, of a set 
\begin_inset Formula $S$
\end_inset

, is defined to be the set of all the subsets of 
\begin_inset Formula $S$
\end_inset

.
 The power set is usually denoted by 
\begin_inset Formula $P\left(S\right)$
\end_inset

 or by 
\begin_inset Formula $2^{S}$
\end_inset

.
 For example, given a set 
\begin_inset Formula $S=\left\{ 1,2\right\} $
\end_inset

, then 
\begin_inset Formula $P\left(S\right)=\left\{ \emptyset,\left\{ 1\right\} ,\left\{ 2\right\} ,\left\{ 1,2\right\} \right\} $
\end_inset

.
\end_layout

\end_inset

 of 
\begin_inset Formula $S$
\end_inset

: 
\begin_inset Formula $I\subseteq P\left(S\right)$
\end_inset

.
\end_layout

\begin_layout Standard
We denote the matroid which is composed of 
\begin_inset Formula $S$
\end_inset

 and 
\begin_inset Formula $I$
\end_inset

 with 
\begin_inset Formula $M=\left(S,I\right)$
\end_inset

.
 We require 
\begin_inset Formula $I$
\end_inset

 to hold three properties:
\end_layout

\begin_layout Enumerate
Must contain the empty set (
\begin_inset Formula $\emptyset\in I$
\end_inset

 ).
\end_layout

\begin_layout Enumerate
Must hold the 
\emph on
Hereditary Property.
\end_layout

\begin_layout Enumerate
Must hold the 
\emph on
Augmentation Property.
\end_layout

\begin_layout Subsubsection
\begin_inset Index idx
status collapsed

\begin_layout Plain Layout
Heriditary Property
\end_layout

\end_inset

Heriditary Property
\end_layout

\begin_layout Standard
We remember that 
\begin_inset Formula $I$
\end_inset

 is a set of subsets of 
\begin_inset Formula $S$
\end_inset

.
 In other words, the elements of 
\begin_inset Formula $I$
\end_inset

 are sets themselfs.
 If we take some set 
\begin_inset Formula $A$
\end_inset

 in 
\begin_inset Formula $I$
\end_inset

 (
\begin_inset Formula $A\in I$
\end_inset

), then we can also look at subsets of 
\begin_inset Formula $A$
\end_inset

.
 Let's look at some subset of 
\begin_inset Formula $A$
\end_inset

 and denote it with 
\begin_inset Formula $B$
\end_inset

, so we have 
\begin_inset Formula $B\subseteq A$
\end_inset

.
 Now we can ask an interesting question - does 
\begin_inset Formula $B\in I$
\end_inset

 hold? In other words, is 
\begin_inset Formula $B$
\end_inset

 also an element in 
\begin_inset Formula $I$
\end_inset

? The answer is that sometimes it is and sometimes it isn't.
 But if it is, for all such 
\begin_inset Formula $A$
\end_inset

's and 
\begin_inset Formula $B$
\end_inset

's, then we say that 
\begin_inset Formula $I$
\end_inset

 is 
\emph on
heriditary.
\end_layout

\begin_layout Paragraph
Formal Definition
\end_layout

\begin_layout Standard
\begin_inset Formula $I$
\end_inset

 is heriditary if and only if 
\begin_inset Formula $\forall A\in I,\forall B\subseteq A:B\in I$
\end_inset

.
\end_layout

\begin_layout Standard
And in words - For every set 
\begin_inset Formula $A$
\end_inset

 in 
\begin_inset Formula $I$
\end_inset

, every subset of 
\begin_inset Formula $A$
\end_inset

 is also in 
\begin_inset Formula $I$
\end_inset

.
\end_layout

\begin_layout Subsubsection
\begin_inset Index idx
status collapsed

\begin_layout Plain Layout
Augmentation Property
\end_layout

\end_inset

Augmentation Property
\end_layout

\begin_layout Standard
Suppose we have two subsets of 
\begin_inset Formula $S$
\end_inset

 which are in 
\begin_inset Formula $I$
\end_inset

: 
\begin_inset Formula $A,B\in I$
\end_inset

.
 And suppose that 
\begin_inset Formula $B$
\end_inset

 contains more elements than 
\begin_inset Formula $A$
\end_inset

.
 Then is it possible to take some element from 
\begin_inset Formula $B$
\end_inset

, which is not also in 
\begin_inset Formula $A$
\end_inset

, move it to 
\begin_inset Formula $A$
\end_inset

 (
\series bold
augment
\series default
 
\begin_inset Formula $A$
\end_inset

), and still remain in 
\begin_inset Formula $I$
\end_inset

? If it's possible for all 
\begin_inset Formula $A$
\end_inset

's and 
\begin_inset Formula $B$
\end_inset

's in 
\begin_inset Formula $I$
\end_inset

, then we say that 
\begin_inset Formula $I$
\end_inset

 has the augmentation property.
\end_layout

\begin_layout Paragraph
Formal Definition
\end_layout

\begin_layout Standard
\begin_inset Formula $I$
\end_inset

 has the augmentation property if and only if 
\begin_inset Formula $\forall A,B\in I,\left|B\right|>\left|A\right|,\exists x\in B\backslash A:A\cup\left\{ x\right\} \in I$
\end_inset

.
\end_layout

\begin_layout Standard
And in words - For all sets 
\begin_inset Formula $A$
\end_inset

 and 
\begin_inset Formula $B$
\end_inset

 in 
\begin_inset Formula $I$
\end_inset

, such that 
\begin_inset Formula $B$
\end_inset

 is bigger than 
\begin_inset Formula $A$
\end_inset

, there exists an element 
\begin_inset Formula $x$
\end_inset

 which is in 
\begin_inset Formula $B$
\end_inset

 but not in 
\begin_inset Formula $A$
\end_inset

, such that the union of 
\begin_inset Formula $A$
\end_inset

 and 
\begin_inset Formula $x$
\end_inset

 is also in 
\begin_inset Formula $I$
\end_inset

.
\end_layout

\begin_layout Subparagraph
Note:
\end_layout

\begin_layout Standard
We only have to find just one such 
\begin_inset Formula $x$
\end_inset

.
\end_layout

\begin_layout Subsection
The Generic Greedy Algorithm
\end_layout

\begin_layout Standard
A generic greedy algorithm will solve an optimization problem if it is defined
 as a matroid.
\end_layout

\begin_layout Standard
[TODO]
\end_layout

\begin_layout Subsection
Examples
\end_layout

\begin_layout Subsubsection
The Transversal
\begin_inset Marginal
status collapsed

\begin_layout Plain Layout
Transversality is the characterization of intersection between sets.
\end_layout

\end_inset

 Matroid
\begin_inset Index idx
status open

\begin_layout Plain Layout
Transversal Matroid
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Let 
\begin_inset Formula $C_{1},C_{2},...,C_{k}$
\end_inset

 be 
\begin_inset Formula $k$
\end_inset

 sets of integers which comprise a disjoint union of 
\begin_inset Formula $\left[n\right]$
\end_inset


\begin_inset Foot
status collapsed

\begin_layout Plain Layout
\begin_inset Formula $\left[n\right]=\left\{ 1,2,3,...,n\right\} $
\end_inset


\end_layout

\end_inset

: 
\begin_inset Formula $C_{1}\uplus C_{2}\uplus...C_{k}=\left[n\right]$
\end_inset

.
\end_layout

\begin_layout Standard
We denote 
\begin_inset Formula $S=\left[n\right]$
\end_inset

, and we define 
\begin_inset Formula $I=\left\{ A\subseteq S:\forall i=1,...,k\left|A\cap C_{i}\right|\leq c\right\} $
\end_inset

.
 
\begin_inset Formula $I$
\end_inset

 Contains all the subsets of 
\begin_inset Formula $S$
\end_inset

 that have an intersection with each 
\begin_inset Formula $C_{i}$
\end_inset

 of at most 
\begin_inset Formula $c$
\end_inset

 elements.
\end_layout

\begin_layout Paragraph
Claim:
\end_layout

\begin_layout Standard
\begin_inset Formula $M=\left(S,I\right)$
\end_inset

 is a matroid.
\end_layout

\begin_layout Paragraph
Proof:
\end_layout

\begin_layout Standard
We need to prove that 
\begin_inset Formula $I$
\end_inset

 holds each of the required three properties.
\end_layout

\begin_layout Subparagraph
Contains the empty set:
\end_layout

\begin_layout Standard
Suppose 
\begin_inset Formula $A=\emptyset$
\end_inset

.
 Obviously 
\begin_inset Formula $A\subset S$
\end_inset

 and for each 
\begin_inset Formula $i=1,...,k$
\end_inset

 it is evident that 
\begin_inset Formula $\left|A\cap C_{i}\right|=\left|\emptyset\cap C_{i}\right|=0\leq c$
\end_inset

.
 Thus 
\begin_inset Formula $A\in I$
\end_inset

.
 
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\begin_layout Subparagraph
Hereditary Property:
\end_layout

\begin_layout Standard
We need to prove that 
\begin_inset Formula $\forall A\in I,\forall B\subseteq A:B\in I$
\end_inset

.
 Suppose 
\begin_inset Formula $A\in I$
\end_inset

 and 
\begin_inset Formula $B\subseteq A$
\end_inset

.
\end_layout

\begin_layout Standard
We need to show that 
\begin_inset Formula $\left|B\cap C_{i}\right|\leq c$
\end_inset

.
\end_layout

\begin_layout Standard
We know that 
\begin_inset Formula $B\subseteq A$
\end_inset

, so obviously 
\begin_inset Formula $\left|B\right|\leq\left|A\right|$
\end_inset

, thus it is evident that 
\begin_inset Formula $\left|B\cap C_{i}\right|\leq\left|A\cap C_{i}\right|$
\end_inset

 for every 
\begin_inset Formula $i$
\end_inset

.
 But because 
\begin_inset Formula $A\in I$
\end_inset

, we have 
\begin_inset Formula $\left|A\cap C_{i}\right|\leq c$
\end_inset

, which means 
\begin_inset Formula $\left|B\cap C_{i}\right|\leq\left|A\cap C_{i}\right|\leq c$
\end_inset

 for every 
\begin_inset Formula $i$
\end_inset

.
 Thus 
\begin_inset Formula $B\in I$
\end_inset

.
 
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\begin_layout Subparagraph
Augmentation Property:
\end_layout

\begin_layout Standard
We need to prove that 
\begin_inset Formula $\forall A,B\in I,\left|B\right|>\left|A\right|,\exists x\in B\backslash A:A\cup\left\{ x\right\} \in I$
\end_inset

.
\end_layout

\begin_layout Standard
Suppose 
\begin_inset Formula $A,B\in I$
\end_inset

 and 
\begin_inset Formula $\left|B\right|>\left|A\right|$
\end_inset

.
 We need to show that there is 
\begin_inset Formula $x\in B\backslash A$
\end_inset

 such that 
\begin_inset Formula $A\cup\left\{ x\right\} \in I$
\end_inset

 .
\end_layout

\begin_layout Standard
[TODO]
\end_layout

\begin_layout Chapter
Dynamic Algorithms
\begin_inset Index idx
status open

\begin_layout Plain Layout
Dynamic Algorithm
\end_layout

\end_inset


\end_layout

\begin_layout Chapter
Approximation Algorithms
\begin_inset Index idx
status open

\begin_layout Plain Layout
Approximation Algorithm
\end_layout

\end_inset


\end_layout

\begin_layout Section
Examples
\end_layout

\begin_layout Subsection
Parallel Machine Online Scheduling
\begin_inset Index idx
status open

\begin_layout Plain Layout
Parallel Machine Online Scheduling
\end_layout

\end_inset


\end_layout

\begin_layout Standard
We have tasks we need to perform, and several machines to perform those
 tasks.
 We want to assign tasks to machines in such an order that we finish all
 the tasks as early as possible.
 By 
\begin_inset Quotes eld
\end_inset

online
\begin_inset Quotes erd
\end_inset

 we mean we cannot control the order in which the tasks arrive.
\end_layout

\begin_layout Paragraph
Input:
\end_layout

\begin_layout Itemize
\begin_inset Formula $k$
\end_inset

 - Number of machines we have.
\end_layout

\begin_layout Itemize
\begin_inset Formula $t_{1},t_{2},...,t_{n}$
\end_inset

 - 
\begin_inset Formula $n$
\end_inset

 tasks, task 
\begin_inset Formula $i$
\end_inset

 takes 
\begin_inset Formula $t_{i}$
\end_inset

 amount of time to finish.
\end_layout

\begin_layout Paragraph
Output:
\end_layout

\begin_layout Standard
A function 
\begin_inset Formula $S$
\end_inset

 which assigns tasks to machines 
\begin_inset Formula $S:\left\{ t_{1},t_{2},...,t_{n}\right\} \rightarrow\left\{ 1,2,...,k\right\} $
\end_inset

.
\end_layout

\begin_layout Paragraph
Goal:
\end_layout

\begin_layout Standard
To minimize 
\begin_inset Formula $q\left(S\right)$
\end_inset

 - The time in which the last task finishes.
\end_layout

\begin_layout Standard
We will show a greedy algorithm which gives a 
\begin_inset Formula $\left(2-\frac{1}{k}\right)$
\end_inset

-approximation to the problem.
\end_layout

\begin_layout Subsubsection
Algorithm
\begin_inset CommandInset label
LatexCommand label
name "sub:Algorithm Parallel Machine Online Scheduling"

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float algorithm
placement H
wide false
sideways false
status open

\begin_layout Enumerate
For each task 
\begin_inset Formula $i$
\end_inset

 from 
\begin_inset Formula $1$
\end_inset

 to 
\begin_inset Formula $n$
\end_inset

:
\end_layout

\begin_deeper
\begin_layout Enumerate
Send task 
\begin_inset Formula $i$
\end_inset

 to the machine which is currently planned to finish first.
\end_layout

\end_deeper
\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Parallel machine online scheduling 
\begin_inset Formula $\left(2-\frac{1}{k}\right)$
\end_inset

-approximation algorithm
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
In other words, the algorithm sends the current task to the least occupied
 machine.
\end_layout

\begin_layout Standard
For example, given the following tasks:
\end_layout

\begin_layout Standard
\begin_inset Formula $t_{1}=1,t_{2}=\frac{1}{2},t_{3}=\frac{2}{3},t_{4}=1$
\end_inset


\end_layout

\begin_layout Standard
and two machines (
\begin_inset Formula $k=2$
\end_inset

), the algorithm will do the following:
\end_layout

\begin_layout Enumerate
Task 1 is assigned to machine 1: 
\begin_inset Tabular
<lyxtabular version="3" rows="2" columns="2">
<features tabularvalignment="middle">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Machine 1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Machine 2
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $t_{1}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Enumerate
Task 2 is assigned to machine 2: 
\begin_inset Tabular
<lyxtabular version="3" rows="2" columns="2">
<features tabularvalignment="middle">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Machine 1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Machine 2
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $t_{1}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $t_{2}$
\end_inset


\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Enumerate
Machine 2 is less occupied than machine 1 (
\begin_inset Formula $t_{2}<t_{1}$
\end_inset

), so task 3 is assigned to machine 2: 
\begin_inset Tabular
<lyxtabular version="3" rows="2" columns="2">
<features tabularvalignment="middle">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Machine 1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Machine 2
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $t_{1}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $t_{2},t_{3}$
\end_inset


\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Enumerate
Machine 1 is less occupied than machine 2 (
\begin_inset Formula $t_{1}<t_{2}+t_{3}$
\end_inset

), so task 4 is assigned to machine 1: 
\begin_inset Tabular
<lyxtabular version="3" rows="2" columns="2">
<features tabularvalignment="middle">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Machine 1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Machine 2
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $t_{1},t_{4}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $t_{2},t_{3}$
\end_inset


\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Standard
In this case, machine 1 will need 
\begin_inset Formula $t_{1}+t_{4}=2$
\end_inset

 time to finish, and machine 2 will need 
\begin_inset Formula $t_{2}+t_{3}=1\frac{1}{6}$
\end_inset

 time to finish.
 So 
\begin_inset Formula $q\left(S\right)=2$
\end_inset

.
\end_layout

\begin_layout Standard
This is an approximating algorithm, so it doesn't promise the best result.
 And indeed there is a better solution: 
\begin_inset Tabular
<lyxtabular version="3" rows="2" columns="2">
<features tabularvalignment="middle">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Machine 1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Machine 2
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $t_{1},t_{2}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $t_{3},t_{4}$
\end_inset


\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset

, for which 
\begin_inset Formula $q\left(S\right)=1\frac{2}{3}$
\end_inset

.
\end_layout

\begin_layout Subsubsection
Proof of 
\begin_inset Formula $\left(2-\frac{1}{k}\right)$
\end_inset

-approximation
\end_layout

\begin_layout Standard
We need to show that the algorithm in 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Algorithm Parallel Machine Online Scheduling"

\end_inset

 is 
\begin_inset Formula $\left(2-\frac{1}{k}\right)$
\end_inset

-approximating.
 In other words, if we denote the solution of the algorithm as 
\begin_inset Formula $S$
\end_inset

, and the uknown optimal solution as 
\begin_inset Formula $S^{\star}$
\end_inset

, then we need to show that 
\begin_inset Formula $q\left(S\right)\leq\left(2-\frac{1}{k}\right)q\left(S^{\star}\right)$
\end_inset

.
\end_layout

\begin_layout Standard
Obviously we don't know what is 
\begin_inset Formula $S^{\star}$
\end_inset

, but we can determine some characteristics it must hold.
 We do this in the following two lemmas.
\end_layout

\begin_layout Lemma
The time in which the last machine finishes in the optimal solution, is
 greater than the average finish time between all machines: 
\begin_inset Formula $q\left(S^{\star}\right)\geq\frac{1}{k}\sum_{i=1}^{n}t_{i}$
\end_inset

.
\end_layout

\begin_layout --Separator--

\end_layout

\begin_layout Lemma
The time in which the last machine finishes in the optimal solution, is
 greater than the time of the longest task (denoted by 
\begin_inset Formula $t_{max}$
\end_inset

): 
\begin_inset Formula $q\left(S^{\star}\right)\geq t_{max}$
\end_inset

.
\end_layout

\begin_layout Standard
We won't prove these lemmas, as they are self evident.
 We now continue with the proof.
\end_layout

\begin_layout Standard
Let's consider the last decision our algorithm has made regarding the machine
 which finishes last.
 We denote the index of the task of this decision as 
\begin_inset Formula $l$
\end_inset

 (
\begin_inset Formula $1\leq l\leq n$
\end_inset

), and the machine as 
\begin_inset Formula $j$
\end_inset

 (
\begin_inset Formula $1\leq j\leq k$
\end_inset

).
 We also denote as 
\begin_inset Formula $F_{j}$
\end_inset

 the time in which machine 
\begin_inset Formula $j$
\end_inset

 finishes after the first 
\begin_inset Formula $l-1$
\end_inset

 tasks have been assigned.
\end_layout

\begin_layout Standard
We also know that, by the definition of the algorithm, 
\begin_inset Formula $F_{j}\leq\frac{1}{k}\sum_{i=1}^{l-1}t_{i}$
\end_inset

 (because otherwise task 
\begin_inset Formula $l$
\end_inset

 wouldn't be assigned to this machine).
\end_layout

\begin_layout Standard
Since 
\begin_inset Formula $j$
\end_inset

 is the machine which finished last, we know that 
\begin_inset Formula $q\left(S\right)=F_{j}+t_{l}$
\end_inset

.
\end_layout

\begin_layout Standard
Thus we have 
\begin_inset Formula $q\left(S\right)\leq\frac{1}{k}\sum_{i=1}^{l-1}t_{i}+t_{l}=\frac{1}{k}\sum_{i=1}^{l}t_{i}+\left(1-\frac{1}{k}\right)t_{l}\leq\frac{1}{k}\sum_{i=1}^{n}t_{i}+\left(1-\frac{1}{k}\right)t_{max}\leq q\left(S^{\star}\right)+\left(1-\frac{1}{k}\right)q\left(S^{\star}\right)=\left(2-\frac{1}{k}\right)q\left(S^{\star}\right)$
\end_inset

.
 
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\begin_layout Subsection
Set Cover Problem
\begin_inset Index idx
status open

\begin_layout Plain Layout
Set Cover
\end_layout

\end_inset


\begin_inset CommandInset label
LatexCommand label
name "sub:Set-Cover-Problem"

\end_inset


\end_layout

\begin_layout Standard
We have 
\begin_inset Formula $m$
\end_inset

 subsets of 
\begin_inset Formula $\left[n\right]$
\end_inset


\begin_inset Foot
status collapsed

\begin_layout Plain Layout
\begin_inset Formula $\left[n\right]=\left\{ 1,2,...,n\right\} $
\end_inset


\end_layout

\end_inset

: 
\begin_inset Formula $A_{i}\subseteq\left[n\right]$
\end_inset

 and 
\begin_inset Formula $1\leq i\leq m$
\end_inset

.
 We also know that the sets 
\begin_inset Formula $A_{i}$
\end_inset

 cover all of 
\begin_inset Formula $\left[n\right]$
\end_inset

: 
\begin_inset Formula $\cup_{i=1}^{m}A_{i}=\left[n\right]$
\end_inset

.
\end_layout

\begin_layout Standard
We want to find the minimal partial group of these sets that still covers
 all of 
\begin_inset Formula $\left[n\right]$
\end_inset

.
 In other words, we want to find 
\begin_inset Formula $S\subseteq\left\{ 1,...,m\right\} $
\end_inset

 such that 
\begin_inset Formula $\cup_{i\in S}A_{i}=\left[n\right]$
\end_inset

 and 
\begin_inset Formula $q\left(S\right)=\left|S\right|$
\end_inset

 is minimal.
\end_layout

\begin_layout Subsubsection
\begin_inset Formula $\ln\left(n\right)$
\end_inset

-Approximating algorithm
\end_layout

\begin_layout Standard
We propose an iterative algorithm.
 In each iteration we denote by 
\begin_inset Formula $X$
\end_inset

 the set of numbers in 
\begin_inset Formula $\left[n\right]$
\end_inset

 which are still not covered (
\begin_inset Formula $X\subseteq\left[n\right]$
\end_inset

).
 We also denote by 
\begin_inset Formula $T_{i}$
\end_inset

 the relevant part of set 
\begin_inset Formula $A_{i}$
\end_inset

 (
\begin_inset Formula $T_{i}=A_{i}\cap X$
\end_inset

).
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
placement H
wide false
sideways false
status open

\begin_layout Enumerate
Initialize 
\begin_inset Formula $S=\emptyset$
\end_inset


\end_layout

\begin_layout Enumerate
Denote by 
\begin_inset Formula $i$
\end_inset

 the index in which 
\begin_inset Formula $\left|T_{i}\right|$
\end_inset

 is maximal.
\end_layout

\begin_layout Enumerate
Update:
\end_layout

\begin_deeper
\begin_layout Enumerate
\begin_inset Formula $S=S\cup\left\{ i\right\} $
\end_inset


\end_layout

\begin_layout Enumerate
\begin_inset Formula $X=X\backslash T_{i}$
\end_inset


\end_layout

\begin_layout Enumerate
\begin_inset Formula $\forall j=1,...,m:T_{j}=T_{j}\backslash T_{i}$
\end_inset


\end_layout

\end_deeper
\begin_layout Enumerate
Repeat steps 2,3 until 
\begin_inset Formula $X=\emptyset$
\end_inset


\end_layout

\begin_layout Enumerate
Return 
\begin_inset Formula $S$
\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Minimal set cover approximating algorithm
\begin_inset CommandInset label
LatexCommand label
name "alg:Minimal-set-cover-algo"

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection
Proof of 
\begin_inset Formula $\ln\left(n\right)$
\end_inset

-approximation
\end_layout

\begin_layout Standard
We want to prove that algorithm 
\begin_inset CommandInset ref
LatexCommand ref
reference "alg:Minimal-set-cover-algo"

\end_inset

 gives a 
\begin_inset Formula $\ln\left(n\right)$
\end_inset

-approximation to the optimal solution.
 In other words, we want to show that 
\begin_inset Formula $\left|S\right|\leq\ln\left(n\right)\left|S^{\star}\right|$
\end_inset

.
\end_layout

\begin_layout Standard
We prove by examining the change in the size of 
\begin_inset Formula $X$
\end_inset

 in each iteration of the algorithm.
\end_layout

\begin_layout Standard
We denote 
\begin_inset Formula $n_{j}$
\end_inset

 the size of 
\begin_inset Formula $X$
\end_inset

 after 
\begin_inset Formula $j$
\end_inset

 iterations.
 Obvisouly 
\begin_inset Formula $n_{0}=n$
\end_inset

 and if 
\begin_inset Formula $n_{j}=0$
\end_inset

 then 
\begin_inset Formula $\left|S\right|\leq j$
\end_inset

.
\end_layout

\begin_layout Standard
Let's examine the 
\begin_inset Formula $j+1$
\end_inset

 iteration of the algorithm (currently 
\begin_inset Formula $\left|S\right|=j$
\end_inset

).
 As denoted earlier, 
\begin_inset Formula $T_{i}$
\end_inset

 is the chosen set in this iteration, which means 
\begin_inset Formula $\left|T_{i}\right|$
\end_inset

 is maximal.
 By our definitions, we have 
\begin_inset Formula $n_{j+1}=\left|X\backslash T_{i}\right|=n_{j}-\left|T_{i}\right|$
\end_inset

.
\end_layout

\begin_layout Standard
We use the following lemma:
\end_layout

\begin_layout Lemma
\begin_inset Formula $\left|T_{i}\right|\geq\frac{\left|X\right|}{\left|S^{\star}\right|}$
\end_inset

.
\end_layout

\begin_layout Proof
We need to show that 
\begin_inset Formula $\left|T_{i}\right|\geq\frac{\left|X\right|}{\left|S^{\star}\right|}$
\end_inset

, or equivalently 
\begin_inset Formula $\left|X\right|\leq\left|S^{\star}\right|\cdot\left|T_{i}\right|$
\end_inset

.
\end_layout

\begin_layout Proof
\begin_inset Formula $\left|T_{i}\right|$
\end_inset

 has the maximal size of all 
\begin_inset Formula $T$
\end_inset

's, so 
\begin_inset Formula $\forall j\neq i:\left|T_{i}\right|\geq\left|T_{j}\right|$
\end_inset

.
 
\end_layout

\begin_layout Proof
\begin_inset Formula $S^{\star}$
\end_inset

 is the optimal solution.
\end_layout

\begin_layout Proof
By the definition of 
\begin_inset Formula $X$
\end_inset

 and the 
\begin_inset Formula $T$
\end_inset

's we can write 
\begin_inset Formula $\left|X\right|=\left|\cup_{j\in S^{\star}}T_{j}\right|$
\end_inset

.
\end_layout

\begin_layout Proof
So, 
\begin_inset Formula $\left|X\right|=\left|\cup_{j\in S^{\star}}T_{j}\right|\leq\cup_{j\in S^{\star}}\left|T_{j}\right|\leq\left|S^{\star}\right|\cdot\left|T_{i}\right|$
\end_inset

, as needed.
 
\end_layout

\begin_layout Standard
We continue with the proof of the approximation.
\end_layout

\begin_layout Standard
We had 
\begin_inset Formula $n_{j+1}=n_{j}-\left|T_{i}\right|$
\end_inset

, so by the lemma, 
\begin_inset Formula $n_{j+1}\leq n_{j}-\frac{\left|X\right|}{\left|S^{\star}\right|}=n_{j}-\frac{n_{j}}{\left|S^{\star}\right|}=n_{j}\left(1-\frac{1}{\left|S^{\star}\right|}\right)$
\end_inset

.
 This is a recursive formula from which we can conclude:
\end_layout

\begin_layout Standard
\begin_inset Formula $n_{j}\leq n_{j-1}\left(1-\frac{1}{\left|S^{\star}\right|}\right)\leq n_{j-2}\left(1-\frac{1}{\left|S^{\star}\right|}\right)^{2}\leq...\leq n_{0}\left(1-\frac{1}{\left|S^{\star}\right|}\right)^{j}=n\left(1-\frac{1}{\left|S^{\star}\right|}\right)^{j}$
\end_inset

.
\end_layout

\begin_layout Standard
We will employ the following lemma (which will not be proven here):
\end_layout

\begin_layout Lemma
\begin_inset Formula $\left(1+a\right)^{b}<e^{ab}$
\end_inset

, for all non zero 
\begin_inset Formula $a,b\in\mathbb{R}$
\end_inset

.
\begin_inset CommandInset label
LatexCommand label
name "lem:,-for-all-1+a^b<e^ab"

\end_inset


\end_layout

\begin_layout Standard
We use the lemma and obtain: 
\begin_inset Formula $n_{j}\leq n\left(1-\frac{1}{\left|S^{\star}\right|}\right)^{j}\leq ne^{\frac{-j}{\left|S^{\star}\right|}}$
\end_inset

.
\end_layout

\begin_layout Standard
Since 
\begin_inset Formula $n_{j}$
\end_inset

 in an integer, then for 
\begin_inset Formula $j=\left|S^{\star}\right|\ln\left(n\right)$
\end_inset

 we obtain 
\begin_inset Formula $n_{j}=0$
\end_inset

, which, as stated earlier, means that 
\begin_inset Formula $\left|S\right|\leq\left|S^{\star}\right|\ln\left(n\right)$
\end_inset

, thus completing the proof.
 
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\begin_layout Subsection
Max-Cut Problem
\begin_inset Index idx
status open

\begin_layout Plain Layout
Max-Cut
\end_layout

\end_inset


\begin_inset CommandInset label
LatexCommand label
name "sub:Max-Cut-Problem"

\end_inset


\end_layout

\begin_layout Standard
We have an undirected graph 
\begin_inset Formula $G=\left(V,E\right)$
\end_inset

.
\end_layout

\begin_layout Standard
A cut in the graph, 
\begin_inset Formula $C=\left(A,B\right)$
\end_inset

, is such that 
\begin_inset Formula $A,B\subseteq V$
\end_inset

 and 
\begin_inset Formula $A\uplus B=V$
\end_inset


\begin_inset Foot
status collapsed

\begin_layout Plain Layout
\begin_inset Formula $\uplus$
\end_inset

 is the symbol for disjoin union, i.e.
 
\begin_inset Formula $A\uplus B=V$
\end_inset

 means 
\begin_inset Formula $A\cup B=V$
\end_inset

 and 
\begin_inset Formula $A\cap B=\emptyset$
\end_inset

.
\end_layout

\end_inset

.
\end_layout

\begin_layout Standard
We denote with 
\begin_inset Formula $E_{C}$
\end_inset

 the edges of the cut: 
\begin_inset Formula $E_{C}=\left\{ \left(i,j\right)\in E:i\in A,j\in B\right\} $
\end_inset

.
\end_layout

\begin_layout Standard
Our goal is to find a cut 
\begin_inset Formula $C$
\end_inset

 with maximum edges in the graph (maximal 
\begin_inset Formula $\left|E_{C}\right|$
\end_inset

).
\end_layout

\begin_layout Subsubsection
\begin_inset Formula $2$
\end_inset

-approximating algorithm
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
wide false
sideways false
status open

\begin_layout Enumerate
Initialize two sets: 
\begin_inset Formula $A=V$
\end_inset

, 
\begin_inset Formula $B=\emptyset$
\end_inset

.
\end_layout

\begin_layout Enumerate
For each vertex 
\begin_inset Formula $i\in V$
\end_inset

:
\end_layout

\begin_deeper
\begin_layout Enumerate
Denote by 
\begin_inset Formula $X$
\end_inset

 the set to which 
\begin_inset Formula $i$
\end_inset

 belongs (
\begin_inset Formula $A$
\end_inset

 or 
\begin_inset Formula $B$
\end_inset

).
\end_layout

\begin_layout Enumerate
Denote by 
\begin_inset Formula $Y$
\end_inset

 the other set.
\end_layout

\begin_layout Enumerate
If 
\begin_inset Formula $i$
\end_inset

 has more neighbors in 
\begin_inset Formula $X$
\end_inset

 than in 
\begin_inset Formula $Y$
\end_inset

, move 
\begin_inset Formula $i$
\end_inset

 to 
\begin_inset Formula $Y$
\end_inset

.
\end_layout

\end_deeper
\begin_layout Enumerate
Repeat step 2 until no more changes occur.
\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Max-Cut 
\begin_inset Formula $2$
\end_inset

-approximating algorithm
\end_layout

\end_inset


\begin_inset CommandInset label
LatexCommand label
name "enu:Max-Cut-2-approximating algorithm"

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
At first it may seem the algorithm might never stop.
 But we notice that the quality of any solution (
\begin_inset Formula $\left|E_{C}\right|$
\end_inset

) is bounded by the number of edges in the graph (
\begin_inset Formula $\left|E_{C}\right|\leq\left|E\right|$
\end_inset

).
 In each iteration of step 2, we move a vertex to the set in which it has
 less neighbors (or leave it, if it's already there), which means that 
\begin_inset Formula $\left|E_{C}\right|$
\end_inset

 either increases or stays the same, but it never decreases.
 But because 
\begin_inset Formula $\left|E_{C}\right|$
\end_inset

 is bounded, then the algorithm must eventually stop.
\end_layout

\begin_layout Subsubsection
Proof of 
\begin_inset Formula $2$
\end_inset

-approximation
\end_layout

\begin_layout Standard
We denote by 
\begin_inset Formula $d_{v}$
\end_inset

 the degree of vertex 
\begin_inset Formula $v$
\end_inset

, and by 
\begin_inset Formula $v_{C}$
\end_inset

 the number of edges in the cut that touch vertex 
\begin_inset Formula $v$
\end_inset

.
\end_layout

\begin_layout Standard
Every edge in the cut touches two vertices, so 
\begin_inset Formula $\left|E_{C}\right|=\frac{1}{2}\sum_{v\in V}v_{C}$
\end_inset

.
\end_layout

\begin_layout Standard
By the operation of the algorithm, it makes sure that for every vertex,
 at least half of its neighbors are in the other set, which means that at
 least half of the edges that touch this vetex are in the cut: 
\begin_inset Formula $\forall v\in V:v_{C}\geq\frac{1}{2}d_{v}$
\end_inset

.
\end_layout

\begin_layout Standard
So: 
\begin_inset Formula $\left|E_{C}\right|=\frac{1}{2}\sum_{v\in V}v_{C}\geq\frac{1}{4}\sum_{v\in V}d_{v}$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Formula $\sum_{v\in V}d_{v}$
\end_inset

 is exactly twice the edges in the graph (We count the number of edges for
 every vertex, but every edge touches two vertices): 
\begin_inset Formula $\sum_{v\in V}d_{v}=2\left|E\right|$
\end_inset

.
\end_layout

\begin_layout Standard
Obviously, the optimal solution (denoted 
\begin_inset Formula $C^{\star}$
\end_inset

) doesn't have more edges in the cut than there are edges in the graph:
 
\begin_inset Formula $\left|E_{C^{\star}}\right|\leq\left|E\right|$
\end_inset


\end_layout

\begin_layout Standard
So now we have 
\begin_inset Formula $\left|E_{C}\right|\geq\frac{1}{4}2\left|E\right|=\frac{1}{2}\left|E\right|\geq\frac{1}{2}\left|E_{C^{\star}}\right|$
\end_inset

, which completes the proof.
 
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\begin_layout Subsection
Max-K-Cut
\end_layout

\begin_layout Standard
As in the 
\emph on
Max-Cut
\emph default
 problem in 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Max-Cut-Problem"

\end_inset

, here also we have an undirected graph 
\begin_inset Formula $G=\left(V,E\right)$
\end_inset

.
 Our goal here is to find a partition of 
\begin_inset Formula $V$
\end_inset

 into 
\begin_inset Formula $k$
\end_inset

 disjoint sets 
\begin_inset Formula $V_{1},V_{2},...,V_{k}$
\end_inset

, such that the sum of the number of edges in the cuts (i.e.
 between all pairs of 
\begin_inset Formula $V_{i},V_{j}$
\end_inset

) is maximized.
\end_layout

\begin_layout Standard
We notice that the 
\emph on
Max-Cut
\emph default
 problem is a private case of the current problem with 
\begin_inset Formula $k=2$
\end_inset

.
\end_layout

\begin_layout Subsubsection
\begin_inset Formula $\left(1-\frac{1}{k}\right)$
\end_inset

-approximating algorithm
\end_layout

\begin_layout Standard
This algorithm is very similar to algorithm 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:Max-Cut-2-approximating algorithm"

\end_inset

.
 Here, too, in each iteration we move the current vertex into the set in
 which most of it's neighbors will be from the other sets.
\end_layout

\begin_layout Standard
We denote by 
\begin_inset Formula $d_{v}$
\end_inset

 the degree of vertex 
\begin_inset Formula $v$
\end_inset

, by 
\begin_inset Formula $N_{v}^{in}$
\end_inset

 the number of neighbors 
\begin_inset Formula $v$
\end_inset

 has inside it's current set, and by 
\begin_inset Formula $N_{v}^{out}$
\end_inset

 the number of neighbors 
\begin_inset Formula $v$
\end_inset

 has outside of it's current set.
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
wide false
sideways false
status open

\begin_layout Enumerate
Partition 
\begin_inset Formula $V$
\end_inset

 into 
\begin_inset Formula $k$
\end_inset

 disjoint sets 
\begin_inset Formula $V_{1},V_{2},...,V_{k}$
\end_inset

 (randomly).
\end_layout

\begin_layout Enumerate
For each vertex 
\begin_inset Formula $i\in V$
\end_inset

:
\end_layout

\begin_deeper
\begin_layout Enumerate
If 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $N_{v}^{in}>\frac{d_{v}}{k}$
\end_inset

, move 
\begin_inset Formula $v$
\end_inset

 from it's current set 
\begin_inset Formula $V_{i}$
\end_inset

 to another set 
\begin_inset Formula $V_{j}$
\end_inset

, such that the new 
\family default
\series default
\shape default
\size default
\emph default
\bar default
\strikeout default
\uuline default
\uwave default
\noun default
\color inherit

\begin_inset Formula $N_{v}^{out}$
\end_inset

 is maximal.
\end_layout

\end_deeper
\begin_layout Enumerate
Repeat step 2 until no more changes occur.
\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Max-K-Cut 
\begin_inset Formula $\left(1-\frac{1}{k}\right)$
\end_inset

-approximating algorithm
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
From the same considerations of algorithm 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:Max-Cut-2-approximating algorithm"

\end_inset

, this algorithm must also eventually stop.
\end_layout

\begin_layout Subsubsection
Proof of 
\begin_inset Formula $\left(1-\frac{1}{k}\right)$
\end_inset

-approximation
\end_layout

\begin_layout Standard
For a solution 
\begin_inset Formula $S$
\end_inset

 we denote by 
\begin_inset Formula $\left|E_{S}\right|$
\end_inset

 the number of edges in the cuts defined by 
\begin_inset Formula $S$
\end_inset

.
 If 
\begin_inset Formula $S$
\end_inset

 is the solution of our algorithm, and 
\begin_inset Formula $S^{\star}$
\end_inset

 is the optimal solution, we need to show that 
\begin_inset Formula $\left|E_{S}\right|\geq\left(1-\frac{1}{k}\right)\left|E_{S^{\star}}\right|$
\end_inset

.
\end_layout

\begin_layout Standard
We notice the following:
\end_layout

\begin_layout Itemize

\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none
\begin_inset Formula $\left|E_{S}\right|=\frac{1}{2}\sum_{v\in V}N_{v}^{out}$
\end_inset

 
\end_layout

\begin_layout Itemize
\begin_inset Formula $\forall v\in V:d_{v}=N_{v}^{out}+N_{v}^{in}$
\end_inset


\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none
.
\end_layout

\begin_layout Itemize
\begin_inset Formula $\left|E\right|=\frac{1}{2}\sum_{v\in V}d_{v}$
\end_inset

.
\end_layout

\begin_layout Standard
After the algorithm finishes its operation, we know that 
\begin_inset Formula $\forall v\in V:N_{v}^{in}<\frac{d_{v}}{k}$
\end_inset

.
\end_layout

\begin_layout Standard
Thus we conclude 
\begin_inset Formula $\forall v\in V:N_{v}^{out}\geq\frac{k-1}{k}d_{v}$
\end_inset

.
\end_layout

\begin_layout Standard
So now we can write: 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $\left|E_{S}\right|=\frac{1}{2}\sum_{v\in V}N_{v}^{out}\geq\frac{1}{2}\frac{k-1}{k}\sum_{v\in V}d_{v}=\frac{k-1}{k}\left|E\right|$
\end_inset

.
\end_layout

\begin_layout Standard
We also know that in any solution, as well as the optimal solution, the
 number of edges in the cuts cannot exeed the number of edges in the graph,
 so: 
\begin_inset Formula $\left|E_{S^{\star}}\right|\leq\left|E\right|$
\end_inset

.
\end_layout

\begin_layout Standard
So finally we have: 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $\left|E_{S}\right|\geq\frac{k-1}{k}\left|E\right|\geq\frac{k-1}{k}\left|E_{S^{\star}}\right|=\left(1-\frac{1}{k}\right)\left|E_{S^{\star}}\right|$
\end_inset

, thus completing the proof.
 
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\begin_layout Subsection
Vertex Cover
\end_layout

\begin_layout Standard
We have a graph of 
\begin_inset Formula $m$
\end_inset

 vertices and 
\begin_inset Formula $n$
\end_inset

 edges: 
\begin_inset Formula $G=\left(V,E\right)$
\end_inset

.
\end_layout

\begin_layout Standard
We want to find a subset 
\begin_inset Formula $S\subseteq V$
\end_inset

 such that every edge has at least one vertex in that set.
 In other words 
\begin_inset Formula $\forall e=\left(i,j\right)\in E:i\in S\, or\, j\in S$
\end_inset

.
\end_layout

\begin_layout Standard
Our goal is to find such a set with minimal size (minimize 
\begin_inset Formula $q\left(S\right)=\left|S\right|$
\end_inset

).
\end_layout

\begin_layout Standard
We notice this is a special case of the 
\emph on
Set Cover Problem
\emph default
 presented in 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Set-Cover-Problem"

\end_inset

, because if we number the edges of the graph 
\begin_inset Formula $1,...,n$
\end_inset

, we can define the set 
\begin_inset Formula $A_{i}$
\end_inset

 to be the vertices of edge 
\begin_inset Formula $i$
\end_inset

.
 So we can solve this problem with the same 
\begin_inset Formula $\ln\left(n\right)$
\end_inset

-approximating algorithm.
\end_layout

\begin_layout Standard
Here, however, we will show a 
\begin_inset Formula $2$
\end_inset

-approximating algorithm.
\end_layout

\begin_layout Standard
First we will see several examples.
\end_layout

\begin_layout Example
The complete graph with 
\begin_inset Formula $m$
\end_inset

 vertices (
\begin_inset Formula $K_{m}$
\end_inset

).
 In this case 
\begin_inset Formula $q\left(S^{\star}\right)=m-1$
\end_inset

, because if we leave out 2 vertices, the edge which connects them will
 not be covered.
\end_layout

\begin_layout --Separator--

\end_layout

\begin_layout Example
The bipartite complete graph 
\begin_inset Formula $K_{a,b}$
\end_inset

.
 If 
\begin_inset Formula $a\leq b$
\end_inset

 then obviously 
\begin_inset Formula $q\left(S^{\star}\right)=a$
\end_inset

.
\end_layout

\begin_layout --Separator--

\end_layout

\begin_layout Example
A matching of size 
\begin_inset Formula $k$
\end_inset

 - a graph with 
\begin_inset Formula $k$
\end_inset

 edges where each vertex has degree of excatly 1 (connected to exactly 1
 edge).
 Obviously 
\begin_inset Formula $q\left(S^{\star}\right)=k$
\end_inset

.
\end_layout

\begin_layout Corollary
If a graph 
\series bold
contains
\series default
 a matching of size 
\begin_inset Formula $k$
\end_inset

, then 
\begin_inset Formula $q\left(S^{\star}\right)\geq k$
\end_inset

.
\begin_inset CommandInset label
LatexCommand label
name "cor:If-a-graph"

\end_inset


\end_layout

\begin_layout Subsubsection
\begin_inset Formula $2$
\end_inset

-approximating algorithm
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
wide false
sideways false
status open

\begin_layout Enumerate
Initialize: 
\begin_inset Formula $S=\emptyset$
\end_inset

, 
\begin_inset Formula $X=E$
\end_inset

.
\end_layout

\begin_layout Enumerate
While 
\begin_inset Formula $X\neq\emptyset$
\end_inset

:
\end_layout

\begin_deeper
\begin_layout Enumerate
Choose some edge 
\begin_inset Formula $e=\left(i,j\right)\in X$
\end_inset

.
\begin_inset CommandInset label
LatexCommand label
name "enu:Choose-some-edge"

\end_inset


\end_layout

\begin_layout Enumerate
Add to 
\begin_inset Formula $S$
\end_inset

 vertices 
\begin_inset Formula $i,j$
\end_inset

: 
\begin_inset Formula $S=S\cup\left\{ i,j\right\} $
\end_inset

.
\end_layout

\begin_layout Enumerate
Remove from 
\begin_inset Formula $X$
\end_inset

 all edges which are covered by 
\begin_inset Formula $i$
\end_inset

 or 
\begin_inset Formula $j$
\end_inset

: 
\begin_inset Formula $X=X\backslash\left\{ All\, edges\, that\, touch\, i\, or\, j\right\} $
\end_inset

.
\begin_inset CommandInset label
LatexCommand label
name "enu:Remove-from-"

\end_inset


\end_layout

\end_deeper
\begin_layout Enumerate
Return 
\begin_inset Formula $S$
\end_inset

.
\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Vertex cover 
\begin_inset Formula $2$
\end_inset

-approximating algorithm
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection
Proof of 
\begin_inset Formula $2$
\end_inset

-approximation
\end_layout

\begin_layout Standard
We denote the solution of the algorithm with 
\begin_inset Formula $S$
\end_inset

, and the optimal solution with 
\begin_inset Formula $S^{\star}$
\end_inset

.
\end_layout

\begin_layout Standard
We want to show that 
\begin_inset Formula $q\left(S\right)\leq2q\left(S^{\star}\right)$
\end_inset

 (
\begin_inset Formula $\left|S\right|\leq2\left|S^{\star}\right|$
\end_inset

).
\end_layout

\begin_layout Standard
By the structure of the algorithm, 
\begin_inset Formula $\left|S\right|$
\end_inset

 is even (we add two vertices each iteration), so we can write 
\begin_inset Formula $\left|S\right|=2k$
\end_inset

 for some 
\begin_inset Formula $k$
\end_inset

.
 We notice that all the edges the algorithm choses in step 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:Choose-some-edge"

\end_inset

 have no vertices in common (becuase of step 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:Remove-from-"

\end_inset

).
 In other words, these edges make a matching of 
\begin_inset Formula $k$
\end_inset

 edges.
 By corollary 
\begin_inset CommandInset ref
LatexCommand ref
reference "cor:If-a-graph"

\end_inset

 we conclude 
\begin_inset Formula $\left|S^{\star}\right|\geq k$
\end_inset

.
\end_layout

\begin_layout Standard
Finally we have 
\begin_inset Formula $\left|S\right|=2k\leq2\left|S^{\star}\right|$
\end_inset

, thus completing the proof.
 
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\begin_layout Subsection
Metric Travelling Salesman
\end_layout

\begin_layout Standard
We have a 
\series bold
complete
\series default
 undirected graph 
\begin_inset Formula $G=\left(V,E\right)$
\end_inset

, and a 
\series bold
metric
\series default
 weight function 
\begin_inset Formula $w:E\rightarrow\mathbb{R}^{+}$
\end_inset

.
 Since 
\begin_inset Formula $w$
\end_inset

 is metric, is holds the triangle inequallity: 
\begin_inset Formula $\forall i,j,k\in V:w\left(i,k\right)\leq w\left(i,j\right)+w\left(j,k\right)$
\end_inset

.
\end_layout

\begin_layout Standard
Our goal is to find a simple cycle 
\begin_inset Formula $C$
\end_inset

 in the graph (
\begin_inset Formula $C=\left(e_{1},e_{2},...,e_{k}\right)$
\end_inset

) which touches 
\series bold
every
\series default
 vertex exactly once, and has a minimal weight (
\begin_inset Formula $w\left(C\right)=\sum_{e\in C}w\left(e\right)$
\end_inset

 is minimal).
\end_layout

\begin_layout Subsubsection
\begin_inset Formula $2$
\end_inset

-approximating algorithm
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
wide false
sideways false
status open

\begin_layout Enumerate
Initialize 
\begin_inset Formula $C=\emptyset$
\end_inset

.
\end_layout

\begin_layout Enumerate
Find a minimal spanning tree (MST) of the graph, and denote it with 
\begin_inset Formula $T$
\end_inset

.
\end_layout

\begin_layout Enumerate
Double the edges in 
\begin_inset Formula $T$
\end_inset

 to form a cycle which touches all the vertices, and denote it with 
\begin_inset Formula $T^{'}$
\end_inset

.
\end_layout

\begin_layout Enumerate
Traverse the edges of 
\begin_inset Formula $T^{'}$
\end_inset

 starting from some arbitrary vertex:
\begin_inset CommandInset label
LatexCommand label
name "enu:Traverse-the-edges"

\end_inset


\end_layout

\begin_deeper
\begin_layout Enumerate
Denote the current vertex with 
\begin_inset Formula $u$
\end_inset

.
\end_layout

\begin_layout Enumerate
Denote the next 
\series bold
unvisited
\series default
 vertex with 
\begin_inset Formula $v$
\end_inset

.
\end_layout

\begin_layout Enumerate
Add the edge 
\begin_inset Formula $\left(u,v\right)$
\end_inset

 to 
\begin_inset Formula $C$
\end_inset

: 
\begin_inset Formula $C=C\cup\left\{ \left(u,v\right)\right\} $
\end_inset

.
\end_layout

\begin_layout Enumerate
Continue the next iteration from 
\begin_inset Formula $v$
\end_inset

.
\end_layout

\end_deeper
\begin_layout Enumerate
Return 
\begin_inset Formula $C$
\end_inset

.
\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Metric Travelling Salesman 
\begin_inset Formula $2$
\end_inset

-approximating algorithm
\end_layout

\end_inset


\begin_inset CommandInset label
LatexCommand label
name "enu:m-tsp-2-approx-algo"

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Paragraph
Proof of correctness
\end_layout

\begin_layout Standard
We need to prove that the returned 
\begin_inset Formula $C$
\end_inset

 is indeed a simple cycle which touches every vertex exactly once.
\end_layout

\begin_layout Standard
We notice that 
\begin_inset Formula $T^{'}$
\end_inset

 is a cycle (not simple) which touches every vertex.
 In step 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:Traverse-the-edges"

\end_inset

, by traversing 
\series bold
every 
\series default
edge of 
\begin_inset Formula $T^{'}$
\end_inset

, we visit 
\series bold
every
\series default
 vertex in the graph.
 But because we only visit the 
\series bold
unvisited
\series default
 vertices, we know that we touch every vertex 
\series bold
once
\series default
.
 Because 
\begin_inset Formula $G$
\end_inset

 is a 
\series bold
complete
\series default
 graph, there is always an edge between the vertices 
\begin_inset Formula $u$
\end_inset

 and 
\begin_inset Formula $v$
\end_inset

 in step 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:Traverse-the-edges"

\end_inset

, thus making 
\begin_inset Formula $C$
\end_inset

 a simple cycle.
 
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\begin_layout Subsubsection
Proof of 
\begin_inset Formula $2$
\end_inset

-approximation
\end_layout

\begin_layout Standard
We denote by 
\begin_inset Formula $C$
\end_inset

 the solution of algorithm 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:m-tsp-2-approx-algo"

\end_inset

, and by 
\begin_inset Formula $C^{\star}$
\end_inset

 the optimal solution.
 We need to prove that 
\begin_inset Formula $w\left(C\right)\leq2w\left(C^{\star}\right)$
\end_inset

.
\end_layout

\begin_layout Claim
\begin_inset CommandInset label
LatexCommand label
name "Let-tmst-be"

\end_inset

Let 
\begin_inset Formula $T_{MST}$
\end_inset

 be a minimal spanning tree of 
\begin_inset Formula $G$
\end_inset

.
 Then 
\begin_inset Formula $w\left(T_{MST}\right)\leq w\left(C^{\star}\right)$
\end_inset

.
\end_layout

\begin_layout Proof
Suppose we have 
\begin_inset Formula $C^{\star}$
\end_inset

.
 We remove one of it's edges.
 Now we have a spanning tree 
\begin_inset Formula $T$
\end_inset

.
 Removing an edge from 
\begin_inset Formula $C^{\star}$
\end_inset

 decreases it's weight by some amount.
 Thus we have 
\begin_inset Formula $w\left(T\right)\leq w\left(C^{\star}\right)$
\end_inset

.
 From the minimality of 
\begin_inset Formula $T_{MST}$
\end_inset

 we have 
\begin_inset Formula $w\left(T_{MST}\right)\leq w\left(T\right)$
\end_inset

.
 So finally we have 
\begin_inset Formula $w\left(T_{MST}\right)\leq w\left(C^{\star}\right)$
\end_inset

.
 
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\begin_layout Standard
In step 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:Traverse-the-edges"

\end_inset

 of the algorithm, from the current vertex 
\begin_inset Formula $u$
\end_inset

 we connect an edge to the next 
\series bold
unvisited
\series default
 vertex 
\begin_inset Formula $v$
\end_inset

, so we skip all the visited vertices between them (by the order defined
 by 
\begin_inset Formula $T^{'}$
\end_inset

).
 So by the triangle inequiallity (remember, 
\begin_inset Formula $w$
\end_inset

 is metric), we conclude: 
\begin_inset Formula $w\left(C\right)\leq w\left(T^{'}\right)$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Formula $T^{'}$
\end_inset

 is formed by doubling the edges of 
\begin_inset Formula $T$
\end_inset

, so 
\begin_inset Formula $w\left(T^{'}\right)=2w\left(T\right)$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Formula $T$
\end_inset

 is a minimal spanning tree, so by claim 
\begin_inset CommandInset ref
LatexCommand ref
reference "Let-tmst-be"

\end_inset

 we have 
\begin_inset Formula $w\left(T\right)\leq w\left(C^{\star}\right)$
\end_inset

.
\end_layout

\begin_layout Standard
Finally we can write 
\begin_inset Formula $w\left(C\right)\leq w\left(T^{'}\right)=2w\left(T\right)\leq2w\left(C^{\star}\right)$
\end_inset

.
 Thus completing the proof.
 
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\begin_layout Subsubsection
\begin_inset Formula $1.5$
\end_inset

-approximating algorithm (by Christofides)
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
wide false
sideways false
status open

\begin_layout Enumerate
Initialize 
\begin_inset Formula $C=\emptyset$
\end_inset

.
\end_layout

\begin_layout Enumerate
Find a minimal spanning tree for 
\begin_inset Formula $G$
\end_inset

 and denote it with 
\begin_inset Formula $T$
\end_inset

.
\end_layout

\begin_layout Enumerate
Denotations:
\end_layout

\begin_deeper
\begin_layout Enumerate
\begin_inset Formula $A$
\end_inset

 - The vertices with odd degree in 
\begin_inset Formula $T$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $G_{A}$
\end_inset

 - The induced graph of 
\begin_inset Formula $A$
\end_inset

 by 
\begin_inset Formula $G$
\end_inset

.
\begin_inset CommandInset label
LatexCommand label
name "enu:---The-induced-graph-of-A-by-G"

\end_inset


\end_layout

\end_deeper
\begin_layout Enumerate
Find a minimal perfect matching 
\begin_inset Formula $M^{*}$
\end_inset

 in 
\begin_inset Formula $G_{A}$
\end_inset

.
\end_layout

\begin_layout Enumerate
Let 
\begin_inset Formula $C^{'}$
\end_inset

 be the edges in 
\begin_inset Formula $M^{*}$
\end_inset

 combined with the edges in 
\begin_inset Formula $T$
\end_inset

 (forming a multigraph).
\begin_inset CommandInset label
LatexCommand label
name "enu:Let-c'-be-the-edges-in-m*-and-T"

\end_inset


\end_layout

\begin_layout Enumerate
Find an Euler cycle in 
\begin_inset Formula $C^{'}$
\end_inset

 and denote it with 
\begin_inset Formula $C_{e}$
\end_inset

.
\begin_inset CommandInset label
LatexCommand label
name "enu:Find-an-Euler"

\end_inset


\end_layout

\begin_layout Enumerate
Traverse the edges of 
\begin_inset Formula $C_{e}$
\end_inset

 starting from some arbitrary vertex:
\end_layout

\begin_deeper
\begin_layout Enumerate
Denote the current vertex with 
\begin_inset Formula $u$
\end_inset

.
\end_layout

\begin_layout Enumerate
Denote the next 
\series bold
unvisited
\series default
 vertex with 
\begin_inset Formula $v$
\end_inset

.
\end_layout

\begin_layout Enumerate
Add the edge 
\begin_inset Formula $\left(u,v\right)$
\end_inset

 to 
\begin_inset Formula $C$
\end_inset

: 
\begin_inset Formula $C=C\cup\left\{ \left(u,v\right)\right\} $
\end_inset

.
\end_layout

\begin_layout Enumerate
Continue the next iteration from 
\begin_inset Formula $v$
\end_inset

.
\end_layout

\end_deeper
\begin_layout Enumerate
Return 
\begin_inset Formula $C$
\end_inset

.
\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Metric Travelling Salesman 
\begin_inset Formula $1.5$
\end_inset

-approximating algorithm (by Christofides)
\end_layout

\end_inset


\begin_inset CommandInset label
LatexCommand label
name "enu:m-tsp-1.5-approx-algo"

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Paragraph
Notes:
\end_layout

\begin_layout Enumerate
In step 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:---The-induced-graph-of-A-by-G"

\end_inset

, 
\begin_inset Formula $G_{A}$
\end_inset

 is a complete graph, because it's induced on a complete graph.
\end_layout

\begin_layout Enumerate
In step 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:Find-an-Euler"

\end_inset

, an 
\emph on
Euler cycle
\emph default
 is a cycle (simple or not) which touches every vertex exactly once.
\end_layout

\begin_layout Standard
In order to use the algorithm, we need the following claims:
\end_layout

\begin_layout Claim
Every graph 
\begin_inset Formula $G$
\end_inset

 has an even number of vertices with odd degree.
\end_layout

\begin_layout Proof
Let 
\begin_inset Formula $d_{v}$
\end_inset

 denote the degree of vertex 
\begin_inset Formula $v$
\end_inset

.
 In every graph 
\begin_inset Formula $G=\left(V,E\right)$
\end_inset

, 
\begin_inset Formula $\sum_{v\in V}d_{v}=2\left|E\right|$
\end_inset

.
 If the number of vertices with odd 
\begin_inset Formula $d_{v}$
\end_inset

 is odd, then 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $\sum_{v\in V}d_{v}$
\end_inset

 will be odd.
 But this is impossible.
 
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\begin_layout Claim
Every connected graph in which for every vertex 
\begin_inset Formula $v$
\end_inset

, 
\begin_inset Formula $d_{v}$
\end_inset

 is even, there is an Euler cycle.
\begin_inset CommandInset label
LatexCommand label
name "Every-connected-graph-even-euler-cycle"

\end_inset


\end_layout

\begin_layout --Separator--

\end_layout

\begin_layout Claim
In a graph with even number of vertices, it is possible to find a minimal
 perfect matching in polynomial runtime (Using Edmond's 
\emph on
Path, Trees and Flowers
\emph default
 algorithm, or Vazirani's algorithm).
\end_layout

\begin_layout --Separator--

\end_layout

\begin_layout Claim
In 
\begin_inset Formula $C^{'}$
\end_inset

 there is a cycle.
\end_layout

\begin_layout Proof
We will show that every vertex 
\begin_inset Formula $i$
\end_inset

 in 
\begin_inset Formula $C^{'}$
\end_inset

 has an even degree, so it must contain a cycle.
 If 
\begin_inset Formula $d_{i}$
\end_inset

 is even in 
\begin_inset Formula $T$
\end_inset

, then adding 
\begin_inset Formula $M^{*}$
\end_inset

 does not affect 
\begin_inset Formula $i$
\end_inset

's degree, because 
\begin_inset Formula $M^{*}$
\end_inset

 is a matching of vertices with odd degree.
 If 
\begin_inset Formula $d_{i}$
\end_inset

 is odd in 
\begin_inset Formula $T$
\end_inset

, then adding 
\begin_inset Formula $M^{*}$
\end_inset

 adds 
\begin_inset Formula $1$
\end_inset

 to 
\begin_inset Formula $d_{i}$
\end_inset

, because 
\begin_inset Formula $M^{*}$
\end_inset

 is a matching, and as such connects only one edge to each vertex.
\end_layout

\begin_layout Claim
In 
\begin_inset Formula $C^{'}$
\end_inset

 there is an Euler cycle.
\end_layout

\begin_layout Proof
We have shown that the degree of every vertex in 
\begin_inset Formula $C^{'}$
\end_inset

 is even, so we can use claim 
\begin_inset CommandInset ref
LatexCommand ref
reference "Every-connected-graph-even-euler-cycle"

\end_inset

.
\end_layout

\begin_layout Standard
In step 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:Find-an-Euler"

\end_inset

 we obtained an Euler cycle, which we transform to a simple cycle which
 touches every vertex, just as we did in algorithm 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:m-tsp-2-approx-algo"

\end_inset

.
\end_layout

\begin_layout Subsubsection
Proof of 
\begin_inset Formula $1.5$
\end_inset

-approximation
\end_layout

\begin_layout Standard
We denote by 
\begin_inset Formula $C$
\end_inset

 the solution of algorithm 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:m-tsp-1.5-approx-algo"

\end_inset

 and by 
\begin_inset Formula $C^{\star}$
\end_inset

 the optimal solution.
\end_layout

\begin_layout Standard
We want to prove 
\begin_inset Formula $w\left(C\right)\leq1.5w\left(C^{\star}\right)$
\end_inset

.
\end_layout

\begin_layout Standard
Obviously 
\begin_inset Formula $w\left(C\right)\leq w\left(T\right)+w\left(M^{*}\right)$
\end_inset

.
\end_layout

\begin_layout Standard
So we will devide the proof into two parts.
\end_layout

\begin_layout Standard
First we will show 
\begin_inset Formula $w\left(T\right)\leq w\left(C^{\star}\right)$
\end_inset

, and then 
\begin_inset Formula $w\left(M^{*}\right)\leq0.5w\left(C^{\star}\right)$
\end_inset

.
\end_layout

\begin_layout Standard
From claim 
\begin_inset CommandInset ref
LatexCommand ref
reference "Let-tmst-be"

\end_inset

 we conclude 
\begin_inset Formula $w\left(T\right)\leq w\left(C^{\star}\right)$
\end_inset

.
\end_layout

\begin_layout Standard
Let's denote with 
\begin_inset Formula $C_{A}^{\star}$
\end_inset

 the optimal solution for the problem on 
\begin_inset Formula $G_{A}$
\end_inset

.
 By the triangle inequality, we can deduce that an optimal solution which
 touches only part of the vertices, is better (has less weight) than an
 optimal solution that touches all of the vertices.
 Thus we conclude 
\begin_inset Formula $w\left(C_{A}^{\star}\right)\leq w\left(C^{\star}\right)$
\end_inset

.
\end_layout

\begin_layout Standard
The set 
\begin_inset Formula $A$
\end_inset

 contains an even number of vertices, and 
\begin_inset Formula $C_{A}^{\star}$
\end_inset

 is a cycle which touches all these vertices.
 This means that in 
\begin_inset Formula $C_{A}^{\star}$
\end_inset

 there are two perfect mathces (alternating edges of the cycle).
 We denote them 
\begin_inset Formula $M_{A}^{1}$
\end_inset

 and 
\begin_inset Formula $M_{A}^{2}$
\end_inset

, and assume, WLOG, 
\begin_inset Formula $M_{A}^{1}$
\end_inset

 has the smaller weight (
\begin_inset Formula $w\left(M_{A}^{1}\right)\leq w\left(M_{A}^{2}\right)$
\end_inset

).
 Both 
\begin_inset Formula $M_{A}^{1}$
\end_inset

 and 
\begin_inset Formula $M_{A}^{2}$
\end_inset

 are also perfect matches in 
\begin_inset Formula $G_{A}$
\end_inset

, and 
\begin_inset Formula $M^{*}$
\end_inset

 is defnied to be the 
\series bold
minimal 
\series default
perfect matching 
\begin_inset Formula $M^{*}$
\end_inset

 in 
\begin_inset Formula $G_{A}$
\end_inset

, thus 
\begin_inset Formula $w\left(M^{*}\right)\leq w\left(M_{A}^{1}\right)$
\end_inset

.
\end_layout

\begin_layout Standard
Also, from the definition of 
\begin_inset Formula $M_{A}^{1}$
\end_inset

 and 
\begin_inset Formula $M_{A}^{2}$
\end_inset

: 
\begin_inset Formula $w\left(C_{A}^{\star}\right)=w\left(M_{A}^{1}\right)+w\left(M_{A}^{2}\right)$
\end_inset

, and from the minimality of 
\begin_inset Formula $M_{A}^{1}$
\end_inset

: 
\begin_inset Formula $w\left(M_{A}^{1}\right)\leq\frac{1}{2}w\left(C_{A}^{\star}\right)$
\end_inset

.
\end_layout

\begin_layout Standard
From this we conclude 
\begin_inset Formula $w\left(M^{*}\right)\leq w\left(M_{A}^{1}\right)\leq\frac{1}{2}w\left(C_{A}^{\star}\right)\leq\frac{1}{2}w\left(C^{\star}\right)$
\end_inset

.
\end_layout

\begin_layout Standard
Finally we have 
\begin_inset Formula $w\left(C\right)\leq w\left(T\right)+w\left(M^{*}\right)\leq w\left(C^{\star}\right)+\frac{1}{2}w\left(C^{\star}\right)=1.5w\left(C^{\star}\right)$
\end_inset

, as needed to complete the proof.
 
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\begin_layout Subsection
3-SAT (Satisfiability)
\begin_inset CommandInset label
LatexCommand label
name "sub:3-SAT-(Satisfiability)-2approximating"

\end_inset


\end_layout

\begin_layout Standard
Before we define the problem, some definitions and denotations:
\end_layout

\begin_layout Itemize
Boolean variable: 
\begin_inset Formula $x\in\left\{ \mathbb{T},\mathbb{F}\right\} $
\end_inset

.
\end_layout

\begin_layout Itemize
Literal: either a variable 
\begin_inset Formula $x$
\end_inset

 or it's negation 
\begin_inset Formula $\neg x$
\end_inset

.
\end_layout

\begin_layout Itemize
Clause: A disjunction of literals (such as 
\begin_inset Formula $x_{1}\vee\neg x_{2}\vee x_{3}$
\end_inset

).
\end_layout

\begin_layout Itemize
Formula: A conjunction of clauses (such as 
\begin_inset Formula $\left(x_{1}\vee\neg x_{2}\vee x_{3}\vee x_{4}\right)\wedge\left(\neg x_{1}\vee x_{4}\vee x_{5}\right)$
\end_inset

).
 Such a formula is said to be in 
\emph on
conjunctive normal form
\emph default
 (CNF).
\end_layout

\begin_layout Itemize
A 
\emph on
k-CNF 
\emph default
formula is a CNF formula in which each clause contains k literals.
\end_layout

\begin_layout Standard
In this problem, our input is a 3-CNF formula with 
\begin_inset Formula $m$
\end_inset

 clauses.
 Our goal is to find an assignment for the variables in the formula such
 that the most clauses are satisfied (i.e.
 evaluated valuated as 
\begin_inset Formula $\mathbb{T}$
\end_inset

).
\end_layout

\begin_layout Standard
Let 
\begin_inset Formula $X$
\end_inset

 be an assignment of the variables, we denote 
\begin_inset Formula $q\left(X\right)$
\end_inset

 as the number of satisfied clauses.
\end_layout

\begin_layout Standard
Assumptions:
\end_layout

\begin_layout Enumerate
No clause contains the same literal more than once.
\end_layout

\begin_layout Enumerate
No clause contains a variable and it's negation.
\end_layout

\begin_layout Subsubsection
\begin_inset Formula $2$
\end_inset

-approximating algorithm
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
wide false
sideways false
status open

\begin_layout Enumerate
Denote the assignment in which all variables are assigned 
\begin_inset Formula $\mathbb{T}$
\end_inset

 with 
\begin_inset Formula $X_{\mathbb{T}}$
\end_inset

.
\end_layout

\begin_layout Enumerate
Denote the assignment in which all variables are assigned 
\begin_inset Formula $\mathbb{F}$
\end_inset

 with 
\begin_inset Formula $X_{\mathbb{F}}$
\end_inset

.
\end_layout

\begin_layout Enumerate
If 
\begin_inset Formula $q\left(X_{\mathbb{T}}\right)>q\left(X_{\mathbb{F}}\right)$
\end_inset

, return 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $X_{\mathbb{T}}$
\end_inset

.
\end_layout

\begin_layout Enumerate
Else, return 
\begin_inset Formula $X_{\mathbb{F}}$
\end_inset

.
\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
3-SAT 
\begin_inset Formula $2$
\end_inset

-approximating algorithm
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection
Proof of 
\begin_inset Formula $2$
\end_inset

-approximation
\end_layout

\begin_layout Standard
Denote with 
\begin_inset Formula $m$
\end_inset

 the number of clauses.
 Let 
\begin_inset Formula $S$
\end_inset

 be the solution of the algorithm and 
\begin_inset Formula $S^{\star}$
\end_inset

 the optimal solution.
\end_layout

\begin_layout Standard
If 
\begin_inset Formula $X_{\mathbb{T}}$
\end_inset

 (as defined in the algorithm) does not satisfy a clause 
\begin_inset Formula $C_{i}$
\end_inset

, then it must be satisfied by 
\begin_inset Formula $X_{\mathbb{F}}$
\end_inset

 (because a clause is a disjunction of literals).
 Thus 
\begin_inset Formula $q\left(X_{\mathbb{T}}\right)+q\left(X_{\mathbb{F}}\right)=m$
\end_inset

.
\end_layout

\begin_layout Standard
We also know that the optimal solution cannot satisfy more than 
\begin_inset Formula $m$
\end_inset

 clauses, so 
\begin_inset Formula $q\left(S^{\star}\right)\leq m$
\end_inset

.
\end_layout

\begin_layout Standard
Also, we know that 
\begin_inset Formula $S=\max\left\{ X_{\mathbb{T}},X_{\mathbb{F}}\right\} $
\end_inset

, so 
\begin_inset Formula $q\left(S\right)\geq\frac{1}{2}m$
\end_inset

.
\end_layout

\begin_layout Standard
Finally we have 
\begin_inset Formula $q\left(S\right)\geq\frac{1}{2}m\geq\frac{1}{2}q\left(S^{\star}\right)$
\end_inset

, thus completing the proof.
 
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\begin_layout Chapter
Probabilistic Algorithms
\begin_inset Index idx
status open

\begin_layout Plain Layout
Probabilistic Algorithm
\end_layout

\end_inset


\end_layout

\begin_layout Section
Examples
\end_layout

\begin_layout Subsection
Max-Lin-2
\end_layout

\begin_layout Standard
This is a problem of solving a linear system of equations over a finite
 field of two elements
\begin_inset Foot
status collapsed

\begin_layout Plain Layout
\begin_inset Formula $F_{2}=\left\{ 0,1\right\} $
\end_inset

 is a finite field (also called 
\emph on
Galois field
\emph default
), in which the results of arithmetic operations are taken modulus 2.
 For example: 
\begin_inset Formula $1+1=0$
\end_inset

.
\end_layout

\end_inset

 (
\begin_inset Formula $F_{2}=\left\{ 0,1\right\} $
\end_inset

).
\end_layout

\begin_layout Standard
The input is a system of 
\begin_inset Formula $m$
\end_inset

 equations with 
\begin_inset Formula $n$
\end_inset

 variables over the field 
\begin_inset Formula $F_{2}$
\end_inset

.
\end_layout

\begin_layout Standard
Our goal is to find an assignment for the 
\begin_inset Formula $n$
\end_inset

 variables, such that as much of the equations are satisfied.
\end_layout

\begin_layout Standard
In other words, if we our solution is 
\begin_inset Formula $S$
\end_inset

 and we define 
\begin_inset Formula $q\left(S\right)=number\, of\, satisfied\, equations$
\end_inset

, then we would like to maximze 
\begin_inset Formula $q\left(S\right)$
\end_inset

.
\end_layout

\begin_layout Standard
Notice that if there is an assignment which satisfies 
\series bold
all
\series default
 the equations, then we already know how to find it by employing one of
 the methods of solving a linear system of equations.
 But the more interesting problem in our case, is when not all equations
 can be satisfied by any assignment.
 In which case we would like to find the assignment which maximizes the
 number of satisfied equations.
\end_layout

\begin_layout Example
The system of equations 
\begin_inset Formula $\left(\begin{array}{ccc}
1 & 1 & 1\\
0 & 1 & 1\\
0 & 0 & 1
\end{array}\right)\left(\begin{array}{c}
x_{1}\\
x_{2}\\
x_{3}
\end{array}\right)=\left(\begin{array}{c}
1\\
0\\
1
\end{array}\right)$
\end_inset

 is solved with 
\begin_inset Formula $\left(\begin{array}{c}
x_{1}\\
x_{2}\\
x_{3}
\end{array}\right)=\left(\begin{array}{c}
1\\
1\\
1
\end{array}\right)$
\end_inset

.
\end_layout

\begin_layout --Separator--

\end_layout

\begin_layout Example
The system of equations 
\begin_inset Formula $\left(\begin{array}{ccc}
1 & 1 & 1\\
0 & 1 & 1\\
0 & 0 & 1\\
0 & 1 & 0
\end{array}\right)\left(\begin{array}{c}
x_{1}\\
x_{2}\\
x_{3}
\end{array}\right)=\left(\begin{array}{c}
1\\
0\\
1\\
1
\end{array}\right)$
\end_inset

 is solved with 
\begin_inset Formula $\left(\begin{array}{c}
x_{1}\\
x_{2}\\
x_{3}
\end{array}\right)=\left(\begin{array}{c}
1\\
1\\
1
\end{array}\right)$
\end_inset

.
 Notice that in this case we have more equations than variables.
\end_layout

\begin_layout --Separator--

\end_layout

\begin_layout Example
The system of equations 
\begin_inset Formula $\left(\begin{array}{ccc}
1 & 1 & 1\\
0 & 1 & 1\\
0 & 0 & 1\\
0 & 1 & 0
\end{array}\right)\left(\begin{array}{c}
x_{1}\\
x_{2}\\
x_{3}
\end{array}\right)=\left(\begin{array}{c}
1\\
0\\
1\\
0
\end{array}\right)$
\end_inset

 
\series bold
cannot
\series default
 be solved.
 However, 
\begin_inset Formula $\left(\begin{array}{c}
x_{1}\\
x_{2}\\
x_{3}
\end{array}\right)=\left(\begin{array}{c}
1\\
1\\
1
\end{array}\right)$
\end_inset

 satisfies the top 3 equations, and only the fourth equation is not satisfied.
\end_layout

\begin_layout Subsubsection
\begin_inset Formula $2$
\end_inset

-approximating probabilistic algorithm
\end_layout

\begin_layout Standard
We will now show an algorithm which yields a 
\begin_inset Formula $2$
\end_inset

-approximating for the expectancy of the solutions.
 In other word, if the best solution, 
\begin_inset Formula $S^{\star}$
\end_inset

, satisfies 
\begin_inset Formula $q\left(S^{\star}\right)$
\end_inset

 equations, then this algorithm finds an assignment, 
\begin_inset Formula $S$
\end_inset

, such that if we consider the expactency of these assignments, at least
 
\begin_inset Formula $\frac{1}{2}q\left(S^{\star}\right)$
\end_inset

 equations are satisfied (
\begin_inset Formula $\mathbb{E}\left[S\right]\geq\frac{1}{2}q\left(S^{\star}\right)$
\end_inset

).
\end_layout

\begin_layout Standard
We denote the 
\begin_inset Formula $n$
\end_inset

 variables with 
\begin_inset Formula $x_{1},x_{2},...,x_{n}$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
wide false
sideways false
status open

\begin_layout Enumerate
For 
\begin_inset Formula $i=1,...,n$
\end_inset

:
\end_layout

\begin_deeper
\begin_layout Enumerate
Assign 
\begin_inset Formula $x_{i}=0$
\end_inset

 or 
\begin_inset Formula $x_{i}=1$
\end_inset

 with probability of 
\begin_inset Formula $0.5$
\end_inset

 (toss a coin).
\end_layout

\end_deeper
\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Max-Lin-2 
\begin_inset Formula $2$
\end_inset

-expectancy-approximation probabilistic algorithm
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection
Proof of 
\begin_inset Formula $2$
\end_inset

-approximation of the expectancy
\end_layout

\begin_layout Standard
Notice that 
\begin_inset Formula $q\left(S^{\star}\right)\leq m$
\end_inset

, so it's enough to show 
\begin_inset Formula $\mathbb{E}\left[S\right]\geq\frac{m}{2}$
\end_inset

.
\end_layout

\begin_layout Standard
We define the following probability space:
\end_layout

\begin_layout Standard
\begin_inset Formula $\Omega=\left\{ \omega=\left\{ \omega_{1},\omega_{2},...,\omega_{n}\right\} :\omega_{i}\in\left\{ 0,1\right\} \right\} $
\end_inset


\end_layout

\begin_layout Standard
Each 
\begin_inset Formula $\omega\in\Omega$
\end_inset

 is an assignment for 
\begin_inset Formula $x_{1},x_{2},...,x_{n}$
\end_inset

.
\end_layout

\begin_layout Standard
We define the probability function 
\begin_inset Formula $P\left(\omega\right)=\frac{1}{2^{n}}$
\end_inset

 (because in each 
\begin_inset Formula $\omega$
\end_inset

 we have 
\begin_inset Formula $n$
\end_inset

 elements with probability 
\begin_inset Formula $\frac{1}{2}$
\end_inset

).
\end_layout

\begin_layout Standard
We also define a random variable 
\begin_inset Formula $X\left(w\right)$
\end_inset

 as the number of equations 
\begin_inset Formula $\omega$
\end_inset

 satisfies (
\begin_inset Formula $X\left(\omega\right)=\left|\left\{ i:\left(A\omega\right)_{i}=b_{i}\right\} \right|$
\end_inset

).
\end_layout

\begin_layout Standard
The expectancy of 
\begin_inset Formula $X$
\end_inset

 is the average number of equations satisfied by a random assignment.
\end_layout

\begin_layout Standard
We will show that 
\begin_inset Formula $\mathbb{E}\left[X\right]=\frac{m}{2}$
\end_inset

.
\end_layout

\begin_layout Standard
Let's define 
\begin_inset Formula $m$
\end_inset

 new random variables 
\begin_inset Formula $X_{1}\left(\omega\right),X_{2}\left(\omega\right),...,X_{m}\left(\omega\right)$
\end_inset

, where 
\begin_inset Formula $X_{i}\left(\omega\right)$
\end_inset

 indicates if equation 
\begin_inset Formula $i$
\end_inset

 is satisfied: 
\begin_inset Formula $X_{i}\left(\omega\right)=\begin{cases}
1 & \left(A\omega\right)_{i}=b_{i}\\
0 & \left(A\omega\right)_{i}\neq b_{i}
\end{cases}$
\end_inset

.
\end_layout

\begin_layout Standard
By this definition, we have 
\begin_inset Formula $X\left(w\right)=\sum_{i=1}^{m}X_{i}\left(\omega\right)$
\end_inset

, and by the linearity of the expectation 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $\mathbb{E}\left[X\right]=\sum_{i=1}^{m}\mathbb{E}\left[X_{i}\right]$
\end_inset

.
\end_layout

\begin_layout Standard
We will now see that 
\begin_inset Formula $\forall i=1,...,m:\mathbb{E}\left[X_{i}\right]=\frac{1}{2}$
\end_inset

, and thus 
\begin_inset Formula $\mathbb{E}\left[X\right]=\frac{m}{2}$
\end_inset

.
\end_layout

\begin_layout Standard

\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none
\begin_inset Formula $\mathbb{E}\left[X_{i}\right]=\sum_{\omega\in\Omega}P\left(\omega\right)\cdot X_{i}\left(\omega\right)=\sum_{\omega\in\Omega:X_{i}\left(\omega\right)=1}P\left(\omega\right)=\frac{1}{2^{n}}\underset{*}{\underbrace{\left(\sum_{\omega\in\Omega:X_{i}\left(\omega\right)=1}1\right)}}$
\end_inset

.
\end_layout

\begin_layout Standard
The expression marked with 
\begin_inset Formula $*$
\end_inset

 is the number of assignments which can satisfy equation 
\begin_inset Formula $i$
\end_inset

.
 From linear algebra we know that a linear equation of 
\begin_inset Formula $n$
\end_inset

 variables has 
\begin_inset Formula $2^{n-1}$
\end_inset

 legal assignments (over the field 
\begin_inset Formula $F_{2}$
\end_inset

)
\begin_inset Foot
status collapsed

\begin_layout Plain Layout
Consider an equation of the form 
\begin_inset Formula $a_{1}x_{1}+a_{2}x_{2}+...+a_{n}x_{n}=b$
\end_inset

.
 In 
\begin_inset Formula $F_{2}$
\end_inset

 each 
\begin_inset Formula $x_{i}\in\left\{ 0,1\right\} $
\end_inset

.
 We can set 
\begin_inset Formula $n-1$
\end_inset

 variables with either 
\begin_inset Formula $1$
\end_inset

 or 
\begin_inset Formula $0$
\end_inset

, by which the 
\begin_inset Formula $n$
\end_inset

'th variable is determined.
 This gives 
\begin_inset Formula $2^{n-1}$
\end_inset

 combinations.
\end_layout

\end_inset

.
\end_layout

\begin_layout Standard
So finally we have 
\begin_inset Formula $\mathbb{E}\left[X_{i}\right]=\frac{2^{n-1}}{2^{n}}=\frac{1}{2}$
\end_inset

, thus copmleting the proof.
 
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\begin_layout Subsubsection
Further discussion
\end_layout

\begin_layout Paragraph
Probability of a random assignment
\begin_inset CommandInset label
LatexCommand label
name "sub:Probability-of-an-assignment"

\end_inset


\end_layout

\begin_layout Standard
We can also determine the probability in which a certain amount of equations
 are satisfied by an assignment 
\begin_inset Formula $\omega$
\end_inset

.
\end_layout

\begin_layout Standard
For example, let's show 
\begin_inset Formula $P\left(\omega:X\left(\omega\right)\geq0.4m\right)\geq\frac{1}{6}$
\end_inset

, or in words - we will show that the probability that an assignment 
\begin_inset Formula $\omega$
\end_inset

 satisfies at least 40% of the equations is larger than 
\begin_inset Formula $\frac{1}{6}$
\end_inset

.
\end_layout

\begin_layout Standard
Let's detone with 
\begin_inset Formula $B$
\end_inset

 the event 
\begin_inset Formula $B=\mbox{\left\{  \omega:X\left(\omega\right)\geq0.4m\right\}  }$
\end_inset

.
 We want to prove 
\begin_inset Formula $P\left(B\right)\geq\frac{1}{6}$
\end_inset

.
 We will prove by negation.
\end_layout

\begin_layout Standard
Suppose 
\begin_inset Formula $P\left(B\right)<\frac{1}{6}$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Formula $\mathbb{E}\left[X\right]=\sum_{\omega\in\Omega}P\left(\omega\right)\cdot X\left(\omega\right)=\sum_{\omega\in B}P\left(\omega\right)\cdot X\left(\omega\right)+\sum_{\omega\notin B}P\left(\omega\right)\cdot X\left(\omega\right)$
\end_inset


\end_layout

\begin_layout Standard
Any assignment cannot satisfy more than 
\begin_inset Formula $m$
\end_inset

 equations (obviously, since there are only 
\begin_inset Formula $m$
\end_inset

 equations), so 
\begin_inset Formula $\sum_{\omega\in B}P\left(\omega\right)\cdot X\left(\omega\right)\leq\sum_{\omega\in B}P\left(\omega\right)\cdot m$
\end_inset

.
\end_layout

\begin_layout Standard
Also, by the definition of 
\begin_inset Formula $B$
\end_inset

: 
\begin_inset Formula $\sum_{\omega\notin B}P\left(\omega\right)\cdot X\left(\omega\right)<\sum_{\omega\notin B}P\left(\omega\right)\cdot0.4m$
\end_inset

.
\end_layout

\begin_layout Standard
So now we have 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $\mathbb{E}\left[X\right]<\sum_{\omega\in B}P\left(\omega\right)\cdot m+\sum_{\omega\notin B}P\left(\omega\right)\cdot0.4m=mP\left(B\right)+0.4mP\left(B^{c}\right)$
\end_inset

, where 
\begin_inset Formula $B^{c}$
\end_inset

 is the complementary event of 
\begin_inset Formula $B$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Formula $P\left(B^{c}\right)=1-P\left(B\right)$
\end_inset

, so 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $\mathbb{E}\left[X\right]<mP\left(B\right)+0.4m\left(1-P\left(B\right)\right)=0.6mP\left(B\right)+0.4m$
\end_inset

.
\end_layout

\begin_layout Standard
But we assumed 
\begin_inset Formula $P\left(B\right)<\frac{1}{6}$
\end_inset

, thus 
\begin_inset Formula $\mathbb{E}\left[X\right]<\frac{1}{6}0.6m+0.4m=0.5m$
\end_inset

.
\end_layout

\begin_layout Standard
Finally we have 
\begin_inset Formula $\mathbb{E}\left[X\right]<0.5m$
\end_inset

.
 But we have already shown 
\begin_inset Formula $\mathbb{E}\left[X\right]=0.5m$
\end_inset

, thus we have reached a contradiction, and we can conclude 
\begin_inset Formula $P\left(B\right)\geq\frac{1}{6}$
\end_inset

.
 
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\begin_layout Paragraph
An improved algorithm
\end_layout

\begin_layout Standard
By 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Probability-of-an-assignment"

\end_inset

 we can formulate an improved algorithm which yields, by very good probability
 (specifically 
\begin_inset Formula $1-\frac{1}{e^{100}}\approx99.999\%$
\end_inset

), an assignment which satisfies at least 40% of the equations.
\end_layout

\begin_layout Standard
Notice that 
\begin_inset Formula $\frac{1}{0.4}=2.5$
\end_inset

, so this is a high-probability 
\begin_inset Formula $2.5$
\end_inset

-approximating algorithm.
 As opposed to the previous algorithm, here we don't say anything about
 the expectancy of the solutions the algorithms yields, but we say a much
 stronger statement about a specific solution.
 Altough 
\begin_inset Formula $2.5$
\end_inset

-approximation is not as good as 
\begin_inset Formula $2$
\end_inset

-approximation (40% vs.
 50%), here we have, with high-probability, a specific solution which satisfies
 at least 40% of the equations.
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
wide false
sideways false
status open

\begin_layout Enumerate
Choose 600 random assignments 
\begin_inset Formula $\omega_{1},\omega_{2},...,\omega_{600}$
\end_inset

.
\end_layout

\begin_layout Enumerate
Return the assignment which satisfies the most equations.
\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Max-Lin-2 
\begin_inset Formula $2.5$
\end_inset

-approximation high-probability algorithm
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
By 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Probability-of-an-assignment"

\end_inset

 we know that assignment 
\begin_inset Formula $\omega_{i}$
\end_inset

 satisfies 40% of the equations with probability of 
\begin_inset Formula $\frac{1}{6}$
\end_inset

.
 The probability that all 600 chosen assignments will fail to do this is
 
\begin_inset Formula $\left(1-\frac{1}{6}\right)^{600}$
\end_inset

.
 By lemma 
\begin_inset CommandInset ref
LatexCommand ref
reference "lem:,-for-all-1+a^b<e^ab"

\end_inset

, we have 
\begin_inset Formula $\left(1-\frac{1}{6}\right)^{600}<e^{-100}$
\end_inset

.
\end_layout

\begin_layout Standard
So the probability that at least one assignment will satisfy 40% of the
 equations is at least 
\begin_inset Formula $1-\frac{1}{e^{100}}$
\end_inset

.
 
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\begin_layout Subsection
3-SAT (Satisfiability)
\end_layout

\begin_layout Standard
See the definition of the problem in 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:3-SAT-(Satisfiability)-2approximating"

\end_inset

.
\end_layout

\begin_layout Subsubsection
Probabilistic 
\begin_inset Formula $\frac{7}{8}$
\end_inset

-approximating algorithm
\end_layout

\begin_layout Standard
We show a probabilistic algorithm which gives a 
\begin_inset Formula $\frac{7}{8}$
\end_inset

-approximation with probability larger than 
\begin_inset Formula $1-\frac{1}{e^{k}}$
\end_inset

 (with 
\begin_inset Formula $k$
\end_inset

 as a parameter of the algorithm).
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
wide false
sideways false
status open

\begin_layout Enumerate
Randomly assign 
\begin_inset Formula $\mathbb{T}$
\end_inset

 or 
\begin_inset Formula $\mathbb{F}$
\end_inset

 to each variable 
\begin_inset Formula $x_{i}$
\end_inset

 (with probability 
\begin_inset Formula $0.5$
\end_inset

).
\end_layout

\begin_layout Enumerate
If 
\begin_inset Formula $q\left(X\right)\geq\frac{7}{8}m$
\end_inset

, finish and return 
\begin_inset Formula $X$
\end_inset

.
\end_layout

\begin_layout Enumerate
Repeat steps 1-2 at most 
\begin_inset Formula $k\left(m+1\right)$
\end_inset

 times.
\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
3-SAT probabilistic 
\begin_inset Formula $\frac{7}{8}$
\end_inset

-approximating algorithm
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection
Proof
\end_layout

\begin_layout Standard
We define 
\emph on
success
\emph default
 of the algorithm as the success in yielding a solution, 
\begin_inset Formula $X$
\end_inset

, which satisfies at least 
\begin_inset Formula $\frac{7}{8}m$
\end_inset

 clauses.
 In other words, we succeed only if 
\begin_inset Formula $q\left(X\right)\geq\frac{7}{8}m$
\end_inset

, otherwise we 
\emph on
fail
\emph default
.
\end_layout

\begin_layout Standard
We will prove in two parts.
 First we will show that the probability for success of steps 1-2 (which
 will be reffered to as the 
\emph on
basic 
\emph default
steps) is 
\begin_inset Formula $P\left(success\, basic\right)\geq\frac{1}{m+1}$
\end_inset

.
 Then we will show that the probability for success of the entire algorithm
 (all 3 steps) is 
\begin_inset Formula $P\left(success\right)\geq1-\frac{1}{e^{k}}$
\end_inset

.
\end_layout

\begin_layout Paragraph
Part 1:
\end_layout

\begin_layout Standard
We need to prove 
\begin_inset Formula $P\left(success\, basic\right)\geq\frac{1}{m+1}$
\end_inset

.
\end_layout

\begin_layout Standard
We define the probability space as all the tuples of 
\begin_inset Formula $\mathbb{T}$
\end_inset

 and 
\begin_inset Formula $\mathbb{F}$
\end_inset

 of size 
\begin_inset Formula $n$
\end_inset

: 
\begin_inset Formula $\Omega=\left\{ \mathbb{T},\mathbb{F}\right\} ^{n}$
\end_inset

.
\end_layout

\begin_layout Standard
Obviously there are 
\begin_inset Formula $2^{n}$
\end_inset

 such tuples, so for some 
\begin_inset Formula $\omega\in\Omega$
\end_inset

 we have 
\begin_inset Formula $P\left(\omega\right)=\frac{1}{2^{n}}$
\end_inset

.
\end_layout

\begin_layout Standard
We define two random variables:
\end_layout

\begin_layout Itemize
\begin_inset Formula $X\left(\omega\right)$
\end_inset

 - The amount of satisfied clauses by 
\begin_inset Formula $\omega$
\end_inset

.
 Thus 
\begin_inset Formula $P\left(success\, basic\right)=P\left(X\geq\frac{7}{8}m\right)$
\end_inset

.
\end_layout

\begin_layout Itemize
\begin_inset Formula $Y\left(\omega\right)$
\end_inset

 - The amount of unsatisfied clauses by 
\begin_inset Formula $\omega$
\end_inset

.
 Thus 
\begin_inset Formula $P\left(failure\, basic\right)=P\left(Y>\frac{1}{8}m\right)$
\end_inset

.
\end_layout

\begin_layout Standard
Instead of proving 
\begin_inset Formula $P\left(X\geq\frac{7}{8}m\right)\geq\frac{1}{m+1}$
\end_inset

, we can equivalently prove 
\begin_inset Formula $P\left(Y>\frac{1}{8}m\right)<1-\frac{1}{m+1}=\frac{m}{m+1}=\frac{1}{1+\frac{1}{m}}$
\end_inset

.
\end_layout

\begin_layout Standard
We define 
\begin_inset Formula $m$
\end_inset

 new random variables:
\end_layout

\begin_layout Standard
\begin_inset Formula $\forall i=1...m:Y_{i}\left(\omega\right)=\begin{cases}
1 & clause\, i\, is\, unsatisfied\, by\,\omega\\
0 & clause\, i\, is\, satisfied\, by\,\omega
\end{cases}$
\end_inset

.
\end_layout

\begin_layout Standard
Obviously 
\begin_inset Formula $Y\left(\omega\right)=\sum_{i=1}^{m}Y_{i}\left(\omega\right)$
\end_inset

, so by the linearity of the expectation 
\begin_inset Formula $\mathbb{E}\left[Y\right]=\sum_{i=1}^{m}\mathbb{E}\left[Y_{i}\right]$
\end_inset

.
\end_layout

\begin_layout Standard

\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none
\begin_inset Formula $\mathbb{E}\left[Y_{i}\right]=P\left(Y_{i}=1\right)\cdot1+P\left(Y_{i}=1\right)\cdot0=P\left(Y_{i}=1\right)$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $Y_{i}=1$
\end_inset

 means that clause 
\begin_inset Formula $i$
\end_inset

 is unsatisfied.
 In 3-SAT, each clause contains 3 literals, each of them can evaluate to
 
\begin_inset Formula $\mathbb{T}$
\end_inset

 or 
\begin_inset Formula $\mathbb{F}$
\end_inset

 by the assignment.
 Thus the probability for a clause to be unsatisfied (all literals get 
\begin_inset Formula $\mathbb{F}$
\end_inset

) is 
\begin_inset Formula $\frac{1}{2}\cdot\frac{1}{2}\cdot\frac{1}{2}=\frac{1}{8}$
\end_inset

.
 Thus 
\begin_inset Formula $\mathbb{E}\left[Y_{i}\right]=P\left(Y_{i}=1\right)=\frac{1}{8}$
\end_inset

.
\end_layout

\begin_layout Standard
And now 
\begin_inset Formula $\mathbb{E}\left[Y\right]=\sum_{i=1}^{m}\mathbb{E}\left[Y_{i}\right]=\frac{m}{8}$
\end_inset

.
\end_layout

\begin_layout Standard
We now recall Markov's inequality:
\end_layout

\begin_layout Standard
For a non-negative random variable, 
\begin_inset Formula $Z$
\end_inset

, and some constant 
\begin_inset Formula $c>1$
\end_inset

: 
\begin_inset Formula $P\left(Z\geq c\cdot\mathbb{E}\left[Z\right]\right)\leq\frac{1}{c}$
\end_inset

.
\end_layout

\begin_layout Standard
We use it on 
\begin_inset Formula $Y$
\end_inset

 with 
\begin_inset Formula $c=1+\frac{1}{m}$
\end_inset

: 
\begin_inset Formula $P\left(Y\geq\left(1+\frac{1}{m}\right)\cdot\frac{m}{8}\right)\leq\frac{1}{1+\frac{1}{m}}$
\end_inset

.
\end_layout

\begin_layout Standard
Both 
\begin_inset Formula $Y$
\end_inset

 and 
\begin_inset Formula $m$
\end_inset

 are integers, so 
\begin_inset Formula $P\left(Y\geq\left(1+\frac{1}{m}\right)\cdot\frac{m}{8}\right)=P\left(Y\geq\frac{m}{8}+\frac{1}{8}\right)=P\left(Y>\frac{m}{8}\right)$
\end_inset

.
\end_layout

\begin_layout Standard
And finally we have 
\begin_inset Formula $P\left(failure\, basic\right)=P\left(Y>\frac{m}{8}\right)\leq\frac{1}{1+\frac{1}{m}}$
\end_inset

, as needed for this part of the proof.
 
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\begin_layout Paragraph
Part 2:
\end_layout

\begin_layout Standard
We need to prove 
\begin_inset Formula $P\left(success\right)\geq1-\frac{1}{e^{k}}$
\end_inset

.
\end_layout

\begin_layout Standard
Equivalently we can also prove 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $P\left(failure\right)<\frac{1}{e^{k}}$
\end_inset

.
\end_layout

\begin_layout Standard
Failure in the entire algorithm is failure in all 
\begin_inset Formula $k\left(m+1\right)$
\end_inset

 attempts.
\end_layout

\begin_layout Standard
\begin_inset Formula $P\left(failure\right)=\prod_{i=1}^{k\left(m+1\right)}P\left(failure\, in\, the\, i'th\, attempt\right)$
\end_inset

.
\end_layout

\begin_layout Standard
In part 1 we already proved the failure in one attempt is 
\begin_inset Formula $P\left(failure\, basic\right)\leq\frac{1}{1+\frac{1}{m}}=1-\frac{1}{m+1}$
\end_inset

, thus:
\end_layout

\begin_layout Standard
\begin_inset Formula $P\left(failure\right)\leq\prod_{i=1}^{k\left(m+1\right)}\left(1-\frac{1}{m+1}\right)=\left(1-\frac{1}{m+1}\right)^{k\left(m+1\right)}=\left(\left(1-\frac{1}{m+1}\right)^{\left(m+1\right)}\right)^{k}<\left(\frac{1}{e}\right)^{k}=\frac{1}{e^{k}}$
\end_inset

, thus completing the proof.
 
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\begin_layout Standard

\end_layout

\begin_layout Chapter
Flow Networks
\begin_inset Index idx
status open

\begin_layout Plain Layout
Flow Network
\end_layout

\end_inset


\end_layout

\begin_layout Section
Definitions and properties
\end_layout

\begin_layout Definition
Flow network.
\end_layout

\begin_layout Definition
A flow network is a tuple of 5 elements 
\begin_inset Formula $\left(V,E,C,s,t\right)$
\end_inset

:
\end_layout

\begin_layout Itemize
\begin_inset Formula $G=\left(V,E\right)$
\end_inset

 - a 
\series bold
directed
\series default
 graph with vertices 
\begin_inset Formula $V$
\end_inset

 and edges 
\begin_inset Formula $E$
\end_inset

.
\end_layout

\begin_layout Itemize
\begin_inset Formula $C:E\rightarrow\mathbb{R}^{+}$
\end_inset

 - a capacity function on the edges of the network.
\end_layout

\begin_layout Itemize
\begin_inset Formula $s\in V$
\end_inset

 - the source vertex.
\end_layout

\begin_layout Itemize
\begin_inset Formula $t\in V$
\end_inset

 - the terminal vertex.
\end_layout

\begin_layout Definition
Flow.
\end_layout

\begin_layout Definition
A flow in a flow network is a function 
\begin_inset Formula $f:E\rightarrow\mathbb{R}^{+}$
\end_inset

 which maintains:
\end_layout

\begin_layout Enumerate
The flow in an edge cannot exceed the capacity of the edge: 
\begin_inset Formula $\forall e\in E:f\left(e\right)\leq C\left(e\right)$
\end_inset

.
\end_layout

\begin_layout Enumerate
Mass preservation for all inner vertices:
\begin_inset Newline newline
\end_inset


\begin_inset Formula $\forall v\in V\backslash\left\{ s,t\right\} :\underset{incoming\, flow\, into\, v}{\underbrace{\sum_{u\in V:\left(u,v\right)\in E}f\left(u,v\right)}}=\underset{outgoing\, flow\, from\, v}{\underbrace{\sum_{u\in V:\left(v,u\right)\in E}f\left(v,u\right)}}$
\end_inset

.
\end_layout

\begin_layout Definition
Flux.
\end_layout

\begin_layout Definition
The flux of a flow is the net flow coming out of the source 
\begin_inset Formula $s$
\end_inset

:
\end_layout

\begin_layout Definition
\begin_inset Formula $\left|f\right|=\underset{outgoing\, flow\, from\, s}{\underbrace{\sum_{u\in V:\left(s,u\right)\in E}f\left(s,u\right)}}-\underset{incoming\, flow\, into\, s}{\underbrace{\sum_{u\in V:\left(u,s\right)\in E}f\left(u,s\right)}}$
\end_inset

.
\end_layout

\begin_layout --Separator--

\end_layout

\begin_layout Definition
Rational flow.
\end_layout

\begin_layout Definition
\begin_inset Formula $f$
\end_inset

 is a rational flow if there are no two vertices 
\begin_inset Formula $u,v\in V$
\end_inset

 such that both 
\begin_inset Formula $f\left(u,v\right)>0$
\end_inset

 and 
\begin_inset Formula $f\left(v,u\right)>0$
\end_inset

.
\end_layout

\begin_layout --Separator--

\end_layout

\begin_layout Definition
Optimal flow.
\end_layout

\begin_layout Standard
Usually when working with flow networks, the goal is to find the maximal
 flux legal flow in the network.
 If 
\begin_inset Formula $f$
\end_inset

 has the maximal flux in the network, it is said to be optimal.
\end_layout

\begin_layout Lemma
For every network there is an optimal flow which is also rational.
\end_layout

\begin_layout Proof
Let 
\begin_inset Formula $f$
\end_inset

 be an optimal flow in the network with a minimal number of pairs 
\begin_inset Formula $u,v\in V$
\end_inset

 such that both 
\begin_inset Formula $f\left(u,v\right)>0$
\end_inset

 and 
\begin_inset Formula $f\left(v,u\right)>0$
\end_inset

.
 We will show that the number of these pairs is 0, and so 
\begin_inset Formula $f$
\end_inset

 is rational.
\end_layout

\begin_layout Proof
We prove by negation.
\end_layout

\begin_layout Proof
Let's assume that there is a pair 
\begin_inset Formula $u,v\in V$
\end_inset

 such that both 
\begin_inset Formula $f\left(u,v\right)>0$
\end_inset

 and 
\begin_inset Formula $f\left(v,u\right)>0$
\end_inset

.
 We will build a new flow, 
\begin_inset Formula $g$
\end_inset

, and will show that it is also optimal, and has less 
\begin_inset Quotes eld
\end_inset

bad
\begin_inset Quotes erd
\end_inset

 pairs than in 
\begin_inset Formula $f$
\end_inset

, thus reaching a contradiction (because we assumed 
\begin_inset Formula $f$
\end_inset

 is the optimal flow with minimal number of 
\begin_inset Quotes eld
\end_inset

bad
\begin_inset Quotes erd
\end_inset

 pairs).
\end_layout

\begin_layout Proof
We assume, WLOG, that 
\begin_inset Formula $f\left(u,v\right)>f\left(v,u\right)$
\end_inset

.
\end_layout

\begin_layout Proof
\begin_inset Formula $g\left(e=\left(w,z\right)\right)=\begin{cases}
f\left(e\right) & \left\{ w,z\right\} \neq\left\{ u,v\right\} \\
f\left(u,v\right)-f\left(v,u\right) & w=u,z=v\\
f\left(v,u\right)-f\left(v,u\right)=0 & w=v,z=u
\end{cases}$
\end_inset


\end_layout

\begin_layout Proof
We now need to show that 
\begin_inset Formula $g$
\end_inset

 is legal, optimal and has less 
\begin_inset Quotes eld
\end_inset

bad
\begin_inset Quotes erd
\end_inset

 pairs than 
\begin_inset Formula $f$
\end_inset

.
\end_layout

\begin_layout Proof
First we notice 
\begin_inset Formula $\forall e\in E:g\left(e\right)\leq f\left(e\right)\leq C\left(e\right)$
\end_inset

.
\end_layout

\begin_layout Proof
Now we check mass preservation on 
\begin_inset Formula $g$
\end_inset

.
 The only vertices that were changed are 
\begin_inset Formula $u,v$
\end_inset

.
 For both 
\begin_inset Formula $u,v$
\end_inset

 we decreased the incoming and outgoing flow by the same amount (
\begin_inset Formula $f\left(v,u\right)$
\end_inset

), thus mass is still preserved.
 So 
\begin_inset Formula $g$
\end_inset

 is legal.
\end_layout

\begin_layout Proof
Now we check 
\begin_inset Formula $g$
\end_inset

 is optimal.
\end_layout

\begin_layout Proof
\begin_inset Formula $\left|g\right|=$
\end_inset


\end_layout

\begin_layout Proof
TODO
\end_layout

\begin_layout Standard

\series bold
From now on, when we talk about flows, we will mean rational flows.
\end_layout

\begin_layout Standard
We would like to work with flow networks that are on complete graphs.
 So for every given flow network, we can define an 
\emph on
extended
\emph default
 flow network, which is completely equivalent.
\end_layout

\begin_layout Definition
Expanded capacity.
\end_layout

\begin_layout Definition
We define a capacity on the complete graph (for 
\series bold
every
\series default
 two vertices in 
\begin_inset Formula $V$
\end_inset

):
\end_layout

\begin_layout Definition
\begin_inset Formula $C^{'}\left(u,v\right)=\begin{cases}
C\left(u,v\right) & \left(u,v\right)\in E\\
0 & \left(u,v\right)\notin E
\end{cases}$
\end_inset

.
\end_layout

\begin_layout --Separator--

\end_layout

\begin_layout Definition
Expanded flow.
\end_layout

\begin_layout Definition
We define a flow on the complete graph (for 
\series bold
every
\series default
 two vertices in 
\begin_inset Formula $V$
\end_inset

):
\end_layout

\begin_layout Definition
\begin_inset Formula $f^{'}\left(u,v\right)=\begin{cases}
f\left(u,v\right) & f\left(u,v\right)>0\\
-f\left(u,v\right) & f\left(v,u\right)>0\\
0 & otherwise
\end{cases}$
\end_inset

.
\end_layout

\begin_layout Definition
Notice that a normal flow (as defined before) is always non-negative, but
 an exapnded flow can be negative 
\begin_inset Formula $\left(f^{'}:V\times V\rightarrow\mathbb{R}\right)$
\end_inset

.
\end_layout

\begin_layout Definition
We also notice that a legal expanded flow holds the following properties:
\end_layout

\begin_layout Enumerate
Anti-symmetricity: 
\begin_inset Formula $\forall u,v\in V:f^{'}\left(u,v\right)=-f^{'}\left(v,u\right)$
\end_inset

.
\end_layout

\begin_layout Enumerate
Constrained by expanded capacity: 
\begin_inset Formula $\forall u,v\in V:f^{'}\left(u,v\right)\leq C^{'}\left(u,v\right)$
\end_inset

.
\end_layout

\begin_layout Enumerate
Preserves mass on inner vertices: 
\begin_inset Formula $\forall u\in V\backslash\left\{ s,t\right\} :\sum_{v\in V}f^{'}\left(u,v\right)=0$
\end_inset

.
\end_layout

\begin_layout Lemma
If 
\begin_inset Formula $f$
\end_inset

 is a legal flow, then the expanded 
\begin_inset Formula $f^{'}$
\end_inset

 is a legal expanded flow.
\end_layout

\begin_layout Proof
We will prove for all three properties:
\end_layout

\begin_layout Proof
TODO
\end_layout

\begin_layout Section
Ford and Fulkerson's algorithm
\end_layout

\begin_layout Standard
Here we present Ford & Fulkerson's algorithm for finding the optimal flow
 in a flow network.
\end_layout

\begin_layout Standard
First we start with some definitions.
\end_layout

\begin_layout Definition
Residual flow network.
\end_layout

\begin_layout Definition
Let 
\begin_inset Formula $G=\left(V,E,C,s,t\right)$
\end_inset

 be a flow network, and 
\begin_inset Formula $f$
\end_inset

 a legal flow in it.
\end_layout

\begin_layout Definition
We define 
\begin_inset Formula $G$
\end_inset

's and 
\begin_inset Formula $f$
\end_inset

's residual network 
\begin_inset Formula $G_{f}=\left(V,E_{f},C_{f},s,t\right)$
\end_inset

 where:
\end_layout

\begin_layout Itemize
\begin_inset Formula $C_{f}\left(u,v\right)=C\left(u,v\right)-f\left(u,v\right)$
\end_inset

 (Residual capacity)
\end_layout

\begin_layout Itemize
\begin_inset Formula $E_{f}=\left\{ \left(u,v\right):C_{f}\left(u,v\right)>0\right\} $
\end_inset


\end_layout

\begin_layout Definition
Augmentation path.
\end_layout

\begin_layout Definition
An augmentation path of flow 
\begin_inset Formula $f$
\end_inset

 is a simple path (which visits each vertex at most once), in the resudual
 network 
\begin_inset Formula $G_{f}$
\end_inset

, from 
\begin_inset Formula $s$
\end_inset

 to 
\begin_inset Formula $t$
\end_inset

.
\end_layout

\begin_layout --Separator--

\end_layout

\begin_layout Definition
Residual capacity of an augmentation path.
\end_layout

\begin_layout Definition
Let 
\begin_inset Formula $P$
\end_inset

 be an augmentation path in 
\begin_inset Formula $G_{f}$
\end_inset

.
 We define the residual capacity of 
\begin_inset Formula $P$
\end_inset

 as the minimal capacity of all the edges of 
\begin_inset Formula $P$
\end_inset

: 
\begin_inset Formula $\Delta_{P}=\min_{e\in P}\left\{ C_{f}\left(e\right)\right\} $
\end_inset


\end_layout

\begin_layout --Separator--

\end_layout

\begin_layout Definition
Residual flow along the augmentation path.
\begin_inset CommandInset label
LatexCommand label
name "Residual-flow-along"

\end_inset


\end_layout

\begin_layout Definition
This is the maximal flow we can enforce on the augmentation path without
 violating any constraints (capacities, mass preservation, etc.).
\end_layout

\begin_layout Definition
We define 
\begin_inset Formula $\Delta_{P}f\left(u,v\right)=\begin{cases}
\Delta_{P} & \left(u,v\right)\in P\\
-\Delta_{P} & \left(v,u\right)\in P\\
0 & otherwise
\end{cases}$
\end_inset

.
\end_layout

\begin_layout Definition
We notice that 
\begin_inset Formula $\Delta_{P}f$
\end_inset

 is a legal flow in 
\begin_inset Formula $G_{f}$
\end_inset

.
\end_layout

\begin_layout --Separator--

\end_layout

\begin_layout Standard
\begin_inset Float algorithm
wide false
sideways false
status open

\begin_layout Enumerate
Initialize 
\begin_inset Formula $f=0$
\end_inset

.
\end_layout

\begin_layout Enumerate
While there is an augmentation path in 
\begin_inset Formula $G_{f}$
\end_inset

:
\end_layout

\begin_deeper
\begin_layout Enumerate
Find some augmentation path in 
\begin_inset Formula $G_{f}$
\end_inset

 and denote it with 
\begin_inset Formula $P$
\end_inset

.
\begin_inset CommandInset label
LatexCommand label
name "enu:Find-some-augmentation"

\end_inset


\end_layout

\begin_layout Enumerate
Update: 
\begin_inset Formula $f=f+\Delta_{P}f$
\end_inset

.
\end_layout

\end_deeper
\begin_layout Enumerate
Return 
\begin_inset Formula $f$
\end_inset

.
\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Ford and Fulkerson's algorithm
\end_layout

\end_inset


\begin_inset CommandInset label
LatexCommand label
name "enu:F&F_algo"

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Proof
\end_layout

\begin_layout Standard
We need to show:
\end_layout

\begin_layout Enumerate
\begin_inset Formula $f+\Delta_{P}f$
\end_inset

 is a legal flow.
\end_layout

\begin_layout Enumerate
In each iteration the flux is improved:
\begin_inset Formula $\left|f+\Delta_{P}f\right|>\left|f\right|$
\end_inset

.
\end_layout

\begin_layout Enumerate
As long as there is an augmentation path in the residual network of the
 current flow, then it is not optimal.
\end_layout

\begin_layout Subsubsection
Legality
\end_layout

\begin_layout Standard
We will show that 
\begin_inset Formula $f+\Delta_{P}f$
\end_inset

 is a legal flow in the flow network.
\end_layout

\begin_layout Standard
We denote 
\begin_inset Formula $g=f+\Delta_{P}f$
\end_inset

.
\end_layout

\begin_layout Paragraph
Anti-symmetricity
\end_layout

\begin_layout Standard
Both 
\begin_inset Formula $f$
\end_inset

 and 
\begin_inset Formula $\Delta_{P}f$
\end_inset

 are anti-symmetric, and so is 
\begin_inset Formula $g$
\end_inset

.
\end_layout

\begin_layout Paragraph
Capacity constraints
\end_layout

\begin_layout Standard
\begin_inset Formula $g\left(u,v\right)=f\left(u,v\right)+\Delta_{P}f\left(u,v\right)\leq f\left(u,v\right)+C_{f}\left(u,v\right)=f\left(u,v\right)+C\left(u,v\right)-f\left(u,v\right)=C\left(u,v\right)$
\end_inset

, as needed.
\end_layout

\begin_layout Paragraph
Mass preservation
\end_layout

\begin_layout Standard
\begin_inset Formula $\forall u\in V\backslash\left\{ s,t\right\} :\sum_{v\in V}g\left(u,v\right)=\sum_{v\in V}\left(f\left(u,v\right)+\Delta_{P}f\left(u,v\right)\right)=\underset{=0}{\underbrace{\sum_{v\in V}f\left(u,v\right)}}+\underset{=0}{\underbrace{\sum_{v\in V}\Delta_{P}f\left(u,v\right)}}=0$
\end_inset

, as needed.
\end_layout

\begin_layout Standard
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\begin_layout Subsubsection
Flux improvement
\end_layout

\begin_layout Standard
\begin_inset Formula $\left|f+\Delta_{P}f\right|=\left|f\right|+\left|\Delta_{P}f\right|>\left|f\right|$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\begin_layout Subsubsection
Optimallity (Max-Flow Min-Cut theorem)
\end_layout

\begin_layout Standard
We want to show that as long as there is an augmentation path in the residual
 network of the current flow, then it is not optimal.
\end_layout

\begin_layout Standard
We will prove a stronger statement:
\end_layout

\begin_layout Theorem
Max-Flow Min-Cut.
\end_layout

\begin_layout Theorem
The following are equivalent:
\end_layout

\begin_layout Enumerate
\begin_inset Formula $f$
\end_inset

 is an optimal flow in network 
\begin_inset Formula $G$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $G_{f}$
\end_inset

 has no augmentations paths.
\end_layout

\begin_layout Enumerate
There exists a cut 
\begin_inset Formula $\left(S,T\right)$
\end_inset

 such that 
\begin_inset Formula $f\left(S,T\right)=C\left(S,T\right)$
\end_inset

.
\end_layout

\begin_layout Proof
We will prove 
\begin_inset Formula $1\rightarrow2$
\end_inset

, 
\begin_inset Formula $2\rightarrow3$
\end_inset

, 
\begin_inset Formula $3\rightarrow1$
\end_inset


\end_layout

\begin_layout Proof
\begin_inset Formula $1\rightarrow2$
\end_inset

:
\end_layout

\begin_layout Proof
\begin_inset Formula $f$
\end_inset

 is an optimal flow in network 
\begin_inset Formula $G$
\end_inset

 and we want to show that 
\begin_inset Formula $G_{f}$
\end_inset

 has no augmentations paths.
\end_layout

\begin_layout Proof
If there was an augmentation paths we could have augmented the flow by 
\begin_inset Formula $f=f+\Delta_{P}f$
\end_inset

 and improve the flow.
 But this contradicts the optimality of 
\begin_inset Formula $f$
\end_inset

.
 Thus indeed there is no augmentation path in 
\begin_inset Formula $G_{f}$
\end_inset

.
\end_layout

\begin_layout Proof
\begin_inset Formula $2\rightarrow3$
\end_inset

:
\end_layout

\begin_layout Proof
\begin_inset Formula $G_{f}$
\end_inset

 has no augmentations paths and we want to show that there exists a cut
 
\begin_inset Formula $\left(S,T\right)$
\end_inset

 such that 
\begin_inset Formula $f\left(S,T\right)=C\left(S,T\right)$
\end_inset

.
\end_layout

\begin_layout Proof
\begin_inset Formula $G_{f}$
\end_inset

 has no augmentations paths, which means there is no path from 
\begin_inset Formula $s$
\end_inset

 to 
\begin_inset Formula $t$
\end_inset

 in the graph 
\begin_inset Formula $\left(V,E_{f}\right)$
\end_inset

.
 We can define the following cut 
\begin_inset Formula $\left(S,T\right)$
\end_inset

:
\end_layout

\begin_layout Proof
\begin_inset Formula $S$
\end_inset

 - every vertex 
\begin_inset Formula $v\in V$
\end_inset

 such that there is a path from 
\begin_inset Formula $s$
\end_inset

 to 
\begin_inset Formula $v$
\end_inset

.
\end_layout

\begin_layout Proof
\begin_inset Formula $T=V\backslash S$
\end_inset

.
\end_layout

\begin_layout Proof
Obviously 
\begin_inset Formula $s\in S$
\end_inset

 and 
\begin_inset Formula $t\in T$
\end_inset

.
 We notice that there are no edges of 
\begin_inset Formula $E_{f}$
\end_inset

 in the cut.
 I.e.
 
\begin_inset Formula $\forall u\in S,v\in T:\left(u,v\right)\notin E_{f}$
\end_inset

, otherwise there was a path from 
\begin_inset Formula $s$
\end_inset

 to 
\begin_inset Formula $v\in T$
\end_inset

, which contradicts the definition of 
\begin_inset Formula $S$
\end_inset

 and 
\begin_inset Formula $T$
\end_inset

.
 By the definition of 
\begin_inset Formula $E_{f}$
\end_inset

 this means that 
\begin_inset Formula $\forall u\in S,v\in T:C_{f}\left(u,v\right)=0$
\end_inset

.
 And by the definition of 
\begin_inset Formula $C_{f}$
\end_inset

 we have 
\begin_inset Formula $\forall u\in S,v\in T:C\left(u,v\right)=f\left(u,v\right)$
\end_inset

.
 So now we can conclude 
\begin_inset Formula $f\left(S,T\right)=\sum_{u\in S,v\in T}f\left(u,v\right)=\sum_{u\in S,v\in T}C\left(u,v\right)=C\left(S,T\right)$
\end_inset

, as needed.
\end_layout

\begin_layout Proof
\begin_inset Formula $3\rightarrow1$
\end_inset

:
\end_layout

\begin_layout Proof
There exists a cut 
\begin_inset Formula $\left(S,T\right)$
\end_inset

 such that 
\begin_inset Formula $f\left(S,T\right)=C\left(S,T\right)$
\end_inset

 and we want to show that 
\begin_inset Formula $f$
\end_inset

 is an optimal flow in network 
\begin_inset Formula $G$
\end_inset

.
\end_layout

\begin_layout Proof
We have already seen in [TODO] that for any cut 
\begin_inset Formula $\left(S^{'},T^{'}\right)$
\end_inset

 and any flow 
\begin_inset Formula $g$
\end_inset

 in the network it holds that 
\begin_inset Formula $\left|g\right|\leq C\left(S^{'},T^{'}\right)$
\end_inset

.
 If 
\begin_inset Formula $f$
\end_inset

 was not optimal, then there is some other flow 
\begin_inset Formula $g$
\end_inset

 such that 
\begin_inset Formula $\left|g\right|>\left|f\right|$
\end_inset

.
 But then, for any cut 
\begin_inset Formula $\left(S^{'},T^{'}\right)$
\end_inset

 we would have 
\begin_inset Formula $\left|f\right|<C\left(S^{'},T^{'}\right)$
\end_inset

, and specifically for 
\begin_inset Formula $\left(S,T\right)$
\end_inset

: 
\begin_inset Formula $\left|f\right|<C\left(S,T\right)$
\end_inset

.
 This is in contradiction to 
\begin_inset Formula $f\left(S,T\right)=C\left(S,T\right)$
\end_inset

.
 Thus 
\begin_inset Formula $f$
\end_inset

 is indeed optimal.
\end_layout

\begin_layout Section
Edmonds and Karp's algorithm
\end_layout

\begin_layout Standard
Edmond & Karp's algorithm is actually an improvement to Ford & Fulkerson's
 algorithm.
 In step 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:Find-some-augmentation"

\end_inset

 of algorithm 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:F&F_algo"

\end_inset

, instead of choosing some arbitrary augmentation path, we choose the shortest
 augmentation path (length wise).
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
wide false
sideways false
status open

\begin_layout Enumerate
Initialize 
\begin_inset Formula $f=0$
\end_inset

.
\end_layout

\begin_layout Enumerate
While there is an augmentation path in 
\begin_inset Formula $G_{f}$
\end_inset

:
\end_layout

\begin_deeper
\begin_layout Enumerate
Find the shortest augmentation path in 
\begin_inset Formula $G_{f}$
\end_inset

 and denote it with 
\begin_inset Formula $P$
\end_inset

.
\begin_inset CommandInset label
LatexCommand label
name "enu:Find-the-shortest"

\end_inset


\end_layout

\begin_layout Enumerate
Update: 
\begin_inset Formula $f=f+\Delta_{P}f$
\end_inset

.
\end_layout

\end_deeper
\begin_layout Enumerate
Return 
\begin_inset Formula $f$
\end_inset

.
\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Edmonds and Karp's algorithm
\end_layout

\end_inset


\begin_inset CommandInset label
LatexCommand label
name "enu:E&K_Algo"

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
In order to find the shortest augmentation path, we can use, for example,
 the BFS algorithm.
 The runtime of BFS is 
\begin_inset Formula $O\left(\left|E\right|\right)$
\end_inset

.
\end_layout

\begin_layout Subsection
Edmond and Karp's theorem
\end_layout

\begin_layout Theorem
Edmonds and Karp.
\end_layout

\begin_layout Theorem
Algorithm 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:E&K_Algo"

\end_inset

 performs 
\begin_inset Formula $O\left(\left|E\right|\cdot\left|V\right|\right)$
\end_inset

 iterations.
\end_layout

\begin_layout Subsubsection
Proof
\end_layout

\begin_layout Standard
First, some denotations:
\end_layout

\begin_layout Itemize
\begin_inset Formula $f_{i}$
\end_inset

 the flow after the 
\begin_inset Formula $i$
\end_inset

'th iteration.
\end_layout

\begin_layout Itemize
\begin_inset Formula $P_{i-1}$
\end_inset

 the augmentation path of step 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:Find-the-shortest"

\end_inset

 in the 
\begin_inset Formula $i$
\end_inset

'th iteration.
\end_layout

\begin_layout Itemize
\begin_inset Formula $G_{f_{i}}=\left(V,E_{f_{i}},C_{f_{i}},s,t\right)$
\end_inset

 the residual network after the 
\begin_inset Formula $i$
\end_inset

'th iteration.
\end_layout

\begin_layout Itemize
\begin_inset Formula $\delta_{i}\left(v\right)$
\end_inset

 the minimal distance of vertex 
\begin_inset Formula $v\in V$
\end_inset

 from the source 
\begin_inset Formula $s$
\end_inset

 in the graph 
\begin_inset Formula $\left(V,E_{f_{i}}\right)$
\end_inset

.
\end_layout

\begin_layout Standard
Some remarks:
\end_layout

\begin_layout Remark
\begin_inset Formula $f_{i}=f_{i-1}+\Delta_{P_{i-1}}f_{i-1}$
\end_inset

.
\end_layout

\begin_layout --Separator--

\end_layout

\begin_layout Remark
The algorithm stops when 
\begin_inset Formula $\delta_{i}\left(t\right)=\infty$
\end_inset

, because this means there is no augmentation path in 
\begin_inset Formula $G_{f_{i}}$
\end_inset

 (no way to reach 
\begin_inset Formula $t$
\end_inset

 from 
\begin_inset Formula $s$
\end_inset

).
\end_layout

\begin_layout --Separator--

\end_layout

\begin_layout Remark
Let 
\begin_inset Formula $P$
\end_inset

 be a path of minimal length between 
\begin_inset Formula $s$
\end_inset

 and some vertex 
\begin_inset Formula $v$
\end_inset

.
 Then for every vertex 
\begin_inset Formula $x$
\end_inset

 in this path, the distance from 
\begin_inset Formula $s$
\end_inset

 to 
\begin_inset Formula $x$
\end_inset

 in this path is the minimal distance between 
\begin_inset Formula $s$
\end_inset

 and 
\begin_inset Formula $x$
\end_inset

 in the graph.
 Specifically, if 
\begin_inset Formula $x$
\end_inset

 and 
\begin_inset Formula $y$
\end_inset

 are two adjacent vertices in the path such that 
\begin_inset Formula $x$
\end_inset

 appears before 
\begin_inset Formula $y$
\end_inset

, then 
\begin_inset Formula $\delta\left(y\right)=\delta\left(x\right)+1$
\end_inset

.
\end_layout

\begin_layout --Separator--

\end_layout

\begin_layout Remark
In the 
\begin_inset Formula $i$
\end_inset

'th iteration, the flow 
\begin_inset Formula $f_{i}$
\end_inset

 is larger than 
\begin_inset Formula $f_{i-1}$
\end_inset

 in all the edges along the augmentation path 
\begin_inset Formula $P_{i-1}$
\end_inset

 by 
\begin_inset Formula $\Delta_{P_{i-1}}$
\end_inset

, and it is smaller than 
\begin_inset Formula $f_{i-1}$
\end_inset

, in the opposite direction, by 
\begin_inset Formula $\Delta_{P_{i-1}}$
\end_inset

 (we conclude this from definition 
\begin_inset CommandInset ref
LatexCommand ref
reference "Residual-flow-along"

\end_inset

).
\end_layout

\begin_layout Corollary
If 
\begin_inset Formula $\left(u,v\right)\in G_{f_{i-1}}$
\end_inset

 and 
\begin_inset Formula $\left(u,v\right)\notin G_{f_{i}}$
\end_inset

 then the flow in 
\begin_inset Formula $\left(u,v\right)$
\end_inset

 was reduced, which must mean that the flow in 
\begin_inset Formula $\left(v,u\right)$
\end_inset

 was increased, thus 
\begin_inset Formula $\left(v,u\right)\in P_{i-1}$
\end_inset

.
\begin_inset CommandInset label
LatexCommand label
name "cor:If-uv-decreased-vu-increased"

\end_inset


\end_layout

\begin_layout Standard
Some lemmas:
\end_layout

\begin_layout Lemma
\begin_inset Formula $\forall v\in V:\delta_{i}\left(v\right)\leq\delta_{i+1}\left(v\right)\leq\infty$
\end_inset

 and if 
\begin_inset Formula $\delta_{i}\left(v\right)=\infty$
\end_inset

 then also 
\begin_inset Formula $\delta_{i+1}\left(v\right)=\infty$
\end_inset

.
\begin_inset CommandInset label
LatexCommand label
name "lem:delta_i_i+1"

\end_inset


\end_layout

\begin_layout Proof
First we will show the second part.
\end_layout

\begin_layout Proof
We prove by negation.
 Assume there is a vertex 
\begin_inset Formula $v\in V$
\end_inset

 and an index 
\begin_inset Formula $i$
\end_inset

 for which 
\begin_inset Formula $\delta_{i}\left(v\right)=\infty$
\end_inset

 but 
\begin_inset Formula $\delta_{i+1}\left(v\right)<\infty$
\end_inset

.
 If there are several such vertices, we choose 
\begin_inset Formula $v$
\end_inset

 to be the closest one to 
\begin_inset Formula $s$
\end_inset

 in 
\begin_inset Formula $G_{f_{i+1}}$
\end_inset

.
 We denote the shortest path from 
\begin_inset Formula $s$
\end_inset

 to 
\begin_inset Formula $v$
\end_inset

 in 
\begin_inset Formula $G_{f_{i+1}}$
\end_inset

 with 
\begin_inset Formula $P$
\end_inset

, and the vertex which comes before 
\begin_inset Formula $v$
\end_inset

 in 
\begin_inset Formula $P$
\end_inset

 as 
\begin_inset Formula $u$
\end_inset

, so 
\begin_inset Formula $P=\left(s,...,u,v\right)$
\end_inset

.
 Because 
\begin_inset Formula $\delta_{i+1}\left(v\right)<\infty$
\end_inset

 then also 
\begin_inset Formula $\delta_{i+1}\left(u\right)<\infty$
\end_inset

 (because 
\begin_inset Formula $u$
\end_inset

 is closer to 
\begin_inset Formula $s$
\end_inset

 than 
\begin_inset Formula $v$
\end_inset

).
 And because 
\begin_inset Formula $\delta_{i+1}\left(u\right)<\infty$
\end_inset

 then also 
\begin_inset Formula $\delta_{i}\left(u\right)<\infty$
\end_inset

 (we chose 
\begin_inset Formula $v$
\end_inset

 as the closest vertex to 
\begin_inset Formula $s$
\end_inset

 which doesn't hold this).
 Now we have 
\begin_inset Formula $\delta_{i}\left(v\right)=\infty$
\end_inset

 and 
\begin_inset Formula $\delta_{i}\left(u\right)<\infty$
\end_inset

, which means that 
\begin_inset Formula $\left(u,v\right)\notin G_{f_{i}}$
\end_inset

.
 But 
\begin_inset Formula $\left(u,v\right)\in G_{f_{i+1}}$
\end_inset

, so by corollary 
\begin_inset CommandInset ref
LatexCommand ref
reference "cor:If-uv-decreased-vu-increased"

\end_inset

 the edge 
\begin_inset Formula $\left(v,u\right)$
\end_inset

 was in the augmentation path of the 
\begin_inset Formula $i$
\end_inset

'th iteration, which means that there is a path from 
\begin_inset Formula $s$
\end_inset

 to 
\begin_inset Formula $v$
\end_inset

 in the 
\begin_inset Formula $i$
\end_inset

'th iteration.
 This contradicts the assumption that 
\begin_inset Formula $\delta_{i}\left(v\right)=\infty$
\end_inset

.
 Thus we conclude that if 
\begin_inset Formula $\delta_{i}\left(v\right)=\infty$
\end_inset

 then also 
\begin_inset Formula $\delta_{i+1}\left(v\right)=\infty$
\end_inset

.
\end_layout

\begin_layout Proof
Now we will show the first part.
\end_layout

\begin_layout Proof
Again we prove by negation.
 Assume there is a vertex 
\begin_inset Formula $v\in V$
\end_inset

 and an index 
\begin_inset Formula $i$
\end_inset

 for which 
\begin_inset Formula $\delta_{i}\left(v\right)>\delta_{i+1}\left(v\right)$
\end_inset

.
 If there are several such vertices, we choose 
\begin_inset Formula $v$
\end_inset

 to be the closest one to 
\begin_inset Formula $s$
\end_inset

 in 
\begin_inset Formula $G_{f_{i+1}}$
\end_inset

.
 We denote the shortest path from 
\begin_inset Formula $s$
\end_inset

 to 
\begin_inset Formula $v$
\end_inset

 in 
\begin_inset Formula $G_{f_{i+1}}$
\end_inset

 with 
\begin_inset Formula $P$
\end_inset

, and the vertex which comes before 
\begin_inset Formula $v$
\end_inset

 in 
\begin_inset Formula $P$
\end_inset

 as 
\begin_inset Formula $u$
\end_inset

, so 
\begin_inset Formula $P=\left(s,...,u,v\right)$
\end_inset

.
 It is evident that 
\begin_inset Formula $\delta_{i+1}\left(v\right)=\delta_{i+1}\left(u\right)+1$
\end_inset

.
 Also, 
\begin_inset Formula $\delta_{i}\left(u\right)\leq\delta_{i+1}\left(u\right)$
\end_inset

 (we chose 
\begin_inset Formula $v$
\end_inset

 as the closest vertex to 
\begin_inset Formula $s$
\end_inset

 which doesn't hold this).
 Now we have 
\begin_inset Formula $\left(u,v\right)\notin G_{f_{i}}$
\end_inset

, because otherwise 
\begin_inset Formula $\delta_{i+1}\left(v\right)=\delta_{i+1}\left(u\right)+1\geq\delta_{i}\left(u\right)+1\underset{if\,\left(u,v\right)\in G_{f_{i}}}{\underbrace{=}}\delta_{i}\left(v\right)$
\end_inset

, which contradicts our assumption.
 So finally we have 
\begin_inset Formula $\left(u,v\right)\notin G_{f_{i}}$
\end_inset

 and 
\begin_inset Formula $\left(u,v\right)\in G_{f_{i+1}}$
\end_inset

.
 As before, we conclude that 
\begin_inset Formula $\left(v,u\right)$
\end_inset

 was an edge in the augmentation path in the 
\begin_inset Formula $i$
\end_inset

'th iteration, so 
\begin_inset Formula $\delta_{i}\left(u\right)=\delta_{i}\left(v\right)+1$
\end_inset

.
 Remember the assumption 
\begin_inset Formula $\delta_{i}\left(v\right)>\delta_{i+1}\left(v\right)$
\end_inset

.
 So now 
\begin_inset Formula $\delta_{i}\left(v\right)>\delta_{i+1}\left(v\right)=\delta_{i+1}\left(u\right)+1\geq\delta_{i}\left(u\right)+1=\delta_{i}\left(v\right)+2$
\end_inset

.
 Finally we have 
\begin_inset Formula $\delta_{i}\left(v\right)>\delta_{i}\left(v\right)+2$
\end_inset

, which is obviously impossible.
 Thus we conclude that 
\begin_inset Formula $\forall v\in V:\delta_{i}\left(v\right)\leq\delta_{i+1}\left(v\right)$
\end_inset

.
\end_layout

\begin_layout Definition
Critical edge.
\end_layout

\begin_layout Definition
\begin_inset Formula $\left(u,v\right)$
\end_inset

 is a critical edge for flow 
\begin_inset Formula $f_{i-1}$
\end_inset

 if its residual capacity 
\begin_inset Formula $C_{f_{i-1}}\left(u,v\right)$
\end_inset

 in the augmentation path 
\begin_inset Formula $P_{i-1}$
\end_inset

 is minimal.
 In other words, this edge is the bottleneck of 
\begin_inset Formula $P_{i-1}$
\end_inset

.
\end_layout

\begin_layout Lemma
For every 
\begin_inset Formula $u,v\in V$
\end_inset

 the edge 
\begin_inset Formula $\left(u,v\right)$
\end_inset

 can be a critical edge in at most 
\begin_inset Formula $O\left(\left|V\right|\right)$
\end_inset

 iterations.
\begin_inset CommandInset label
LatexCommand label
name "lem:For-every-at-most-O(V)"

\end_inset


\end_layout

\begin_layout Proof
Let 
\begin_inset Formula $i,j$
\end_inset

 (
\begin_inset Formula $i<j$
\end_inset

) be two different iterations in algorithm 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:E&K_Algo"

\end_inset

 such that in both the edge 
\begin_inset Formula $\left(u,v\right)$
\end_inset

 is a critical edge.
\end_layout

\begin_layout Proof
Because 
\begin_inset Formula $\left(u,v\right)$
\end_inset

 is critical in the 
\begin_inset Formula $i$
\end_inset

'th iteration, it means that 
\begin_inset Formula $\left(u,v\right)\notin G_{f_{i}}$
\end_inset

.
 But by the assumption, there is some later iteration in which 
\begin_inset Formula $\left(u,v\right)$
\end_inset

 is again a critical edge.
 This means that 
\begin_inset Formula $\left(u,v\right)$
\end_inset

 must reappear in some iteration 
\begin_inset Formula $k$
\end_inset

 between 
\begin_inset Formula $i$
\end_inset

 and 
\begin_inset Formula $j$
\end_inset

 (
\begin_inset Formula $i<k<j$
\end_inset

).
 This means that at some point there was a flow in the opposite direction
 (on 
\begin_inset Formula $\left(v,u\right)$
\end_inset

), in other words 
\begin_inset Formula $\left(v,u\right)\in P_{k}$
\end_inset

.
 This means that in the 
\begin_inset Formula $k$
\end_inset

'th iteration 
\begin_inset Formula $\delta_{k}\left(u\right)=\delta_{k}\left(v\right)+1$
\end_inset

.
 Also, because 
\begin_inset Formula $\left(u,v\right)$
\end_inset

 is an edge in the augmentation path of the 
\begin_inset Formula $i$
\end_inset

'th iteration we have 
\begin_inset Formula $\delta_{i}\left(v\right)=\delta_{i}\left(u\right)+1$
\end_inset

.
\end_layout

\begin_layout Proof
From lemma 
\begin_inset CommandInset ref
LatexCommand ref
reference "lem:delta_i_i+1"

\end_inset

 we have 
\begin_inset Formula $\delta_{k}\left(v\right)\geq\delta_{i}\left(v\right)$
\end_inset

 and 
\begin_inset Formula $\delta_{j}\left(u\right)\geq\delta_{k}\left(u\right)$
\end_inset

.
 Thus 
\begin_inset Formula $\delta_{j}\left(u\right)\geq\delta_{k}\left(u\right)=\delta_{k}\left(v\right)+1\geq\delta_{i}\left(v\right)+1=\delta_{i}\left(u\right)+1+1=\delta_{i}\left(u\right)+2$
\end_inset

.
 Finally we obtained 
\begin_inset Formula $\delta_{j}\left(u\right)\geq\delta_{i}\left(u\right)+2$
\end_inset

.
\end_layout

\begin_layout Proof
Obviously 
\begin_inset Formula $\delta\left(u\right)$
\end_inset

 is bounded by 
\begin_inset Formula $\left|V\right|$
\end_inset

 (for any iteration, as long as 
\begin_inset Formula $\delta\left(u\right)<\infty$
\end_inset

).
 Because 
\begin_inset Formula $\delta\left(u\right)$
\end_inset

 increases by at least 2 between any two iterations in which 
\begin_inset Formula $\left(u,v\right)$
\end_inset

 is critical, we conclude that 
\begin_inset Formula $\left(u,v\right)$
\end_inset

 can be critical at most 
\begin_inset Formula $\frac{\left|V\right|}{2}$
\end_inset

 times, which is 
\begin_inset Formula $O\left(\left|V\right|\right)$
\end_inset

, as needed.
\end_layout

\begin_layout Corollary
Because there are at most 
\begin_inset Formula $2\left|E\right|$
\end_inset

 edges in each residual network, and because each edge can be critical 
\begin_inset Formula $O\left(\left|V\right|\right)$
\end_inset

 times (by lemma 
\begin_inset CommandInset ref
LatexCommand ref
reference "lem:For-every-at-most-O(V)"

\end_inset

), we conclude that the algorithm performs 
\begin_inset Formula $O\left(\left|E\right|\cdot\left|V\right|\right)$
\end_inset

 iterations.
 
\begin_inset CommandInset label
LatexCommand label
name "cor:Because-there-are-O(EV)-corollary"

\end_inset


\end_layout

\begin_layout Standard
With corollary 
\begin_inset CommandInset ref
LatexCommand ref
reference "cor:Because-there-are-O(EV)-corollary"

\end_inset

 we complete the proof.
 
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\begin_layout Section
Examples
\end_layout

\begin_layout Subsection
Maximal matching in a bipartite graph
\end_layout

\begin_layout Standard
We have an undirected bipartite graph 
\begin_inset Formula $G=\left(L,R,E\right)$
\end_inset

, and we want to find a maximal matching.
\end_layout

\begin_layout Subsubsection
Algorithm which uses a flow network
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
wide false
sideways false
status open

\begin_layout Enumerate
Construct a flow network 
\begin_inset Formula $G=\left(V^{'},E^{'},C,s,t\right)$
\end_inset

:
\end_layout

\begin_deeper
\begin_layout Enumerate
\begin_inset Formula $V^{'}=L\cup R\cup\left\{ s,t\right\} $
\end_inset

 (with 
\begin_inset Formula $s$
\end_inset

 and 
\begin_inset Formula $t$
\end_inset

 as some artificial vertices).
\end_layout

\begin_layout Enumerate
\begin_inset Formula $E^{'}=\left\{ \left(s,v\right):v\in L\right\} \cup\left\{ \left(v,t\right):v\in R\right\} \cup\vec{E}$
\end_inset

 (where 
\begin_inset Formula $\vec{E}$
\end_inset

 is a set of the edges in 
\begin_inset Formula $E$
\end_inset

 directed from 
\begin_inset Formula $L$
\end_inset

 to 
\begin_inset Formula $R$
\end_inset

).
\end_layout

\begin_layout Enumerate
\begin_inset Formula $\forall e\in E^{'}:C\left(e\right)=1$
\end_inset

.
\end_layout

\end_deeper
\begin_layout Enumerate
Find the maximal flow on the network.
\end_layout

\begin_layout Enumerate
Return all the original edges on which the flow is 1: 
\begin_inset Formula $M=\left\{ e\in\vec{E}|f\left(e\right)=1\right\} $
\end_inset

.
\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Maximal matching in a bipartite graph (with flow network)
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection
Proof of legality
\end_layout

\begin_layout Standard
We need to show that the solution of the algorithm (
\begin_inset Formula $M$
\end_inset

) is indeed a legal matching.
\end_layout

\begin_layout Standard
We prove by negation.
 Assume there is a vertex 
\begin_inset Formula $v$
\end_inset

 which touces more than one edge in 
\begin_inset Formula $M$
\end_inset

.
\end_layout

\begin_layout Standard
If 
\begin_inset Formula $v\in R$
\end_inset

, then it has one outgoing edge 
\begin_inset Formula $\left(v,t\right)$
\end_inset

 which has capacity 
\begin_inset Formula $C\left(v,t\right)=1$
\end_inset

.
 Because all the capacities are integers...
\end_layout

\begin_layout Standard
[TODO]
\end_layout

\begin_layout Subsection
Roads and advertisements
\end_layout

\begin_layout Standard
A town has a system of 1-way or 2-way roads and junctions.
 We denote 
\begin_inset Formula $A=\left(a_{1},a_{2},...,a_{n}\right)$
\end_inset

 the set of junctions.
 
\begin_inset Formula $E\subseteq A$
\end_inset

 is a subset of entrance junctions, through which one can enter the town.
 We have a store on one of the junctions which we want to advertise.
 We want our advertisements to appear on at least one junction on any path
 from one of the entrance junctions to our store's junction.
 The cost of putting an advertisement on junction 
\begin_inset Formula $a_{i}$
\end_inset

 is 
\begin_inset Formula $s_{i}$
\end_inset

.
 Our goal is to find a subset of the junctions 
\begin_inset Formula $A^{'}\subseteq A$
\end_inset

 that satisfies this condition, and that has a minimal cost (minimize 
\begin_inset Formula $\sum_{a_{i}\in A^{'}}s_{i}$
\end_inset

).
\end_layout

\begin_layout Subsubsection
Algorithm which uses a flow network
\end_layout

\begin_layout Standard
TODO
\end_layout

\begin_layout Standard

\end_layout

\begin_layout Chapter
Fast Fourier Transform
\begin_inset Index idx
status open

\begin_layout Plain Layout
Fast Fourier Transform
\end_layout

\end_inset


\end_layout

\begin_layout Section
Proof that FFT solves DFT
\end_layout

\begin_layout Subsection
Denotations and definitions
\end_layout

\begin_layout Itemize
Coefficients representation of a polynomial: The vector which represents
 the polynomial in the monomial basis 
\begin_inset Formula $1,x,x^{2},...,x^{n-1}$
\end_inset

 is called the 
\emph on
coefficients representation
\emph default
.
 If we have coefficients representation 
\begin_inset Formula $\left(a_{0},a_{1},...,a_{n-1}\right)$
\end_inset

 then the polynomial is given by 
\begin_inset Formula $p\left(x\right)=\sum_{i=0}^{n-1}a_{i}x^{i}$
\end_inset

.
\end_layout

\begin_layout Itemize
Values representation of a polynomial: Given 
\begin_inset Formula $n$
\end_inset

 points 
\begin_inset Formula $x_{0},x_{1},...,x_{n-1}$
\end_inset

, the values of the polynomial in these points (
\begin_inset Formula $\left(p\left(x_{0}\right),p\left(x_{1}\right),...,p\left(x_{n-1}\right)\right)$
\end_inset

) is called the 
\emph on
values representation
\emph default
 of the polynomial.
 The vector of these values is in the Lagrange basis 
\begin_inset Formula $L_{0}\left(x\right),L_{1}\left(x\right),...,L_{n-1}\left(x\right)$
\end_inset

, where 
\begin_inset Formula $L_{i}\left(x\right)=\frac{\left(x-x_{0}\right)\cdot...\cdot\left(x-x_{i-1}\right)\cdot\left(x-x_{i+1}\right)\cdot...\cdot\left(x-x_{n-1}\right)}{\left(x_{i}-x_{0}\right)\cdot...\cdot\left(x_{i}-x_{i-1}\right)\cdot\left(x_{i}-x_{i+1}\right)\cdot...\cdot\left(x_{i}-x_{n-1}\right)}$
\end_inset

.
 The polynomial is given by 
\begin_inset Formula $p\left(x\right)=\sum_{i=0}^{n-1}p\left(x_{i}\right)L_{i}\left(x\right)$
\end_inset

.
\end_layout

\begin_layout Itemize
\begin_inset Formula $\omega_{n}$
\end_inset

 - primitive root of unity of order 
\begin_inset Formula $n$
\end_inset

: 
\begin_inset Formula $\omega_{n}=e^{\frac{2\pi i}{n}}$
\end_inset

.
\end_layout

\begin_layout Itemize
\begin_inset Formula $M$
\end_inset

 - the Vandermonde matrix which we use for the basis transformation from
 the monomial basis to the Lagrange basis.
 If the values representation of the polynomial is needed on points 
\begin_inset Formula $x_{0},x_{1},...,x_{n-1}$
\end_inset

, then 
\begin_inset Formula $M=\left(\begin{array}{cccc}
x_{0}^{0} & x_{0}^{1} & \cdots & x_{0}^{n-1}\\
x_{1}^{0} & x_{1}^{1} & \cdots & x_{1}^{n-1}\\
\vdots & \vdots & \ddots & \vdots\\
x_{n-1}^{0} & x_{n-1}^{1} & \cdots & x_{n-1}^{n-1}
\end{array}\right)=\left(x_{i}^{j}\right)_{i,j=0}^{n-1}$
\end_inset

.
 And now 
\begin_inset Formula $\left(\begin{array}{c}
p\left(x_{0}\right)\\
p\left(x_{1}\right)\\
\vdots\\
p\left(x_{n-1}\right)
\end{array}\right)=M\left(\begin{array}{c}
a_{0}\\
a_{1}\\
\vdots\\
a_{n-1}
\end{array}\right)$
\end_inset

.
 If we choose the points to be the roots of unity of order 
\begin_inset Formula $n$
\end_inset

, 
\begin_inset Formula $1,\omega_{n},\omega_{n}^{2},...,\omega_{n}^{n-1}$
\end_inset

, then we have 
\begin_inset Formula $M=\left(\left(\omega_{n}\right)^{i\cdot j}\right)_{i,j=0}^{n-1}$
\end_inset

.
\end_layout

\begin_layout Itemize
\begin_inset Formula $M^{-1}$
\end_inset

 - the inverse Vandermonde matrix which we use for the basis transformation
 from the Lagrange basis to the monomial basis.
 If we choose the points to be the roots of unity of order 
\begin_inset Formula $n$
\end_inset

, 
\begin_inset Formula $1,\omega_{n},\omega_{n}^{2},...,\omega_{n}^{n-1}$
\end_inset

, then we have 
\begin_inset Formula $M^{-1}=\frac{1}{n}\left(\left(\omega_{n}\right)^{-i\cdot j}\right)_{i,j=0}^{n-1}$
\end_inset

.
\end_layout

\begin_layout Subsection
The lemma
\end_layout

\begin_layout Standard
Given a coefficients representation 
\begin_inset Formula $\left(\begin{array}{c}
a_{0}\\
\vdots\\
a_{n-1}
\end{array}\right)$
\end_inset

 we want to calculate the corresponding values representation 
\series bold
on the roots of unity
\series default
 
\begin_inset Formula $\left(\begin{array}{c}
p\left(\left(w_{n}\right)^{0}\right)\\
p\left(\left(w_{n}\right)^{1}\right)\\
\vdots\\
p\left(\left(w_{n}\right)^{n-1}\right)
\end{array}\right)$
\end_inset

.
\end_layout

\begin_layout Standard
We already know that, given the corresponding Vandermonde matrix, 
\begin_inset Formula $\left(\begin{array}{c}
p\left(\left(w_{n}\right)^{0}\right)\\
p\left(\left(w_{n}\right)^{1}\right)\\
\vdots\\
p\left(\left(w_{n}\right)^{n-1}\right)
\end{array}\right)=M\left(\begin{array}{c}
a_{0}\\
a_{1}\\
\vdots\\
a_{n-1}
\end{array}\right)$
\end_inset

.
 But this is a lengthy calculation - multiplying a matrix with a vector
 is 
\begin_inset Formula $O\left(n^{2}\right)$
\end_inset

.
 We want to do this in 
\begin_inset Formula $O\left(n\log n\right)$
\end_inset

.
\end_layout

\begin_layout Standard
We denote the matrix 
\begin_inset Formula $M$
\end_inset

 with 
\begin_inset Formula $DFT_{n}$
\end_inset

 and 
\begin_inset Formula $M^{-1}$
\end_inset

 with 
\begin_inset Formula $DFT_{n}^{-1}$
\end_inset

.
\end_layout

\begin_layout Lemma
We can make the calculation shorter with the following recurrsion formula:
\begin_inset CommandInset label
LatexCommand label
name "lem:DFT_Lemma"

\end_inset


\end_layout

\begin_layout Lemma
\begin_inset Formula $DFT_{n}\left(\begin{array}{c}
a_{0}\\
a_{1}\\
\vdots\\
a_{n-1}
\end{array}\right)=\left(\begin{array}{c}
DFT_{\frac{n}{2}}\left(\begin{array}{c}
a_{0}\\
a_{2}\\
\vdots\\
a_{n-2}
\end{array}\right)\\
DFT_{\frac{n}{2}}\left(\begin{array}{c}
a_{0}\\
a_{2}\\
\vdots\\
a_{n-2}
\end{array}\right)
\end{array}\right)+\left(\begin{array}{c}
\left(w_{n}\right)^{0}\\
\left(w_{n}\right)^{1}\\
\vdots\\
\left(w_{n}\right)^{n-1}
\end{array}\right)\cdot\left(\begin{array}{c}
DFT_{\frac{n}{2}}\left(\begin{array}{c}
a_{1}\\
a_{3}\\
\vdots\\
a_{n-1}
\end{array}\right)\\
DFT_{\frac{n}{2}}\left(\begin{array}{c}
a_{1}\\
a_{3}\\
\vdots\\
a_{n-1}
\end{array}\right)
\end{array}\right)$
\end_inset


\end_layout

\begin_layout Lemma
(with the last product 
\begin_inset Formula $\cdot$
\end_inset

 as an element-by-element product).
\end_layout

\begin_layout Remark
Lemma 
\begin_inset CommandInset ref
LatexCommand ref
reference "lem:DFT_Lemma"

\end_inset

 works for any 
\begin_inset Formula $n$
\end_inset

 (the order of the roots of unity) which is a power of 
\begin_inset Formula $2$
\end_inset

.
 But this can always be arranged by padding the coefficients representation
 of the polynomial with zeros in the end.
\end_layout

\begin_layout Subsection
The proof
\end_layout

\begin_layout Standard
We will now prove lemma 
\begin_inset CommandInset ref
LatexCommand ref
reference "lem:DFT_Lemma"

\end_inset

.
 We do this by showing that the vectors on both sides of the equation are
 equal on all indices.
\end_layout

\begin_layout Standard
We denote 
\begin_inset Formula $m=\frac{n}{2}$
\end_inset

 (remember 
\begin_inset Formula $n$
\end_inset

 is a power of 
\begin_inset Formula $2$
\end_inset

), 
\begin_inset Formula $\omega$
\end_inset

 as the primitive root of unity of order 
\begin_inset Formula $n$
\end_inset

 and 
\begin_inset Formula $\eta$
\end_inset

 as the primitive root of unity of order 
\begin_inset Formula $m$
\end_inset

.
 Notice that 
\begin_inset Formula $\eta=\omega^{2}$
\end_inset

.
\end_layout

\begin_layout Standard
We also denote
\begin_inset Formula $M=DFT_{n}=\left(\omega^{a\cdot b}\right)_{a,b=0}^{n-1}$
\end_inset

 and 
\begin_inset Formula $L=DFT_{m}=\left(\eta^{a\cdot b}\right)_{a,b=0}^{m-1}$
\end_inset

.
\end_layout

\begin_layout Standard
We will now examine the 
\begin_inset Formula $k$
\end_inset

'th element on the vectors in both sides of the equation.
\end_layout

\begin_layout Paragraph
Case 1 - 
\begin_inset Formula $0\leq k\leq m-1$
\end_inset

 (
\begin_inset Formula $0\leq k\leq\frac{n}{2}-1$
\end_inset

):
\end_layout

\begin_layout Standard

\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none
\begin_inset Formula $DFT_{n}\left(\begin{array}{c}
a_{0}\\
a_{1}\\
\vdots\\
a_{n-1}
\end{array}\right)$
\end_inset

 in the 
\begin_inset Formula $k$
\end_inset

'th element is given by 
\begin_inset Formula $\sum_{t=0}^{n-1}\left[M\right]_{k,t}\cdot a_{t}=\sum_{t=0}^{n-1}\omega^{k\cdot t}\cdot a_{t}$
\end_inset

.
\end_layout

\begin_layout Standard
We can decompose this expression as follows:
\end_layout

\begin_layout Standard

\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none
\begin_inset Formula $\sum_{t=0}^{n-1}\omega^{k\cdot t}\cdot a_{t}=\underset{even\, t's}{\underbrace{\sum}}\omega^{k\cdot t}\cdot a_{t}+\underset{odd\, t's}{\underbrace{\sum}}\omega^{k\cdot t}\cdot a_{t}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\underset{even\, t's}{\underbrace{\sum}}\omega^{k\cdot t}\cdot a_{t}=a_{0}+\omega^{2k}a_{2}+\omega^{4k}a_{4}+...+\omega^{\left(n-2\right)k}a_{n-2}=a_{0}+\eta^{k}a_{2}+\eta^{2k}a_{4}+...+\eta^{\left(m-1\right)k}a_{n-2}=\sum_{t=0}^{m-1}\eta^{k\cdot t}\cdot a_{2t}=\sum_{t=0}^{m-1}\left[L\right]_{k,t}\cdot a_{2t}$
\end_inset

, which is precisely the 
\begin_inset Formula $k$
\end_inset

'th element in 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $\left(\begin{array}{c}
DFT_{\frac{n}{2}}\left(\begin{array}{c}
a_{0}\\
a_{2}\\
\vdots\\
a_{n-2}
\end{array}\right)\\
DFT_{\frac{n}{2}}\left(\begin{array}{c}
a_{0}\\
a_{2}\\
\vdots\\
a_{n-2}
\end{array}\right)
\end{array}\right)$
\end_inset

.
\end_layout

\begin_layout Itemize
\begin_inset Formula $\underset{odd\, t's}{\underbrace{\sum}}\omega^{k\cdot t}\cdot a_{t}=\omega^{k}a_{1}+\omega^{3k}a_{3}+\omega^{5k}a_{5}+...+\omega^{\left(n-1\right)k}a_{n-1}=\omega^{k}\left(a_{1}+\omega^{2k}a_{3}+\omega^{4k}a_{5}+...+\omega^{\left(n-2\right)k}a_{n-1}\right)=\omega^{k}\left(a_{1}+\eta^{k}a_{3}+\eta^{2k}a_{5}+...+\eta^{\left(m-1\right)k}a_{n-1}\right)=\omega^{k}\left(\sum_{t=0}^{m-1}\eta^{k\cdot t}\cdot a_{2t+1}\right)=\omega^{k}\sum_{t=0}^{m-1}\left[L\right]_{k,t}\cdot a_{2t+1}$
\end_inset

 which is precisely the 
\begin_inset Formula $k$
\end_inset

'th element in 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $\left(\begin{array}{c}
\left(w_{n}\right)^{0}\\
\left(w_{n}\right)^{1}\\
\vdots\\
\left(w_{n}\right)^{n-1}
\end{array}\right)\cdot\left(\begin{array}{c}
DFT_{\frac{n}{2}}\left(\begin{array}{c}
a_{1}\\
a_{3}\\
\vdots\\
a_{n-1}
\end{array}\right)\\
DFT_{\frac{n}{2}}\left(\begin{array}{c}
a_{1}\\
a_{3}\\
\vdots\\
a_{n-1}
\end{array}\right)
\end{array}\right)$
\end_inset

.
\end_layout

\begin_layout Standard
Finally we have that the 
\begin_inset Formula $k$
\end_inset

'th element in the left side of the equation equals the 
\begin_inset Formula $k$
\end_inset

'th element in the right side of the equation.
\end_layout

\begin_layout Paragraph
Case 2 - 
\begin_inset Formula $m\leq k\leq2m-1$
\end_inset

 (
\begin_inset Formula $\frac{n}{2}\leq k\leq n-1$
\end_inset

):
\end_layout

\begin_layout Standard

\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none
Again, 
\begin_inset Formula $DFT_{n}\left(\begin{array}{c}
a_{0}\\
a_{1}\\
\vdots\\
a_{n-1}
\end{array}\right)$
\end_inset

 in the 
\begin_inset Formula $k$
\end_inset

'th element is given by 
\begin_inset Formula $\sum_{t=0}^{n-1}\left[M\right]_{k,t}\cdot a_{t}=\sum_{t=0}^{n-1}\omega^{k\cdot t}\cdot a_{t}$
\end_inset

.
\end_layout

\begin_layout Standard
Now we can write 
\begin_inset Formula $k=m+s$
\end_inset

 and 
\begin_inset Formula $0\leq s\leq m-1$
\end_inset

.
 We notice that 
\begin_inset Formula $\eta^{k}=\eta^{m+s}=\eta^{m}\cdot\eta^{s}=1\cdot\eta^{s}=\eta^{s}$
\end_inset

.
\end_layout

\begin_layout Standard
We can now repeat a similar analysis as in case 1 and reach the conclusion
 that the 
\begin_inset Formula $k$
\end_inset

'th element in the left side of the equation equals the 
\begin_inset Formula $\left(m+s\right)$
\end_inset

'th (or, 
\begin_inset Formula $k$
\end_inset

'th) element in the right side of the equation.
\end_layout

\begin_layout Standard
Thus we complete the proof.
 
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\begin_layout Chapter
Cryptography
\end_layout

\begin_layout Section
Foundations
\end_layout

\begin_layout Subsection
Survey of group theory
\end_layout

\begin_layout Definition
Group.
\end_layout

\begin_layout Definition
A non-empty group 
\begin_inset Formula $G$
\end_inset

 with some operation 
\begin_inset Formula $\circ$
\end_inset

, such that 
\begin_inset Formula $\circ:G\times G\rightarrow G$
\end_inset

, holds the following properties:
\end_layout

\begin_layout Enumerate
Associativity: 
\begin_inset Formula $\forall a,b,c\in G:a\circ\left(b\circ c\right)=\left(a\circ b\right)\circ c$
\end_inset

.
\end_layout

\begin_layout Enumerate
Existence of 
\emph on
identity element
\emph default
 
\begin_inset Formula $e$
\end_inset

: There exists 
\begin_inset Formula $e\in G$
\end_inset

 such that for every 
\begin_inset Formula $a\in G$
\end_inset

 it holds 
\begin_inset Formula $a\circ e=e\circ a=a$
\end_inset

.
\end_layout

\begin_layout Enumerate
Existence of 
\emph on
inverse element: F
\emph default
or every 
\begin_inset Formula $a\in G$
\end_inset

 there exists 
\begin_inset Formula $a^{-1}\in G$
\end_inset

 such that 
\begin_inset Formula $a\circ a^{-1}=a^{-1}\circ a=e$
\end_inset

.
\end_layout

\begin_layout Remark
We denote a group 
\begin_inset Formula $G$
\end_inset

 with operation 
\begin_inset Formula $\circ$
\end_inset

 as a tuple 
\begin_inset Formula $\left(G,\circ\right)$
\end_inset

.
\end_layout

\begin_layout Lemma
The identity element of 
\begin_inset Formula $G$
\end_inset

 is unique.
\end_layout

\begin_layout Proof
Assume there are two identity elements 
\begin_inset Formula $a$
\end_inset

 and 
\begin_inset Formula $b$
\end_inset

.
\end_layout

\begin_layout Proof
Because 
\begin_inset Formula $a$
\end_inset

 is an identity element we have 
\begin_inset Formula $a\circ b=b$
\end_inset

.
\end_layout

\begin_layout Proof
Because 
\begin_inset Formula $b$
\end_inset

 is an identity element we have 
\begin_inset Formula $a\circ b=a$
\end_inset

.
\end_layout

\begin_layout Proof
Thus we conclude 
\begin_inset Formula $a=b$
\end_inset

, which means the identity element is unique.
\end_layout

\begin_layout Lemma
For each 
\begin_inset Formula $a\in G$
\end_inset

 there is a unique inverse element 
\begin_inset Formula $a^{-1}\in G$
\end_inset

.
\end_layout

\begin_layout Proof
Assume 
\begin_inset Formula $a$
\end_inset

 has two inverse elements 
\begin_inset Formula $b,c$
\end_inset

.
\end_layout

\begin_layout Proof
Because 
\begin_inset Formula $c$
\end_inset

 is an inverse element of 
\begin_inset Formula $a$
\end_inset

: 
\begin_inset Formula $b\circ\left(a\circ c\right)=b\circ e=b$
\end_inset

.
\end_layout

\begin_layout Proof
Because 
\begin_inset Formula $b$
\end_inset

 is an inverse element of 
\begin_inset Formula $a$
\end_inset

: 
\begin_inset Formula $b\circ\left(a\circ c\right)=\left(b\circ a\right)\circ c=e\circ c=c$
\end_inset

.
\end_layout

\begin_layout Proof
Thus we conclude 
\begin_inset Formula $b=c$
\end_inset

, which means the inverse element is unique.
\end_layout

\begin_layout Standard
[TODO - more definitions.
 such as sub groups, 
\begin_inset Formula $ord_{G}\left(a\right)$
\end_inset

, cyclic group, etc.]
\end_layout

\begin_layout Theorem
Lagrange's theorem.
\begin_inset CommandInset label
LatexCommand label
name "thm:Lagrange's-theorem."

\end_inset


\end_layout

\begin_layout Theorem
Let 
\begin_inset Formula $G$
\end_inset

 be a finite group and 
\begin_inset Formula $H\subseteq G$
\end_inset

 a subgroup, then 
\begin_inset Formula $\left|H\right|$
\end_inset

 divides 
\begin_inset Formula $\left|G\right|$
\end_inset

 (
\begin_inset Formula $\left|G\right|=0\mod\left|H\right|$
\end_inset

).
\end_layout

\begin_layout Proof
For each 
\begin_inset Formula $a\in G$
\end_inset

 we denote 
\begin_inset Formula $aH=\left\{ a\cdot h|h\in H\right\} $
\end_inset

.
\end_layout

\begin_layout Proof
We will see that for every 
\begin_inset Formula $a,b\in G$
\end_inset

 either 
\begin_inset Formula $aH=bH$
\end_inset

 or 
\begin_inset Formula $aH\cap bH=\emptyset$
\end_inset

.
\end_layout

\begin_layout Proof
Let's assume there is 
\begin_inset Formula $x\in aH\cap bH$
\end_inset

.
 It means that there are 
\begin_inset Formula $h_{1},h_{2}\in H$
\end_inset

 such that 
\begin_inset Formula $x=a\cdot h_{1}=b\cdot h_{2}$
\end_inset

.
 Thus 
\begin_inset Formula $b^{-1}\cdot a=h_{2}\cdot h_{1}^{-1}$
\end_inset

 which means that 
\begin_inset Formula $b^{-1}\cdot a\in H$
\end_inset

.
\end_layout

\begin_layout Proof
We will now show that 
\begin_inset Formula $aH\subseteq bH$
\end_inset

 and 
\begin_inset Formula $bH\subseteq aH$
\end_inset

, and conclude that 
\begin_inset Formula $aH=bH$
\end_inset

.
\end_layout

\begin_layout Proof
We will show 
\begin_inset Formula $aH\subseteq bH$
\end_inset

, and the other direction is analogous.
\end_layout

\begin_layout Proof
Let 
\begin_inset Formula $x=bh\in bH$
\end_inset

.
 We can write 
\begin_inset Formula $x=b\underset{e}{\underbrace{\left(\left(b^{-1}a\right)\left(b^{-1}a\right)^{-1}\right)}}h=b\left(b^{-1}a\right)\left(b^{-1}a\right)^{-1}h=a\left(b^{-1}a\right)^{-1}h$
\end_inset

.
\end_layout

\begin_layout Proof
We have seen that 
\begin_inset Formula $b^{-1}a\in H$
\end_inset

, and thus also 
\begin_inset Formula $\left(b^{-1}a\right)^{-1}\in H$
\end_inset

 and 
\begin_inset Formula $\left(b^{-1}a\right)^{-1}h\in H$
\end_inset

.
 Thus we conclude 
\begin_inset Formula $x=a\left(b^{-1}a\right)^{-1}h\in aH$
\end_inset

.
\end_layout

\begin_layout Proof
We have seen that if 
\begin_inset Formula $x\in bH$
\end_inset

 then 
\begin_inset Formula $x\in aH$
\end_inset

, which means 
\begin_inset Formula $bH\subseteq aH$
\end_inset

, as needed (along with the opposite direction of 
\begin_inset Formula $aH\subseteq bH$
\end_inset

) to conclude that 
\begin_inset Formula $aH=bH$
\end_inset

.
\end_layout

\begin_layout Proof
Now we will see that for every 
\begin_inset Formula $a,b\in G$
\end_inset

: 
\begin_inset Formula $\left|aH\right|=\left|bH\right|$
\end_inset

.
 Obviously it's true if 
\begin_inset Formula $aH=bH$
\end_inset

, so we assume that 
\begin_inset Formula $aH\cap bH=\emptyset$
\end_inset

.
 We will define a bijection 
\begin_inset Formula $\varphi:aH\rightarrow bH$
\end_inset

.
 If we show that 
\begin_inset Formula $\varphi$
\end_inset

 is indeed a bijection, then we can conclude 
\begin_inset Formula $\left|aH\right|=\left|bH\right|$
\end_inset

.
\end_layout

\begin_layout Proof
We define 
\begin_inset Formula $\varphi\left(x\right)=b\cdot a^{-1}x$
\end_inset

.
\end_layout

\begin_layout Proof
For 
\begin_inset Formula $x=a\cdot h\in aH$
\end_inset

 we have 
\begin_inset Formula $\varphi\left(x\right)=b\cdot a^{-1}a\cdot h=b\cdot h\in bH$
\end_inset

.
\end_layout

\begin_layout Proof
First we show that 
\begin_inset Formula $\varphi$
\end_inset

 is injective.
\end_layout

\begin_layout Proof
For some 
\begin_inset Formula $x,y$
\end_inset

 we have 
\begin_inset Formula $\varphi\left(x\right)=\varphi\left(y\right)$
\end_inset

 
\begin_inset Formula $\Leftrightarrow$
\end_inset

 
\begin_inset Formula $b\cdot a^{-1}x=b\cdot a^{-1}y$
\end_inset

 
\begin_inset Formula $\Leftrightarrow$
\end_inset

 
\begin_inset Formula $\left(b^{-1}\cdot a\right)\cdot b\cdot a^{-1}x=\left(b^{-1}\cdot a\right)\cdot b\cdot a^{-1}y$
\end_inset

 
\begin_inset Formula $\Leftrightarrow$
\end_inset

 
\begin_inset Formula $x=y$
\end_inset

.
 So 
\begin_inset Formula $\varphi$
\end_inset

 is indeed injection.
\end_layout

\begin_layout Proof
Now we will show that 
\begin_inset Formula $\varphi$
\end_inset

 is surjective.
\end_layout

\begin_layout Proof
Each 
\begin_inset Formula $y\in bH$
\end_inset

 has the form 
\begin_inset Formula $y=b\cdot h$
\end_inset

 which is exactly 
\begin_inset Formula $\varphi\left(x\right)$
\end_inset

 with 
\begin_inset Formula $x=a\cdot h\in aH$
\end_inset

.
 Thus 
\begin_inset Formula $\varphi$
\end_inset

 is surjective.
\end_layout

\begin_layout Proof
We have shown that 
\begin_inset Formula $\varphi$
\end_inset

 is indeed a bijection and we can conclude 
\begin_inset Formula $\left|aH\right|=\left|bH\right|$
\end_inset

.
\end_layout

\begin_layout Proof
Now we can conclude that there is a set of elements 
\begin_inset Formula $\left\{ a_{1},a_{2},...,a_{k}\right\} $
\end_inset

 in 
\begin_inset Formula $G$
\end_inset

 such that all the sets 
\begin_inset Formula $a_{1}H,a_{2}H,...,a_{k}H$
\end_inset

 are mutually disjoint, and such that for every 
\begin_inset Formula $b\in G$
\end_inset

 there is some 
\begin_inset Formula $a_{i}$
\end_inset

 for which 
\begin_inset Formula $bH=a_{i}H$
\end_inset

.
\end_layout

\begin_layout Proof
We would now like to see that 
\begin_inset Formula $G=\cup_{i=1}^{k}a_{i}H$
\end_inset

.
 Obviously 
\begin_inset Formula $\cup_{i=1}^{k}a_{i}H\subseteq G$
\end_inset

, and we will now show 
\begin_inset Formula $G\subseteq\cup_{i=1}^{k}a_{i}H$
\end_inset

.
\end_layout

\begin_layout Proof
We will show by negation.
 Assume there is some 
\begin_inset Formula $b\in G$
\end_inset

 such that 
\begin_inset Formula $b\notin a_{i}H$
\end_inset

 for any 
\begin_inset Formula $i$
\end_inset

.
 This means that 
\begin_inset Formula $bH\cap a_{i}H=\emptyset$
\end_inset

 for any 
\begin_inset Formula $i$
\end_inset

, which means that 
\begin_inset Formula $b$
\end_inset

 is in the set 
\begin_inset Formula $\left\{ a_{1},a_{2},...,a_{k}\right\} $
\end_inset

, thus 
\begin_inset Formula $b=a_{i}$
\end_inset

 for some 
\begin_inset Formula $i$
\end_inset

 and 
\begin_inset Formula $b\in a_{i}H$
\end_inset

, which is a contradiction.
\end_layout

\begin_layout Proof
Now we can conclude 
\begin_inset Formula $G=\cup_{i=1}^{k}a_{i}H$
\end_inset

.
 We have already seen that 
\begin_inset Formula $\left|a_{i}H\right|=\left|a_{j}H\right|$
\end_inset

 for any 
\begin_inset Formula $i,j$
\end_inset

, that all 
\begin_inset Formula $a_{i}H$
\end_inset

's are disjoint and that 
\begin_inset Formula $\left|a_{i}H\right|=\left|H\right|$
\end_inset

 (by the definition of 
\begin_inset Formula $a_{i}H$
\end_inset

).
 Thus 
\begin_inset Formula $G=k\cdot\left|H\right|$
\end_inset

, which means that 
\begin_inset Formula $\left|H\right|$
\end_inset

 divides 
\begin_inset Formula $\left|G\right|$
\end_inset

, as needed to complete the proof.
 
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\begin_layout Lemma
Euclid's lemma.
\begin_inset CommandInset label
LatexCommand label
name "lem:Euclid's-lemma."

\end_inset


\end_layout

\begin_layout Lemma
Let 
\begin_inset Formula $p$
\end_inset

 be a prime number and 
\begin_inset Formula $a,b\in\mathbb{N}$
\end_inset

.
 If 
\begin_inset Formula $p$
\end_inset

 divides 
\begin_inset Formula $a\cdot b$
\end_inset

 then 
\begin_inset Formula $p$
\end_inset

 also divides 
\begin_inset Formula $a$
\end_inset

 or 
\begin_inset Formula $b$
\end_inset

.
\end_layout

\begin_layout --Separator--

\end_layout

\begin_layout Standard

\end_layout

\begin_layout Lemma
\begin_inset Formula $\mathbb{Z}_{n}^{*}=\left\{ 1\leq a\leq n-1:gcd\left(a,n\right)=1\right\} $
\end_inset

.
 
\begin_inset Formula $\left(\mathbb{Z}_{n}^{*},\circ\right)$
\end_inset

, with 
\begin_inset Formula $\circ$
\end_inset

 as the modulu-
\begin_inset Formula $n$
\end_inset

 product operation is a group.
\begin_inset CommandInset label
LatexCommand label
name "lem:.z*p-prod-mod-n-is-a-group"

\end_inset


\end_layout

\begin_layout Proof
We prove the properties:
\end_layout

\begin_layout Itemize
Closure with respect to 
\begin_inset Formula $\circ$
\end_inset

 - the modulu-
\begin_inset Formula $n$
\end_inset

 product operation.
 Let 
\begin_inset Formula $a,b\in\mathbb{Z}_{n}^{*}$
\end_inset

, we will show that 
\begin_inset Formula $a\circ b\in\mathbb{Z}_{n}^{*}$
\end_inset

.
 We need to show that if 
\begin_inset Formula $gcd\left(a,n\right)=1$
\end_inset

 and 
\begin_inset Formula $gcd\left(b,n\right)=1$
\end_inset

 then also 
\begin_inset Formula $gcd\left(a\circ b,n\right)=1$
\end_inset

.
 We prove by negation.
 Assume 
\begin_inset Formula $gcd\left(a\circ b,n\right)>1$
\end_inset

, then there is some prime number 
\begin_inset Formula $p$
\end_inset

 such that it divides both 
\begin_inset Formula $a\circ b$
\end_inset

 and 
\begin_inset Formula $n$
\end_inset

.
 Now, from lemma 
\begin_inset CommandInset ref
LatexCommand ref
reference "lem:Euclid's-lemma."

\end_inset

, either one of the following two options hold:
\end_layout

\begin_deeper
\begin_layout Enumerate
\begin_inset Formula $p$
\end_inset

 divides both 
\begin_inset Formula $n$
\end_inset

 and 
\begin_inset Formula $a$
\end_inset

, and so 
\begin_inset Formula $gcd\left(a,n\right)>1$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $p$
\end_inset

 divides both 
\begin_inset Formula $n$
\end_inset

 and 
\begin_inset Formula $b$
\end_inset

, and so 
\begin_inset Formula $gcd\left(b,n\right)>1$
\end_inset

.
\end_layout

\end_deeper
\begin_layout Itemize
Either one of the options is a contradiction, so we conclude 
\begin_inset Formula $gcd\left(a\circ b,n\right)=1$
\end_inset

.
\end_layout

\begin_layout Itemize
Associativity - Follows immediately from the properties of the modulu-
\begin_inset Formula $n$
\end_inset

 product operation.
\end_layout

\begin_layout Itemize
Existence of 
\emph on
identity element
\emph default
 
\begin_inset Formula $e$
\end_inset

: 
\begin_inset Formula $e=1\in\mathbb{Z}_{n}^{*}$
\end_inset

.
\end_layout

\begin_layout Itemize
Existence of 
\emph on
inverse element: 
\emph default
From corollary 
\begin_inset CommandInset ref
LatexCommand ref
reference "cor:corollary-from-euclids-extended"

\end_inset

 we can conclude that there is 
\begin_inset Formula $x$
\end_inset

 such that 
\begin_inset Formula $x\cdot a+y\cdot n=1$
\end_inset

, or 
\begin_inset Formula $x\cdot a=1\mod n$
\end_inset

.
 We define 
\begin_inset Formula $b=x\mod n$
\end_inset

.
 Obviously 
\begin_inset Formula $0\leq b\leq n-1$
\end_inset

 and 
\begin_inset Formula $b\cdot a=1\mod n$
\end_inset

.
 Now we just need to show that 
\begin_inset Formula $b\in\mathbb{Z}_{p}^{*}$
\end_inset

, or that 
\begin_inset Formula $gcd\left(b,n\right)=1$
\end_inset

.
 We prove this by negation.
 Assume 
\begin_inset Formula $gcd\left(b,n\right)>1$
\end_inset

, then there is some prime number 
\begin_inset Formula $p$
\end_inset

 that divides both 
\begin_inset Formula $b$
\end_inset

 and 
\begin_inset Formula $n$
\end_inset

.
 This also means that 
\begin_inset Formula $p$
\end_inset

 divides 
\begin_inset Formula $x$
\end_inset

.
 Finally we conclude that 
\begin_inset Formula $p$
\end_inset

 also divides 
\begin_inset Formula $x\cdot a+y\cdot n$
\end_inset

.
 But 
\begin_inset Formula $x\cdot a+y\cdot n=1$
\end_inset

, which means that 
\begin_inset Formula $p$
\end_inset

 divides 
\begin_inset Formula $1$
\end_inset

.
 But this is impossible.
 So we conclude that indeed 
\begin_inset Formula $gcd\left(b,n\right)=1$
\end_inset

 and thus 
\begin_inset Formula $b\cdot a=1\mod n$
\end_inset

, and 
\begin_inset Formula $b$
\end_inset

 is the inverse element of 
\begin_inset Formula $a$
\end_inset

.
\end_layout

\begin_layout Definition
For a prime number 
\begin_inset Formula $p\in\mathbb{N}$
\end_inset

, 
\begin_inset Formula $\mathbb{Z}_{p}^{*}$
\end_inset

 is the product modulu group of the field 
\begin_inset Formula $\mathbb{F}_{p}\backslash\left\{ 0\right\} $
\end_inset

.
 Remember that 
\begin_inset Formula $\mathbb{F}_{n}=\left\{ 0,1,...,n-1\right\} $
\end_inset

.
\end_layout

\begin_layout Definition
We define 
\begin_inset Formula $\mathbb{Z}_{p}^{*}=\left(\mathbb{F}_{p}\backslash\left\{ 0\right\} ,\circ\right)$
\end_inset

, with 
\begin_inset Formula $\circ$
\end_inset

 as the modulu-
\begin_inset Formula $p$
\end_inset

 product operation.
 Obviously 
\begin_inset Formula $\mathbb{Z}_{p}^{*}=\left\{ 1,2,...,p-1\right\} $
\end_inset

and 
\begin_inset Formula $\left|\mathbb{Z}_{p}^{*}\right|=p-1$
\end_inset

.
 Notice that this definition coincides with the group defined in lemma 
\begin_inset CommandInset ref
LatexCommand ref
reference "lem:.z*p-prod-mod-n-is-a-group"

\end_inset

 for a prime number.
\end_layout

\begin_layout Corollary
Fermat's little theorem.
\end_layout

\begin_layout Corollary
Let 
\begin_inset Formula $p$
\end_inset

 be a prime number and 
\begin_inset Formula $a\in\mathbb{N}$
\end_inset

 which does not divide by 
\begin_inset Formula $p$
\end_inset

; then 
\begin_inset Formula $p$
\end_inset

 devides 
\begin_inset Formula $a^{p-1}-1$
\end_inset

: 
\begin_inset Formula $a^{p-1}-1=0\mod p$
\end_inset

.
\end_layout

\begin_layout Proof
We need to show that 
\begin_inset Formula $a^{p-1}-1=0\mod p$
\end_inset

, or equivalently 
\begin_inset Formula $a^{p-1}=1\mod p$
\end_inset

.
 We notice that by the properties of modular product
\begin_inset Foot
status collapsed

\begin_layout Plain Layout
Suppose we have 
\begin_inset Formula $p$
\end_inset

 and 
\begin_inset Formula $n>p$
\end_inset

, then we can write 
\begin_inset Formula $n=k\cdot p+r$
\end_inset

 for some 
\begin_inset Formula $k$
\end_inset

 and 
\begin_inset Formula $0\leq r<p$
\end_inset

, or 
\begin_inset Formula $n\mod p=r$
\end_inset

.
 For some 
\begin_inset Formula $m\in\mathbb{N}$
\end_inset

: 
\begin_inset Formula $n^{m}=\left(k\cdot p+r\right)^{m}=\sum_{i=0}^{m}\left(\begin{array}{c}
m\\
i
\end{array}\right)\left(k\cdot p\right)^{i}\cdot r^{m-i}$
\end_inset

, for any 
\begin_inset Formula $i\neq0$
\end_inset

 we have 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $\left(k\cdot p\right)^{i}=0\mod p$
\end_inset

, and for 
\begin_inset Formula $i=0$
\end_inset

 we have 
\begin_inset Formula $\left(k\cdot p\right)^{i}=1\mod p$
\end_inset

, thus 
\family default
\series default
\shape default
\size default
\emph default
\bar default
\strikeout default
\uuline default
\uwave default
\noun default
\color inherit

\begin_inset Formula $n^{m}=r^{m}\mod p=\left(n\mod p\right)^{m}$
\end_inset

.
\end_layout

\end_inset

, this is equivalent to showing 
\begin_inset Formula $\left(a\mod p\right)^{p-1}=1\mod p$
\end_inset

.
 We notice that 
\begin_inset Formula $a\mod p\in\mathbb{Z}_{p}^{*}$
\end_inset

 (becaseu 
\begin_inset Formula $a$
\end_inset

 does not divide by 
\begin_inset Formula $p$
\end_inset

), so it's actually enough to show that for any 
\begin_inset Formula $b\in\mathbb{Z}_{p}^{*}$
\end_inset

 we have 
\begin_inset Formula $b^{p-1}=1$
\end_inset

 (in 
\begin_inset Formula $\mathbb{Z}_{p}^{*}$
\end_inset

).
\end_layout

\begin_layout Proof
We denote 
\begin_inset Formula $m=ord_{\mathbb{Z}_{p}^{*}}\left(b\right)=\left|\left\langle b\right\rangle \right|$
\end_inset

 (the order of 
\begin_inset Formula $b$
\end_inset

 in 
\begin_inset Formula $\mathbb{Z}_{p}^{*}$
\end_inset

, which means 
\begin_inset Formula $b^{m}=e$
\end_inset

).
 
\begin_inset Formula $\left\langle b\right\rangle $
\end_inset

 is a subgroup of 
\begin_inset Formula $\mathbb{Z}_{p}^{*}$
\end_inset

, so by theorem 
\begin_inset CommandInset ref
LatexCommand ref
reference "thm:Lagrange's-theorem."

\end_inset

 we know that 
\begin_inset Formula $m$
\end_inset

 devides 
\begin_inset Formula $\left|\mathbb{Z}_{p}^{*}\right|=p-1$
\end_inset

.
 In other words, there is some 
\begin_inset Formula $k\in\mathbb{N}$
\end_inset

 such that 
\begin_inset Formula $p-1=k\cdot m$
\end_inset

.
 Now we can conclude 
\begin_inset Formula $b^{p-1}=b^{k\cdot m}=\left(b^{m}\right)^{k}=e^{k}=e=1$
\end_inset

, as needed to complete the proof.
\end_layout

\begin_layout Lemma
For every finite group 
\begin_inset Formula $G$
\end_inset

 and 
\begin_inset Formula $a\in G$
\end_inset

 it holds that 
\begin_inset Formula $a^{\left|G\right|}=e$
\end_inset

 (with 
\begin_inset Formula $e$
\end_inset

 as the identity element in 
\begin_inset Formula $G$
\end_inset

).
\begin_inset CommandInset label
LatexCommand label
name "lem:For-every-finite"

\end_inset


\end_layout

\begin_layout Proof
Let's consider the cyclic group formed by 
\begin_inset Formula $a$
\end_inset

: 
\begin_inset Formula $\left\langle a\right\rangle $
\end_inset

.
 We denote 
\begin_inset Formula $m=\left|\left\langle a\right\rangle \right|$
\end_inset

, and we know that also 
\begin_inset Formula $m=ord_{G}\left(a\right)$
\end_inset

, which means that 
\begin_inset Formula $a^{m}=e$
\end_inset

.
 But 
\begin_inset Formula $\left|G\right|\geq m$
\end_inset

, thus also 
\begin_inset Formula $a^{\left|G\right|}=e$
\end_inset

.
\end_layout

\begin_layout Definition
Euler's function: 
\begin_inset Formula $\varphi\left(n\right)=\left|\mathbb{Z}_{n}^{*}\right|$
\end_inset

.
 We notice that if 
\begin_inset Formula $p$
\end_inset

 is prime, then 
\begin_inset Formula $\varphi\left(p\right)=p-1$
\end_inset

.
\end_layout

\begin_layout Theorem
Euler's theorem.
\end_layout

\begin_layout Theorem
Let 
\begin_inset Formula $n\in\mathbb{N}$
\end_inset

 and 
\begin_inset Formula $a$
\end_inset

 such that 
\begin_inset Formula $gcd\left(a,n\right)=1$
\end_inset

, then 
\begin_inset Formula $a^{\varphi\left(n\right)}=1$
\end_inset

.
\end_layout

\begin_layout Proof
It's enough to show that for 
\begin_inset Formula $a\in\mathbb{Z}_{n}^{*}$
\end_inset

 then 
\begin_inset Formula $a^{\varphi\left(n\right)}=1$
\end_inset

 in 
\begin_inset Formula $\mathbb{Z}_{n}^{*}$
\end_inset

.
 We recall 
\begin_inset Formula $\varphi\left(n\right)=\left|\mathbb{Z}_{n}^{*}\right|$
\end_inset

, so the proof follows directly from lemma 
\begin_inset CommandInset ref
LatexCommand ref
reference "lem:For-every-finite"

\end_inset

.
\end_layout

\begin_layout Subsection
Greatest common divisor (GCD)
\end_layout

\begin_layout Definition
Greatest Common Divisor.
\end_layout

\begin_layout Definition
Let 
\begin_inset Formula $a,b\in\mathbb{N}$
\end_inset

 such that 
\begin_inset Formula $a\geq b$
\end_inset

.
 The GCD of 
\begin_inset Formula $a$
\end_inset

 and 
\begin_inset Formula $b$
\end_inset

 is the largest 
\begin_inset Formula $d\in\mathbb{N}$
\end_inset

 (
\begin_inset Formula $d\geq1$
\end_inset

) such that 
\begin_inset Formula $d$
\end_inset

 divides both 
\begin_inset Formula $a$
\end_inset

 and 
\begin_inset Formula $b$
\end_inset

 without a remainder.
\end_layout

\begin_layout Definition
\begin_inset Formula $gcd\left(a,b\right)=\max\left\{ d\in\mathbb{N},d\geq1:a=0\mod d,b=0\mod d\right\} $
\end_inset


\end_layout

\begin_layout --Separator--

\end_layout

\begin_layout Theorem
Fundamental theorem of arithmetic.
\begin_inset CommandInset label
LatexCommand label
name "thm:Fundamental-theorem-of-arithm"

\end_inset


\end_layout

\begin_layout Theorem
Every 
\begin_inset Formula $n\in\mathbb{N}$
\end_inset

 (
\begin_inset Formula $n>1$
\end_inset

) can be written as a product of prime numbers.
 The primes involved in the product are unique.
\end_layout

\begin_layout Theorem
\begin_inset Formula $n=p_{1}^{r_{1}}\cdot p_{2}^{r_{2}}\cdot...\cdot p_{k}^{r_{k}}=\prod_{i=1}^{k}p_{i}^{r_{i}}$
\end_inset

, where each 
\begin_inset Formula $p_{i}$
\end_inset

 is a prime number and each 
\begin_inset Formula $e_{i}\in\mathbb{N}\cup\left\{ 0\right\} $
\end_inset

.
\end_layout

\begin_layout Definition
Greatest Common Divisor (alternative).
\end_layout

\begin_layout Definition
Let 
\begin_inset Formula $a,b\in\mathbb{N}$
\end_inset

 such that 
\begin_inset Formula $a\geq b>1$
\end_inset

.
\end_layout

\begin_layout Definition
By theorem 
\begin_inset CommandInset ref
LatexCommand ref
reference "thm:Fundamental-theorem-of-arithm"

\end_inset

 we can write:
\end_layout

\begin_layout Definition
\begin_inset Formula $a=p_{1}^{e_{1}}\cdot p_{2}^{e_{2}}\cdot...\cdot p_{k}^{e_{k}}$
\end_inset


\end_layout

\begin_layout Definition
\begin_inset Formula $b=p_{1}^{f_{1}}\cdot p_{2}^{f_{2}}\cdot...\cdot p_{k}^{f_{k}}$
\end_inset


\end_layout

\begin_layout Definition
Where 
\begin_inset Formula $\left\{ p_{i}\right\} _{i=1}^{k}$
\end_inset

 is the set of prime numbers which devide both 
\begin_inset Formula $a$
\end_inset

 and 
\begin_inset Formula $b$
\end_inset

 (remember 
\begin_inset Formula $e_{i}$
\end_inset

 and 
\begin_inset Formula $f_{i}$
\end_inset

 can be zero).
\end_layout

\begin_layout Definition
Then: 
\begin_inset Formula $gcd\left(a,b\right)=p_{1}^{\min\left\{ e_{1},f_{1}\right\} }\cdot p_{2}^{\min\left\{ e_{2},f_{2}\right\} }\cdot...\cdot p_{k}^{\min\left\{ e_{k},f_{k}\right\} }=\prod_{i=1}^{k}p_{i}^{\min\left\{ e_{i},f_{i}\right\} }$
\end_inset

.
\end_layout

\begin_layout Claim
Let 
\begin_inset Formula $a,b\in\mathbb{N}$
\end_inset

 such that 
\begin_inset Formula $a\geq b$
\end_inset

, and 
\begin_inset Formula $S=\left\{ a\cdot x+b\cdot y|x,y\in\mathbb{Z},a\cdot x+b\cdot y\geq1\right\} $
\end_inset

.
\begin_inset CommandInset label
LatexCommand label
name "Let-min-ax+by"

\end_inset


\end_layout

\begin_layout Claim
Then: 
\begin_inset Formula $gcd\left(a,b\right)=\min S$
\end_inset

.
\end_layout

\begin_layout Proof
We denote 
\begin_inset Formula $t=gcd\left(a,b\right)$
\end_inset

 and 
\begin_inset Formula $z=\min S$
\end_inset

.
 We want to prove 
\begin_inset Formula $t=z$
\end_inset

.
 For this we will show that 
\begin_inset Formula $t\leq z$
\end_inset

 and 
\begin_inset Formula $z\leq t$
\end_inset

 and conclude 
\begin_inset Formula $t=z$
\end_inset

.
\end_layout

\begin_layout Proof
\begin_inset Formula $t\leq z$
\end_inset

:
\end_layout

\begin_layout Proof
We will see that 
\begin_inset Formula $z\mod t=0$
\end_inset

, which means that 
\begin_inset Formula $t\leq z$
\end_inset

.
\end_layout

\begin_layout Proof
\begin_inset Formula $t=gcd\left(a,b\right)$
\end_inset

 so 
\begin_inset Formula $a\mod t=0$
\end_inset

 and 
\begin_inset Formula $b\mod t=0$
\end_inset

, which means that there exist some 
\begin_inset Formula $k_{1},k_{2}\in\mathbb{N}$
\end_inset

 such that 
\begin_inset Formula $t\cdot k_{1}=a$
\end_inset

 and 
\begin_inset Formula $t\cdot k_{2}=b$
\end_inset

.
\end_layout

\begin_layout Proof
Also, 
\begin_inset Formula $z\in S$
\end_inset

, which means there exist some 
\begin_inset Formula $x,y\in\mathbb{Z}$
\end_inset

 such that 
\begin_inset Formula $z=ax+by$
\end_inset

.
\end_layout

\begin_layout Proof
Now we can write 
\begin_inset Formula $z=ax+by=t\cdot k_{1}\cdot x+t\cdot k_{2}\cdot y=t\left(k_{1}x+k_{2}y\right)$
\end_inset

.
 Which means that 
\begin_inset Formula $z\mod t=0$
\end_inset

, as needed.
\end_layout

\begin_layout Proof
\begin_inset Formula $z\leq t$
\end_inset

:
\end_layout

\begin_layout Proof
We will show that 
\begin_inset Formula $z$
\end_inset

 divides both 
\begin_inset Formula $a$
\end_inset

 and 
\begin_inset Formula $b$
\end_inset

, but because 
\begin_inset Formula $t$
\end_inset

 is the maximal such divisor, we will conclude 
\begin_inset Formula $z\leq t$
\end_inset

.
\end_layout

\begin_layout Proof
We will prove for 
\begin_inset Formula $a$
\end_inset

, and the proof for 
\begin_inset Formula $b$
\end_inset

 is analogous.
\end_layout

\begin_layout Proof
First we will show that 
\begin_inset Formula $z\leq a$
\end_inset

.
 Assume it isn't, so 
\begin_inset Formula $z>a$
\end_inset

.
 We define 
\begin_inset Formula $z^{'}=1\cdot a+0\cdot b$
\end_inset

.
 By definition of 
\begin_inset Formula $S$
\end_inset

, 
\begin_inset Formula $z^{'}\in S$
\end_inset

, and obviously 
\begin_inset Formula $z^{'}=a$
\end_inset

.
 Thus 
\begin_inset Formula $z^{'}<z$
\end_inset

, but this contradicts the minimality of 
\begin_inset Formula $z$
\end_inset

 in 
\begin_inset Formula $S$
\end_inset

.
 So 
\begin_inset Formula $z\leq a$
\end_inset

.
\end_layout

\begin_layout Proof
Now we can write 
\begin_inset Formula $a=k\cdot z+r$
\end_inset

 with 
\begin_inset Formula $0\leq r\leq z-1$
\end_inset

.
 All that is left is to show that 
\begin_inset Formula $r=0$
\end_inset

 (and thus conclude that 
\begin_inset Formula $z$
\end_inset

 divides 
\begin_inset Formula $a$
\end_inset

).
\end_layout

\begin_layout Proof
\begin_inset Formula $z\in S$
\end_inset

 so it must be of the form 
\begin_inset Formula $z=ax+by$
\end_inset

, which means 
\begin_inset Formula $r=a-k\cdot z=a\left(1-x\right)-by$
\end_inset

.
 If 
\begin_inset Formula $r\geq1$
\end_inset

, then also 
\begin_inset Formula $r\in S$
\end_inset

 (it fits the structure of 
\begin_inset Formula $S$
\end_inset

), and from the minimality of 
\begin_inset Formula $z$
\end_inset

 in 
\begin_inset Formula $S$
\end_inset

 we conclude 
\begin_inset Formula $r\geq z$
\end_inset

.
 But 
\begin_inset Formula $r$
\end_inset

 was defined 
\begin_inset Formula $r\leq z-1$
\end_inset

, so we have a contradiction, and thus 
\begin_inset Formula $r=0$
\end_inset

, as needed.
\end_layout

\begin_layout Claim
Let 
\begin_inset Formula $a,b$
\end_inset

 such that 
\begin_inset Formula $a\geq b\geq0$
\end_inset

 and 
\begin_inset Formula $a\neq0$
\end_inset

, then 
\begin_inset Formula $gcd\left(a,b\right)=gcd\left(b,a\mod b\right)$
\end_inset

.
\begin_inset CommandInset label
LatexCommand label
name "Let-gcdab=gcdbamodb"

\end_inset


\end_layout

\begin_layout Proof
We denote 
\begin_inset Formula $d=gcd\left(a,b\right)$
\end_inset

 and 
\begin_inset Formula $d^{'}=gcd\left(b,a\mod b\right)$
\end_inset

.
 We will show that 
\begin_inset Formula $d=d^{'}$
\end_inset

 by showing 
\begin_inset Formula $d\geq d^{'}$
\end_inset

 and 
\begin_inset Formula $d^{'}\geq d$
\end_inset

.
\end_layout

\begin_layout Proof
\begin_inset Formula $d^{'}\geq d$
\end_inset

:
\end_layout

\begin_layout Proof
We will see that 
\begin_inset Formula $d$
\end_inset

 divides both 
\begin_inset Formula $b$
\end_inset

 and 
\begin_inset Formula $a\mod b$
\end_inset

, and conclude 
\begin_inset Formula $d^{'}\geq d$
\end_inset

.
\end_layout

\begin_layout Proof
\begin_inset Formula $d$
\end_inset

 divides 
\begin_inset Formula $a$
\end_inset

, so there exists some 
\begin_inset Formula $k_{1}$
\end_inset

 such that 
\begin_inset Formula $a=k_{1}d$
\end_inset

.
\end_layout

\begin_layout Proof
\begin_inset Formula $d$
\end_inset

 divides 
\begin_inset Formula $b$
\end_inset

, so there exists some 
\begin_inset Formula $k_{2}$
\end_inset

 such that 
\begin_inset Formula $b=k_{2}d$
\end_inset

.
\end_layout

\begin_layout Proof
There exist some 
\begin_inset Formula $k_{3},r\in\mathbb{N}$
\end_inset

 such that 
\begin_inset Formula $r=a\mod b=a-k_{3}b$
\end_inset

 and 
\begin_inset Formula $0\leq r\leq b-1$
\end_inset

.
 We can write 
\begin_inset Formula $r=k_{1}d-k_{3}k_{2}d=\left(k_{1}-k_{2}k_{3}\right)d=k_{4}d$
\end_inset

 (
\begin_inset Formula $k_{4}>0$
\end_inset

 because 
\begin_inset Formula $d,r>0$
\end_inset

), which means that 
\begin_inset Formula $d$
\end_inset

 divides 
\begin_inset Formula $a\mod b$
\end_inset

, as needed.
\end_layout

\begin_layout Proof
\begin_inset Formula $d\geq d^{'}$
\end_inset

:
\end_layout

\begin_layout Proof
We will see that 
\begin_inset Formula $d^{'}$
\end_inset

 divides both 
\begin_inset Formula $a$
\end_inset

 and 
\begin_inset Formula $b$
\end_inset

, and conclude 
\begin_inset Formula $d\geq d^{'}$
\end_inset

.
\end_layout

\begin_layout Proof
\begin_inset Formula $d^{'}$
\end_inset

 divides 
\begin_inset Formula $b$
\end_inset

, so there exists some 
\begin_inset Formula $k_{1}$
\end_inset

 such that 
\begin_inset Formula $b=k_{1}d^{'}$
\end_inset

.
\end_layout

\begin_layout Proof
\begin_inset Formula $d^{'}$
\end_inset

 divides 
\begin_inset Formula $a\mod b$
\end_inset

, so there exists some 
\begin_inset Formula $k_{2}$
\end_inset

 such that 
\begin_inset Formula $a\mod b=k_{2}d^{'}$
\end_inset

.
\end_layout

\begin_layout Proof
There exist some 
\begin_inset Formula $k_{3},r\in\mathbb{N}$
\end_inset

 such that 
\begin_inset Formula $r=a\mod b=a-k_{3}b$
\end_inset

 and 
\begin_inset Formula $0\leq r\leq b-1$
\end_inset

.
 We can write 
\begin_inset Formula $a=a\mod b+k_{3}b=k_{2}d^{'}+k_{3}k_{1}d^{'}=\left(k_{2}+k_{3}k_{1}\right)d^{'}=k_{4}d^{'}$
\end_inset

 (
\begin_inset Formula $k_{4}>0$
\end_inset

 because 
\begin_inset Formula $d^{'},a>0$
\end_inset

), which means that 
\begin_inset Formula $d^{'}$
\end_inset

 divides 
\begin_inset Formula $a$
\end_inset

, as needed.
\end_layout

\begin_layout Corollary
Let 
\begin_inset Formula $a,b\in\mathbb{N}$
\end_inset

 with 
\begin_inset Formula $gcd\left(a,b\right)=1$
\end_inset

, then there exist 
\begin_inset Formula $x,y$
\end_inset

 such that 
\begin_inset Formula $x\cdot a+y\cdot b=1$
\end_inset

.
\begin_inset CommandInset label
LatexCommand label
name "cor:corollary-from-euclids-extended"

\end_inset


\end_layout

\begin_layout Subsubsection
Euclid's algorithm for GCD
\end_layout

\begin_layout Paragraph
Input:
\end_layout

\begin_layout Standard
\begin_inset Formula $a,b\in\mathbb{N}$
\end_inset

 and 
\begin_inset Formula $a>b$
\end_inset

.
\end_layout

\begin_layout Paragraph
Output:
\end_layout

\begin_layout Standard
\begin_inset Formula $gcd\left(a,b\right)$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float algorithm
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

Euclid(a,b):
\end_layout

\begin_layout Plain Layout

  if b = 0:
\end_layout

\begin_layout Plain Layout

    return a
\end_layout

\begin_layout Plain Layout

  else:
\end_layout

\begin_layout Plain Layout

    return Euclid(b, a mod b)
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Euclid's algorithm for GCD
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
The correctness of the algorithm follows directly from claim 
\begin_inset CommandInset ref
LatexCommand ref
reference "Let-gcdab=gcdbamodb"

\end_inset

.
\end_layout

\begin_layout Subsubsection
Euclid's extended algorithm
\end_layout

\begin_layout Standard
By claim 
\begin_inset CommandInset ref
LatexCommand ref
reference "Let-min-ax+by"

\end_inset

 we know there are 
\begin_inset Formula $x,y$
\end_inset

 such that 
\begin_inset Formula $a\cdot x+b\cdot y=gcd\left(a,b\right)$
\end_inset

.
\end_layout

\begin_layout Paragraph
Input:
\end_layout

\begin_layout Standard
\begin_inset Formula $a,b\in\mathbb{N}$
\end_inset

 and 
\begin_inset Formula $a>b$
\end_inset

.
\end_layout

\begin_layout Paragraph
Output:
\end_layout

\begin_layout Standard
\begin_inset Formula $(g,x,y)$
\end_inset

 such that 
\begin_inset Formula $g=gcd\left(a,b\right)$
\end_inset

 and 
\begin_inset Formula $a\cdot x+b\cdot y=gcd\left(a,b\right)$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

Extended_Euclid(a,b):
\end_layout

\begin_layout Plain Layout

  if b = 0:
\end_layout

\begin_layout Plain Layout

    return (g, x, y) = (a, 1, 0)
\end_layout

\begin_layout Plain Layout

  else:
\end_layout

\begin_layout Plain Layout

    (g', x', y') = Extended_Euclid(b, a mod b)
\end_layout

\begin_layout Plain Layout

    return (g, x, y) = (g', y', x' - y' * floor(a/b))
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Euclid's extended algorithm for GCD
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Paragraph
Correctness:
\end_layout

\begin_layout Standard
We will prove the correctness of the recurssion.
\end_layout

\begin_layout Standard
Base: If 
\begin_inset Formula $b=0$
\end_inset

, then it obvious.
\end_layout

\begin_layout Standard
By the recurssion we know that 
\begin_inset Formula $g'=gcd\left(b,a\mod b\right)$
\end_inset

, but by claim 
\begin_inset CommandInset ref
LatexCommand ref
reference "Let-gcdab=gcdbamodb"

\end_inset

 
\begin_inset Formula $gcd\left(b,a\mod b\right)=gcd\left(a,b\right)$
\end_inset

, thus 
\begin_inset Formula $g=g^{'}$
\end_inset

 is correct.
\end_layout

\begin_layout Standard
Also, by the recurssion, 
\begin_inset Formula $x^{'}b+y^{'}\left(a\mod b\right)=g^{'}=g$
\end_inset

.
 We also know that 
\begin_inset Formula $a\mod b=a-k\cdot b$
\end_inset

 for some 
\begin_inset Formula $k$
\end_inset

.
 Notice that 
\begin_inset Formula $k=\left\lfloor \frac{a}{b}\right\rfloor $
\end_inset

 (by definition of remainder).
 So now we have 
\begin_inset Formula $g=x^{'}b+y^{'}\left(a-k\cdot b\right)=x^{'}b+y^{'}a-y^{'}\cdot k\cdot b=y^{'}a+\left(x^{'}-k\cdot y^{'}\right)b=y^{'}a+\left(x^{'}-\left\lfloor \frac{a}{b}\right\rfloor \cdot y^{'}\right)b$
\end_inset

, and indeed 
\begin_inset Formula $x=y^{'}$
\end_inset

 and 
\begin_inset Formula $y=x^{'}-\left\lfloor \frac{a}{b}\right\rfloor \cdot y^{'}$
\end_inset

, as needed.
 
\begin_inset Formula $\blacksquare$
\end_inset


\end_layout

\end_body
\end_document