Design and Analysis

Algorithms
Dr. Metwally Rashad Lecture 7
2022
Table of Contents
1. Foundations
- The Role of Algorithms in Computing
- Design and Analysis algorithms
- Growth of Functions+ Recurrence
2. Sorting
- Heapsort
- Quicksort
- Sorting in Linear Time
3. Graph Algorithms
- Elementary Graph Algorithms
- Minimum Spanning Trees
4. Advanced Design and Analysis Techniques
- Dynamic Programming
- Greedy Algorithms
1/43
Graph Algorithms
- Graphs Terminology
- Representations of Graphs
- Graph Searching Algorithms
- Breadth-first Search
- Depth-first Search

2/43
 Graphs Terminology
• A graph is a structure that consists of a set of vertices and a set of
edges between pairs of vertices
F
• A graph is a pair (V, E), where
– V is a set of vertices D
– E is a set of pairs of vertices, called edges E

A
• Example: C
– V = {A, B, C, D, E, F}
– E = {(A,B), (B,C), (B,E), (C, D), (C,E), (E,F)}
B 3/43
 Graphs Terminology(cont.)
 Directed and Undirected Graph
• Directed Graph
u
– ordered pair of vertices (u,v)
– A graph with directed edges is called a directed v
graph or digraph

• Undirected Graph
– unordered pair of vertices (u,v) u
– A graph with undirected edges is an undirected
graph or simply a graph v
4/43
 Graphs Terminology(cont.)
 Weighted Graphs
• The edges in a graph may have values associated with them known
as their weights
• A graph with weighted edges is known as a weighted graph

5/43
 Graphs Terminology(cont.)
• End vertices (or endpoints) of an edge
– U and V are the endpoints of an edge “a”
• Edges incident on a vertex V
– a, d, and b are incident on vertex “V” a b
• Adjacent vertices
h j
– U and V are adjacent U d X Z
• Degree of a vertex
– X has degree 5 c e i
• Parallel edges W
– h and i are parallel edges
g
• Self-loop
– j is a self-loop
f
Y
6/43
 Graphs Terminology(cont.)
• A path is a sequence of vertices in which each
successive vertex is adjacent to its
predecessor V
a b
• In a simple path, the vertices and edges are P1
distinct except that the first and last vertex d
may be the same U X Z
P2 h
• Examples c e
– P1 = (V, X, Z) is a simple path
W g
– P2 = (U, W, X, Y, W, V) is a path that is
not simple f
Y
7/43
 Graphs Terminology(cont.)
• A cycle is a path in which the first and final
vertices are the same V
a b
• Simple cycle
d
– cycle such that all its vertices and edges U X Z
are distinct C2 h
c e C1
• Examples W g
– C1 = (V, X, Y, W, U, V) is a simple cycle
– C2 = (U, W, X, Y, W, V, U) is a cycle f
that is not simple Y
8/43
 Graphs Terminology(cont.)
• A subgraph S of a graph G is a graph Subgraph
such that
S
– The vertices of S are a subset of the
vertices of G
– The edges of S are a subset of the
edges of G

• A spanning subgraph of G is a Spanning subgraph

subgraph that contains all the vertices
of G

9/43
 Graphs Terminology(cont.)
• A graph is connected if there is a
path between every pair of
vertices
• A connected component of a
graph G is a maximal connected Connected graph Non connected graph
subgraph of G with two connected
components

• A tree is an undirected graph T

such that
– T is connected
– T has no cycles
Tree
10/43
 Representations of Graphs
 Two standard ways
a b a b c d
– Adjacency Lists. b a c

c d c d a b
d a c

1 2 1 2 3 4
a b
1 0 1 1 1
2 1 0 1 0
– Adjacency Matrix. c d 3 1 1 0 1
3 4
4 1 0 1 0 11/43
 Representations of Graphs(cont.)
 Adjacency List
• Consists of an array Adj of |V| lists.
• One list per vertex.
• For u  V, Adj[u] consists of all vertices adjacent to u.
a b a b c d
b c
If weighted, store weights also in
c d c d
adjacency lists.
d
a b a b c d
b a c
c d c d a b
d a c 12/43
 Representations of Graphs(cont.)
 Adjacency Matrix
• |V|  |V| matrix A.
• Number vertices from 1 to |V| in some arbitrary manner.
• A is then given by: 1 if (i, j )  E
A[i, j ]  aij  
0 otherwise

