Algorithms Analysis & Design - Lecture 7

Introduction to the Design and Analysis of Algorithms

1. Algorithms
By Mohamed Gamal
© Mohamed Gamal 2024

2. Exhaustive Search (Brute-Force)

3. –Uninformed (blind) strategies use only the information available in the problem definition.
–These strategies order nodes without using any domain specific information (Blind).
–Contrary to Informed (heuristic) search techniques which might have additional information.
• Breadth-first search (BFS)
• Depth-first search (DFS)
• Depth-limited search (DLS)
• Iterative deepening search (IDS)
• …
• etc.
Unguided/Blind Search
Uninformed (Blind) Search Strategies

4. Tree Basic Terminology
»Root: no parent.
»Leaf: no child.
»Height: distance from root to leaf (maximum number of edges in path from root).
»Depth (level): number of edge in the path from the root to that node.
»Branch: internal node, neither the root nor the leaf.
»Successor nodes of a node: its children.
»Predecessor node of a node: its parent.
»Path: sequence of nodes along the edges of a tree.

5. Depth of the whole tree is 3.
Tree height = 3
No. nodes = 16.
No. edges = No. nodes – 1 = 16 – 1 = 15
Lvl 0
Lvl 1
Lvl 2
Lvl 3
Root
Leaf Leaf
LeafLeafLeafLeafLeafLeaf
LeafLeaf
Node Height Depth
A 3 0
B 0 1
C 0 1
D 1 1
… … …

6. Graph Basic Terminology
1 2
4
3
1: Node or Vertex
: Directed Edge
: Undirected Edge
: Weighted Edge (i.e., includes cost)
n
1: Loop
1 2
43
5

7. Adjacency Matrix: an adjacency matrix is a square matrix, or you can say it is a 2D array, and the elements
of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
Graph Representation
1 2
4
3
5
1 2 3 4 5
1 0 1 0 0 0
2 0 0 0 0 1
3 1 0 0 0 0
4 1 0 1 0 0
5 0 0 0 1 0

9. Criteria Tree Graph
Path Only one between two vertices More than one path is allowed
Root node It has exactly one root node Graph doesn’t have a root node
Loops No loops are permitted Graph can have loops
Complexity Less complex More complex comparatively
Traversal techniquesPre-order, In-order and Post-order BFS and DFS
No. edges (n – 1), where n is the no. edgesNot defined
Model type Hierarchical Network
Examples
Social networks, road networks,
computer networks, …, etc.
File systems, family trees, HTML DOM
structure, …, etc.
Tree versus Graph

10. »Completeness: is the technique guaranteed to find a solution (if there is one)?
»Optimality/Admissibility: does it always find a least-cost solution?
»Time Complexity: how long does it take to find a solution?
» Space Complexity: how much memory does it take to find a solution?
10
Criteria to compare different search techniques
–As we are going to consider different techniques to search the problem space,
we need to consider what criteria we will use to compare them.

11. Complete? Yes
Optimal? Yes, if path cost is nondecreasing function of depth
Time Complexity: O(b
d
)
Space Complexity: O(b
d
), note that every node in the fringe is kept in the queue

12. Breadth first search algorithm
▪Put an arbitrary node ?????? in queue ??????.
▪Mark the node x as visited.
▪Repeat:
»ℎ = remove the first node from queue ??????.
»Put all of ℎ's unvisited neighbor nodes in a queue ??????.
»Mark all inserted nodes as visited.
queue

13. Breadth First Search (BFS) – Tree
◼Application 1:
Given the following state space (tree search), give the sequence of visited nodes when
using BFS (assume that the node O is the goal state).
A
B C ED
F G H I J
K L
O
M
N

14. ◼A,
A
B C ED
Breadth First Search (BFS) – Tree

15. ◼A,
◼B,
A
B C ED
F G
Breadth First Search (BFS) – Tree

16. ◼A,
◼B,C
A
B C ED
F G H
Breadth First Search (BFS) – Tree

17. ◼A,
◼B,C,D
A
B C ED
F G H I J
Breadth First Search (BFS) – Tree

18. ◼A,
◼B,C,D,E
A
B C ED
F G H I J
Breadth First Search (BFS) – Tree

19. ◼A,
◼B,C,D,E,
◼F,
A
B C ED
F G H I J
Breadth First Search (BFS) – Tree

20. ◼A,
◼B,C,D,E,
◼F,G
A
B C ED
F G H I J
K L
Breadth First Search (BFS) – Tree

