Depth-first Search

INPUT: A connected graph $G=(V,E)$, $V=\{ v_1,\dots ,v_n\}$.
OUTPUT: A (depth-first) spanning tree $T$ of $G$.

( Step 1)

Initialize $T=(V_T,E_T)$: $V_T=\{ v_1\}$ and $E_T=\emptyset$. Set $current:=v_1$.

( Step 2)

Select the neighbour of $current$ with the lowest index which is not yet visited. If no such neighbour exist, continue to Step 3. If it does exist, say $v_i$, set $current:=v_i$ and return to Step 2.

( Step 3)

If $current\not= v_1$, then find the parent $v_j$ of $current$, and set $current=v_j$ (backtracking). Go to Step 2.

( Step 4)

If $current=v_1$, then stop.

Breadth-first Search

INPUT: A connected graph $G=(V,E)$, $V=\{ v_1,\dots ,v_n\}$.
OUTPUT: A (breadth-first) spanning tree $T$ of $G$.

( Step 1)

Initialize $T=(V_T,E_T)$: $V_T=\{ v_1\}$ and $E_T=\emptyset$. Insert $v_1$ in a queue $Q$.

( Step 2)

Set $current$ to be the vertex at the front of the queue $Q$, and delete this vertex from $Q$. Add all neighbours of $current$ that have not been visited to the rear of the queue, in order of increasing index. If no such neigbours exist, repeat Step 2.

( Step 3)

If $Q$ is empty, then stop.

Vertex set: $\{ a,b,c,d,e,f,g,h\}$.
Adjacency matrix:

$$\left[ \begin{array}{cccccccc} 0&1&1&1&0&0&0&0\\ 1&0&0&1&1&... ...0&0&0\\ 0&0&1&0&0&0&0&0\\ 0&0&0&1&1&0&0&0 \end{array}\right]$$

Merge sort:

INPUT: A list $L$ of $n$ unordered numbers
OUTPUT: A list $OL$ of the same numbers in increasing order.

( Step 1:)

Form a binary tree $T$ of height $t$, where $t=\lceil\log_2(n)\rceil$. Label its leaves with the elements of $L$. Label all intermediate nodes as unfinished, all leaves as finished.

( Step 2:)

Find an unfinished intermediate node $v$ with two finished children with lists $L_1$ and $L_2$:

( Step2a:)

Merge $L_1$ and $L_2$ into $L$: take the smallest of the first elements of $L_1$ and $L_2$, remove it from its list and put it at the end of $L$. Repeate this until $L_1$ and $L_2$ are empty.

( Step 2b:)

Assign $L$ to $v$, and label $v$ as finished.

Repeat this step until all nodes are finished.

( Step 3:)

Let $OL$ be the list assigned to the root.

A relation from set $A$ to set $B$ is a subset of $A\times B$.

Notation: Given a relation $R\subseteq A\times B$,

$$xRy \Leftrightarrow (x,y)\in R$$

A relation $R$ on a set $A$ is a relation from $A$ to $A$. Such a relation can have the following properties (universe of the quantifiers is $A$):

Reflexive:

$$\forall_{x}\, (x,x)\in R.$$

Symmetric:

$$\forall_{x}\forall_{y}\, (x,y)\in R\rightarrow (y,x)\in R.$$

Antisymmetric:

$$\forall_x\forall_y\, [(x,y)\in R\wedge (y,x)\in R] \rightarrow x=y$$

Transitive:

$$\forall_x\forall_y\forall_z [(x,y)\in R \wedge (y,z)\in R] \rightarrow (x,z)\in R$$

$A$	$xRy$ if:	refl.	sym.	antis.	trans.
people	$x$ is taller than $y$			X	X
reals	$x<y$			X	X
reals	$x\geq y$	X		X	X
integers	$x\vert y$	X		X	X
integers	$x+y$ is even	X	X		X
people	$x$ has the same age as $y$	X		X	X
people	$x$ has a parent in common with $y$	X		X
integers	$y=x^2$
sets	$x\subseteq y$	X		X	X
integers	$x$ and $y$ are
	relatively prime		X
integers	$x$ and $y$, divided by 5	X	X		X
	have the same remainder
bit strings	$x$ and $y$ have the same	X	X		X
of length 7	number of 1's
web pages	$x$ has a hyperlink to $y$

Partial order: a relation that is reflexive, antisymmetric and transitive.

Examples:

• The relation $R$ on $\mathbb{Z}$ where $xRy$ if $x\geq y$,
• The relation $R$ on the collection of alls sets where $xRy$ if $x\subseteq y$,
• The relation $R$ on $\mathbb{Z}$ where $xRy$ if $x\vert y$.

Equivalence relation: a relation that is reflexive, symmetric and transitive.

Examples:

• The relation $R$ on $\mathbb{Z}$ where $xRy$ if $x-y$ is divisible by 5.
• The relation $R$ on the set of all people where $xRy$ if $x$ and $y$ have the same age.

A relation $R$ on a set $A$ can be represented as a directed graph $G_R=(A,E)$ as follows:

The vertices of $G_R$ are the elements of $A$
The edge set $E=\{ (a,b)\in A\times A\vert aRb\}$.

A relation $R$ on a set $A=\{ a_1,a_2,\dots, a_n\}$ can be represented by an $n\times n$ relation matrix $A$ as follows:

$$A_{i,j}=\left\{ \begin{array}{ll} 1&\mbox{if $a_iRa_j$}\\ 0&\mbox{otherwise} \end{array}\right.$$

Note that the relation matrix of $R$ is the adjacency matrix of the directed graph representing $R$.