1 2 1 2 3 4 1 2
a b a b 1 2 3 4
1 0 1 1 1 1 0 1 1 1
2 0 0 1 0 2 1 0 1 0
c d4 3 0 0 0 1 c d 3 1 1 0 1
3 4 0 0 0 0 3 4 4 1 0 1 0
13/43
 Graph Searching Algorithms
• Searching a graph:
– Systematically follow the edges of a graph
to visit the vertices of the graph.

• Used to discover the structure of a graph.

• Standard graph searching algorithms.
– Breadth-first Search (BFS).
– Depth-first Search (DFS).
14/43
 Breadth-first Search (BFS)
 Input: Graph G = (V, E) is represented using adjacency lists, either directed or
undirected, and source vertex s  V.
 Output:
– Store the color of each vertex 𝑢 ∈ 𝑉 in the attribute 𝑢. 𝑐𝑜𝑙𝑜𝑟 and the predecessor
of 𝑢 in the attribute 𝑢. 
– If 𝑢 has no predecessor then 𝑢.  =NIL.
– 𝒖. 𝒅 holds the distance from the source 𝑠 to vertex 𝑢 computed by the algorithm.
– The algorithm also uses a first-in, first-out queue 𝑸
– A vertex is “discovered” if the first time it is encountered during the search.
– A vertex is “finished” if all vertices adjacent to it have been discovered.
15/43
BFS(𝑮, 𝒔)
1. for each vertex 𝑢 ∈ 𝐺. 𝑣 – {s} BFS
2 𝑢. 𝑐𝑜𝑙𝑜𝑟 = white
3 𝑢. 𝑑 = ∞
Algorithm
Q
4 𝑢.  = NIL
5 𝑠. 𝑐𝑜𝑙𝑜𝑟 = Gray White: undiscovered
6 𝑠. 𝑑 = 0 Gray: discovered
7 𝑠.  = NIL Black: finished
8 𝑄=∅
9 Enqueue (𝑄, 𝑠)
10 while 𝑄 ∅ 𝑄: a queue of discovered
11 𝑢 = Dequeue(𝑄) vertices
12 for each 𝑣 ∈ 𝐺. 𝐴𝑑𝑗[𝑢] 𝑣. 𝑐𝑜𝑙𝑜𝑟: color of 𝑣
13 if 𝑣. 𝑐𝑜𝑙𝑜𝑟 == WHITE 𝑣. 𝑑: distance from s to 𝑣
14 𝑣. 𝑐𝑜𝑙𝑜𝑟 = GRAY 𝑣. : predecessor of 𝑣
15 𝑣. 𝑑 = 𝑢. 𝑑 + 1
16 𝑣.  = 𝑢
15 Enqueue(𝑄, 𝑣)
18 𝑢. 𝑐𝑜𝑙𝑜𝑟= Black
16/43
 Breadth-first Search (BFS) (cont.)
 Example (BFS)
r s t u
 0  

   
v w x y

Q: s
0
17/43
 Breadth-first Search (BFS) (cont.)
 Example (BFS)
r s t u
1 0  

 1  
v w x y

Q: w r
1 1
18/43
 Breadth-first Search (BFS) (cont.)
 Example (BFS)
r s t u
1 0 2 

 1 2 
v w x y

Q: r t x
1 2 2
19/43
 Breadth-first Search (BFS) (cont.)
 Example (BFS)
r s t u
1 0 2 

2 1 2 
v w x y

Q: t x v
2 2 2
20/43
 Breadth-first Search (BFS) (cont.)
 Example (BFS)
r s t u
1 0 2 3

2 1 2 
v w x y

Q: x v u
2 2 3
21/43
 Breadth-first Search (BFS) (cont.)
 Example (BFS)
r s t u
1 0 2 3

2 1 2 3
v w x y

Q: v u y
2 3 3
22/43
 Breadth-first Search (BFS) (cont.)
 Example (BFS)
r s t u
1 0 2 3

2 1 2 3
v w x y

Q: u y
3 3
23/43
 Breadth-first Search (BFS) (cont.)
 Example (BFS)
r s t u
1 0 2 3

2 1 2 3
v w x y

Q: y
3
24/43
 Breadth-first Search (BFS) (cont.)
 Example (BFS)
r s t u
1 0 2 3

2 1 2 3
v w x y

Q: 
25/43
 Depth-first Search (DFS) (cont.)
 Input - G = (V, E) is represented using adjacency lists, directed or undirected.