21. ◼A,
◼B,C,D,E,
◼F,G,H
A
B C ED
F G H I J
K L
Breadth First Search (BFS) – Tree

22. ◼A,
◼B,C,D,E,
◼F,G,H,I
A
B C ED
F G H I J
K L M
Breadth First Search (BFS) – Tree

23. ◼A,
◼B,C,D,E,
◼F,G,H,I,J,
A
B C ED
F G H I J
K L M
N
Breadth First Search (BFS) – Tree

24. ◼A,
◼B,C,D,E,
◼F,G,H,I,J,
◼K, A
B C ED
F G H I J
K L M
N
Breadth First Search (BFS) – Tree

25. ◼A,
◼B,C,D,E,
◼F,G,H,I,J,
◼K,L A
B C ED
F G H I J
K L
O
M
N
Breadth First Search (BFS) – Tree

26. ◼A,
◼B,C,D,E,
◼F,G,H,I,J,
◼K,L,M, A
B C ED
F G H I J
K L
O
M
N
Breadth First Search (BFS) – Tree

27. ◼A,
◼B,C,D,E,
◼F,G,H,I,J,
◼K,L,M,N, A
B C ED
F G H I J
K L
O
M
N
Breadth First Search (BFS) – Tree

28. ◼A,
◼B,C,D,E,
◼F,G,H,I,J,
◼K,L,M,N,
◼Goal state: O
A
B C ED
F G H I J
K L
O
M
N
Breadth First Search (BFS) – Tree

29. ◼The returned solution is the sequence of operators in the path:
A, B, G, L, O
A
B C ED
F G H I J
K L
O
M
N
Breadth First Search (BFS) – Tree

30. Breadth First Search (BFS) – Graph
◼Application 2:

31. Breadth First Search (BFS) – Graph

32. Breadth First Search (BFS) – Graph

33. Breadth First Search (BFS) – Graph

34. Breadth First Search (BFS) – Graph

35. Breadth First Search (BFS) – Graph

36. Breadth First Search (BFS) – Graph

37. Breadth First Search (BFS) – Graph

38. Breadth First Search (BFS) – Graph

39. Breadth First Search (BFS) – Graph

40. Breadth First Search (BFS) – Graph
DONE!
(The queue has become empty)

41. Complete? No
Optimal? No
Time Complexity: O(b
m
)
Space Complexity: O(b ×m)

42. ◼Application 1:
Given the following state space (tree search), give the sequence of visited nodes when
using DFS (assume that the node O is the goal state).
A
B C ED
F G H I J
K L
O
M
N
Depth First Search (DFS) – Tree

43. ◼A,
A
B C ED
Depth First Search (DFS) – Tree

44. ◼A,B,
A
B C ED
F G
Depth First Search (DFS) – Tree

45. ◼A,B,F,
A
B C ED
F G
Depth First Search (DFS) – Tree

46. ◼A,B,F,
◼G,
A
B C ED
F G
K L
Depth First Search (DFS) – Tree

47. ◼A,B,F,
◼G,K,
A
B C ED
F G
K L
Depth First Search (DFS) – Tree

48. ◼A,B,F,
◼G,K,
◼L,
A
B C ED
F G
K L
O
Depth First Search (DFS) – Tree

49. ◼A,B,F,
◼G,K,
◼L, O: Goal State
A
B C ED
F G
K L
O
Depth First Search (DFS) – Tree

50. A
B C ED
F G
K L
O
◼The returned solution is the sequence of operators in the path:
A, B, G, L, O
Depth First Search (DFS) – Tree

51. Depth First Search (DFS) – Graph
◼Application 2:
Stack
(LIFO)

52. Depth First Search (DFS) – Graph

53. Depth First Search (DFS) – Graph

54. Depth First Search (DFS) – Graph

55. Depth First Search (DFS) – Graph

56. Depth First Search (DFS) – Graph

57. Depth First Search (DFS) – Graph

58. Depth First Search (DFS) – Graph

59. Depth First Search (DFS) – Graph

60. Depth First Search (DFS) – Graph

61. Depth First Search (DFS) – Graph
3 is visited, skip!

62. Depth First Search (DFS) – Graph
8 is visited, skip!

63. Depth First Search (DFS) – Graph
DONE!

64. Cairo
Giza Alexandria Port Said
Ismailia
SuezZagazigDamietta
Banha
Arish
127.5 km
172.1 km
218.4 km
5.1 km
198.1 km
356.2 km
202.2 km
336.0 km
141.1 km
200.4 km
Assignment:
•Traverse this graph using BFS.

65. Thank You!