- No source vertex given!
 Output
– 2 timestamps on each vertex Integers between 1 and 2|𝑉|.
• v.d = discovery time, when 𝑣 is first discovered (v turns from white to gray)
• v.f = finishing time, when the search finishes examining 𝑣’s adjacency list (v
turns from gray to black)
– 𝑣. = predecessor of v, such that v was discovered during the scan of u’s
adjacency list.
– Uses the same coloring scheme for vertices as BFS.
– If any undiscovered vertices remain, then one of them is chosen as a new source
and search is repeated from that source. 26/43
 Depth-first Search (DFS)(cont.)
DFS-Visit(𝒖)
DFS(𝑮) 1. 𝑢. 𝑐𝑜𝑙𝑜𝑟 = Gray  White vertex u has
1. for each vertex 𝑢  𝐺. 𝑉 been discovered
2. 𝑢. 𝑐𝑜𝑙𝑜𝑟 = 𝑤ℎ𝑖𝑡𝑒 2. 𝑡𝑖𝑚𝑒 = 𝑡𝑖𝑚𝑒 + 1
3. 𝑢. 𝑑 = time
3. u. = 𝑁𝐼𝐿
4. for each v  Adj[u]
4. 𝑡𝑖𝑚𝑒 = 0
5. if 𝑣. 𝑐𝑜𝑙𝑜𝑟 == White
5. for each vertex 𝑢  𝐺. 𝑉 6. 𝑣. = u
6. if 𝑢. 𝑐𝑜𝑙𝑜𝑟 == 𝑤ℎ𝑖𝑡𝑒 7. DFS-Visit(v)
7. 𝐷𝐹𝑆-𝑉𝑖𝑠𝑖𝑡(𝑢) 8. 𝑢. 𝑐𝑜𝑙𝑜𝑟 = Black  Blacken u; it is
finished.
9. 𝑡𝑖𝑚𝑒 = 𝑡𝑖𝑚𝑒 + 1
Uses a global timestamp time. 10. 𝑢. 𝑓= 𝑡𝑖𝑚𝑒 29/36
 Depth-first Search (DFS)(cont.)
 Example (DFS)
time u v w
1/

x y z

28/43
 Depth-first Search (DFS)(cont.)
 Example (DFS)
u v w
1/ 2/

x y z

29/43
 Depth-first Search (DFS)(cont.)
 Example (DFS)
u v w
1/ 2/

3/
x y z

30/43
 Depth-first Search (DFS)(cont.)
 Example (DFS)
u v w
1/ 2/

4/ 3/
x y z

31/43
 Depth-first Search (DFS)(cont.)
 Example (DFS)
u v w
1/ 2/

4/ 3/
x y z

32/43
 Depth-first Search (DFS)(cont.)
 Example (DFS)
u v w
1/ 2/

4/5 3/
x y z

33/43
 Depth-first Search (DFS)(cont.)
 Example (DFS)
u v w
1/ 2/

4/5 3/6
x y z

34/43
 Depth-first Search (DFS)(cont.)
 Example (DFS)
u v w
1/ 2/7

4/5 3/6
x y z

35/43
 Depth-first Search (DFS)(cont.)
 Example (DFS)
u v w
1/ 2/7

F B

4/5 3/6
x y z

36/43
 Depth-first Search (DFS)(cont.)
 Example (DFS)
u v w
1/8 2/7

F B

4/5 3/6
x y z

37/43
 Depth-first Search (DFS)(cont.)
 Example (DFS)
u v w
1/8 2/7 9/

F B

4/5 3/6
x y z

38/43
 Depth-first Search (DFS)(cont.)
 Example (DFS)
u v w
1/8 2/7 9/

F B C

4/5 3/6
x y z

39/43
 Depth-first Search (DFS)(cont.)
 Example (DFS)
u v w
1/8 2/7 9/

F B C

4/5 3/6 10/

x y z

40/43
 Depth-first Search (DFS)(cont.)
 Example (DFS)
u v w
1/8 2/7 9/

F B C

4/5 3/6 10/ B

x y z

41/43
 Depth-first Search (DFS)(cont.)
 Example (DFS)
u v w
1/8 2/7 9/

F B C

4/5 3/6 10/11 B

x y z

42/43
 Depth-first Search (DFS)(cont.)
 Example (DFS)
u v w
1/8 2/7 9/12

F B C

4/5 3/6 10/11 B

x y z

43/43