Data Structures & Algorithms - Lecture 2
1mohamedgamal54
146 views
161 slides
Sep 09, 2024
Slide 1 of 161
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
About This Presentation
Data Structures and Algorithms using C++ programming language.
Slide Content
Data Structures and
Algorithms
By Mohamed Gamal
© Mohamed Gamal 2024
C++
Algorithms
By Mohamed Gamal
© Mohamed Gamal 2024
C++
The topics of today’s lecture:
Agenda
Agenda
Searching Algorithms
–Searching is to find the location of specific value in a list of data
elements.
–Searching methods can be divided into two categories:
•Searching methods for both sorted and unsorted lists.
–e.g., Linear (or Sequential) Search.
•Searching methods for sorted lists.
–e.g., Binary Search.
–Direct access by key value (hashing).
–Searching is to find the location of specific value in a list of data
elements.
–Searching methods can be divided into two categories:
•Searching methods for both sorted and unsorted lists.
–e.g., Linear (or Sequential) Search.
•Searching methods for sorted lists.
–e.g., Binary Search.
–Direct access by key value (hashing).
1) Linear (or Sequential) Search
–Linear Search is one of the simplest search algorithms to understand and
implement.
–It can be used on both sorted and unsorted data.
–The algorithm checks each element in the array or list sequentially until the
desired element is found or the end of the list is reached.
target
–Linear Search is one of the simplest search algorithms to understand and
implement.
–It can be used on both sorted and unsorted data.
–The algorithm checks each element in the array or list sequentially until the
desired element is found or the end of the list is reached.
target
Linear Search Algorithm
1)Start from the beginning of the list or array.
2)Iterate through each element sequentially.
3)Compare each element with the target value.
4)If the element matches the target value, return its index (or position).
5)If the end of the list is reached without finding the target value, return a message
indicating the target value is not in the list.
6)Stop.
2 8 5 3 9 4
1)Start from the beginning of the list or array.
2)Iterate through each element sequentially.
3)Compare each element with the target value.
4)If the element matches the target value, return its index (or position).
5)If the end of the list is reached without finding the target value, return a message
indicating the target value is not in the list.
6)Stop.
2 8 5 3 9 4
2 8 5 3 9 4
2 8 5 3 9 4
2 8 5 3 9 4
2 8 5 3 9 4
2 8 5 3 9 4
2 8 5 3 9 4
Initial
Unsorted List
Example:
Target: find 9
1
st
Iteration
2
nd
Iteration
3
rd
Iteration
4
th
Iteration
5
th
Iteration
2 == 9 ?
8 == 9 ?
5 == 9 ?
3 == 9 ?
9 == 9 ?
Target
2 8 5 3 9 4
2 8 5 3 9 4
2 8 5 3 9 4
2 8 5 3 9 4
2 8 5 3 9 4
Initial
Unsorted List
Example:
Target: find 9
1
st
Iteration
2
nd
Iteration
3
rd
Iteration
4
th
Iteration
5
th
Iteration
2 == 9 ?
8 == 9 ?
5 == 9 ?
3 == 9 ?
9 == 9 ?
Target
#include <iostream>
using namespace std;
int linearSearch(int arr[], int n, int target)
{
for(inti = 0; i < n; i++)
if (arr[i] == target)
return i;
return -1;
}
void print(int arr[], int n)
{
cout << "Index: ";
for(inti = 0; i < n; i++)
cout << i << " ";
cout << endl;
cout << "Array: ";
for(inti = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
int main(void)
{
int arr[] = { 2, 8, 5, 3, 9, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int val = 9;
int index = linearSearch(arr, n, val);
print(arr, n);
if (index != -1)
cout << "\nFound " << arr[index] << " at index " << index << endl;
else
cout << "\nNot found!" << endl;
return 0;
}
Linear Search
C++
implementation
using namespace std;
int linearSearch(int arr[], int n, int target)
{
for(inti = 0; i < n; i++)
if (arr[i] == target)
return i;
return -1;
}
void print(int arr[], int n)
{
cout << "Index: ";
for(inti = 0; i < n; i++)
cout << i << " ";
cout << endl;
cout << "Array: ";
for(inti = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
int main(void)
{
int arr[] = { 2, 8, 5, 3, 9, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int val = 9;
int index = linearSearch(arr, n, val);
print(arr, n);
if (index != -1)
cout << "\nFound " << arr[index] << " at index " << index << endl;
else
cout << "\nNot found!" << endl;
return 0;
}
Linear Search
C++
implementation
Complexity:
▪Worst Case: ??????(�)
▪Average Case: ??????(�)
▪Best Case: ??????(1)
Advantages:
▪The algorithm is straightforward to implement with minimal code.
▪Linear Search can be applied to any data structure that supports sequential access, such as
arrays, linked lists, and even files.
▪Linear Search is an in-place search algorithm and does not require any additional memory.
Disadvantages:
▪It is inefficient for large datasets because it may require examining each element.
▪Worst Case: ??????(�)
▪Average Case: ??????(�)
▪Best Case: ??????(1)
Advantages:
▪The algorithm is straightforward to implement with minimal code.
▪Linear Search can be applied to any data structure that supports sequential access, such as
arrays, linked lists, and even files.
▪Linear Search is an in-place search algorithm and does not require any additional memory.
Disadvantages:
▪It is inefficient for large datasets because it may require examining each element.
2) Binary Search
–It uses the divide-and-conquer approach to reduce the search space by half with
each comparison.
–Binary Search continually divides the search interval in half and compares the
middle element with the target value.
–Binary Search requires the data to be sorted in ascending or descending order
before searching.
–Binary Search can be implemented recursively or iteratively.
1 2 3 4 5 8 9
Right or Low
0 1 2 3 4 5 6
Left or High
Sorted
List
Mid
(Low + High) / 2
–It uses the divide-and-conquer approach to reduce the search space by half with
each comparison.
–Binary Search continually divides the search interval in half and compares the
middle element with the target value.
–Binary Search requires the data to be sorted in ascending or descending order
before searching.
–Binary Search can be implemented recursively or iteratively.
1 2 3 4 5 8 9
Right or Low
0 1 2 3 4 5 6
Left or High
Sorted
List
Mid
(Low + High) / 2
Binary Search Algorithm
1)Let min = 0 and max = n – 1, where n is the number of elements in the sorted array.
2)Compute the midpoint:
a)mid = (low + high) / 2
3)Compare the target value with the element at the midpoint:
a)If target == array[mid], return mid (target found).
b)If target < array[mid], set high = mid - 1 (discard the right half).
c)If target > array[mid], set low = mid + 1 (discard the left half).
4)Repeat steps 2-3 until low <= high.
5)If the target value is not found after the loop, return a message indicating it is not
in the array.
1)Let min = 0 and max = n – 1, where n is the number of elements in the sorted array.
2)Compute the midpoint:
a)mid = (low + high) / 2
3)Compare the target value with the element at the midpoint:
a)If target == array[mid], return mid (target found).
b)If target < array[mid], set high = mid - 1 (discard the right half).
c)If target > array[mid], set low = mid + 1 (discard the left half).
4)Repeat steps 2-3 until low <= high.
5)If the target value is not found after the loop, return a message indicating it is not
in the array.
Initial
Sorted List
Example:
Target: find 3
2
nd
Iteration
3
rd
Iteration
Target = arrmid ?
Return mid (target found).
Target < arr[mid] ?
Set high = mid - 1 (discard the right half).
Target > arr[mid] ?
Set low = mid + 1 (discard the left half).
Target
Mid High
1 2 3 4 5 8 9
1 2 3 4 5 8 9
1 2 3 4 5 8 9
Low HighMid
Low
High
Mid
Low
No. Iterations =log
27=3 iterations
1
st
Iteration
Sorted List
Example:
Target: find 3
2
nd
Iteration
3
rd
Iteration
Target = arrmid ?
Return mid (target found).
Target < arr[mid] ?
Set high = mid - 1 (discard the right half).
Target > arr[mid] ?
Set low = mid + 1 (discard the left half).
Target
Mid High
1 2 3 4 5 8 9
1 2 3 4 5 8 9
1 2 3 4 5 8 9
Low HighMid
Low
High
Mid
Low
No. Iterations =log
27=3 iterations
1
st
Iteration
Mid High
1 2 3 4 5 8 913172030
Low
Mid High
1 2 3 4 5 8 913172030
Low
Mid
High
1 2 3 4 5 8 913172030
Low
Target = 20
Mid
(High + Low) / 2
Target = arrmid ?
Return mid (target found).
Target < arr[mid] ?
Set high = mid - 1 (discard the right half).
Target > arr[mid] ?
Set low = mid + 1 (discard the left half).
1 2 3 4 5 8 913172030
Mid
High
Low
1 2 3 4 5 8 913172030
Low
Mid High
1 2 3 4 5 8 913172030
Low
Mid
High
1 2 3 4 5 8 913172030
Low
Target = 20
Mid
(High + Low) / 2
Target = arrmid ?
Return mid (target found).
Target < arr[mid] ?
Set high = mid - 1 (discard the right half).
Target > arr[mid] ?
Set low = mid + 1 (discard the left half).
1 2 3 4 5 8 913172030
Mid
High
Low
Given the list { 1, 2, 3, 4, 5, 8, 9 } and the target value 3
1. First iteration:
1.Calculate mid: mid = (0 + 6) / 2 = 3 (integer division)
2.Compare target 3 with the middle element 4
3.Since 3 < 4, update right boundary: High = 3 − 1 = 2
2. Second iteration:
1.Calculate new mid: mid = (0 + 2) / 2 = 1
2.Compare target 3 with middle element 2
3.Since 3 > 2, update low boundary: Low = 1 + 1 = 2
3. Third iteration:
1.Calculate new mid: mid = (2 + 2) / 2 = 2
2.Compare target 3 with element at index 2: 3
3.Target found at index 2
Thus, it took 3 iterations to find the target value 3.
Target
Mid High
1234589
Low HighMid
Low
High
Mid
Low
1234589
1234589
1. First iteration:
1.Calculate mid: mid = (0 + 6) / 2 = 3 (integer division)
2.Compare target 3 with the middle element 4
3.Since 3 < 4, update right boundary: High = 3 − 1 = 2
2. Second iteration:
1.Calculate new mid: mid = (0 + 2) / 2 = 1
2.Compare target 3 with middle element 2
3.Since 3 > 2, update low boundary: Low = 1 + 1 = 2
3. Third iteration:
1.Calculate new mid: mid = (2 + 2) / 2 = 2
2.Compare target 3 with element at index 2: 3
3.Target found at index 2
Thus, it took 3 iterations to find the target value 3.
Target
Mid High
1234589
Low HighMid
Low
High
Mid
Low
1234589
1234589
#include <iostream>
using namespace std;
int binarySearch(int arr[], int n, int target)
{
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
// Check if target is present at mid
if (arr[mid] == target)
return mid;
// If target greater, ignore left half
else if (target > arr[mid])
low = mid + 1;
// If target is smaller, ignore right half
else
high = mid - 1;
}
return -1;
}
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 8, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
int val = 3;
int index = binarySearch(arr, n, val);
if (index != -1)
cout << "Element found at index " << index << endl;
else
cout << "Element not found in the array" << endl;
return 0;
}
Binary Search
C++
implementation
using namespace std;
int binarySearch(int arr[], int n, int target)
{
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
// Check if target is present at mid
if (arr[mid] == target)
return mid;
// If target greater, ignore left half
else if (target > arr[mid])
low = mid + 1;
// If target is smaller, ignore right half
else
high = mid - 1;
}
return -1;
}
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 8, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
int val = 3;
int index = binarySearch(arr, n, val);
if (index != -1)
cout << "Element found at index " << index << endl;
else
cout << "Element not found in the array" << endl;
return 0;
}
Binary Search
C++
implementation
Complexity:
▪Worst Case: ??????(log�)
▪Average Case: ??????log�
▪Best Case: ??????(1) — at the middle.
Advantages:
▪The algorithm is relatively simple to implement, especially in its iterative form, and easy to understand.
▪Highly efficient and faster for searching large sorted datasets.
▪It does not require additional memory beyond a few variables for indices.
Disadvantages:
▪If the data is not sorted, Binary Search cannot be applied directly. Sorting the data first would incur additional time complexity.
▪Binary Search is not efficient for data structures that do not support random access, such as linked lists, because it relies on
indexing to access the middle element.
▪While the iterative version is simple, the recursive version can be more complex due to additional overhead from recursive
function calls, which use more stack space.
▪For small datasets, the overhead of repeatedly dividing the search space and comparing elements might make it slower compared
to a simpler linear search.
▪Worst Case: ??????(log�)
▪Average Case: ??????log�
▪Best Case: ??????(1) — at the middle.
Advantages:
▪The algorithm is relatively simple to implement, especially in its iterative form, and easy to understand.
▪Highly efficient and faster for searching large sorted datasets.
▪It does not require additional memory beyond a few variables for indices.
Disadvantages:
▪If the data is not sorted, Binary Search cannot be applied directly. Sorting the data first would incur additional time complexity.
▪Binary Search is not efficient for data structures that do not support random access, such as linked lists, because it relies on
indexing to access the middle element.
▪While the iterative version is simple, the recursive version can be more complex due to additional overhead from recursive
function calls, which use more stack space.
▪For small datasets, the overhead of repeatedly dividing the search space and comparing elements might make it slower compared
to a simpler linear search.
Decrease-and-Conquer
Russian Peasant Multiplication
–Russian Peasant Multiplication, also known as Egyptian Multiplication, is an
ancient algorithm for multiplying two numbers.
–Its origins date back to ancient civilizations, including the Egyptians and Russians,
who used this method for its simplicity and ease of use with basic arithmetic
operations.
–The algorithm's beauty lies in its use of only basic operations: addition, halving,
and doubling.
–Russian Peasant Multiplication, also known as Egyptian Multiplication, is an
ancient algorithm for multiplying two numbers.
–Its origins date back to ancient civilizations, including the Egyptians and Russians,
who used this method for its simplicity and ease of use with basic arithmetic
operations.
–The algorithm's beauty lies in its use of only basic operations: addition, halving,
and doubling.
Russian Peasant Multiplication — Algorithm
1)Let the two given numbers be 'a' and 'b'.
2)Initialize result 'res' as 0.
3)Do the following while 'b' is greater than 0
a)If 'b' is odd, add 'a' to 'res'
b)Double 'a' and halve 'b'
4)Return 'res'.
1)Let the two given numbers be 'a' and 'b'.
2)Initialize result 'res' as 0.
3)Do the following while 'b' is greater than 0
a)If 'b' is odd, add 'a' to 'res'
b)Double 'a' and halve 'b'
4)Return 'res'.
÷2 ×2
��
Cancel every row with even numbers.
��
��
Cancel every row with even numbers.
��
Add other rows with odd numbers.
��
��
int russianMult(int a, int b) {
int res = 0;
while (a > 0) {
// if 'a' is odd, add 'b’ to 'res'
if (a % 2 != 0)
res += b;
a= a >> 1; // halve a
b= b << 1; // doubleb
}
return res;
}
Method #1
int res = 0;
while (a > 0) {
// if 'a' is odd, add 'b’ to 'res'
if (a % 2 != 0)
res += b;
a= a >> 1; // halve a
b= b << 1; // doubleb
}
return res;
}
Method #1
int russianMult(int a, int b) {
int res = 0;
while (a > 0) {
// if 'a' is odd, add 'b' to res
if (a % 2 != 0)
res += b;
a /= 2;// halve a
b *= 2;// double b
}
return res;
}
Method #2
int res = 0;
while (a > 0) {
// if 'a' is odd, add 'b' to res
if (a % 2 != 0)
res += b;
a /= 2;// halve a
b *= 2;// double b
}
return res;
}
Method #2
Complexity:
▪Worst Case: Olog� – � is a large integer.
▪Average Case: Olog� – � is a random integer.
▪Best Case: O(log�) – � is a very small integer.
Advantages:
▪Simplicity – easy to implement with basic arithmetic and bitwise operations.
▪Efficiency – logarithmic time complexity, scalable for large values.
Disadvantages:
▪Less practical compared to modern optimized multiplication algorithms.
▪No Built-In Hardware Optimization – relies on software-based arithmetic without direct hardware
support.
▪Worst Case: Olog� – � is a large integer.
▪Average Case: Olog� – � is a random integer.
▪Best Case: O(log�) – � is a very small integer.
Advantages:
▪Simplicity – easy to implement with basic arithmetic and bitwise operations.
▪Efficiency – logarithmic time complexity, scalable for large values.
Disadvantages:
▪Less practical compared to modern optimized multiplication algorithms.
▪No Built-In Hardware Optimization – relies on software-based arithmetic without direct hardware
support.
–There’re two formulas for calculating the day of the week for a given date.
»Zeller’s Congruence
»Key-Value Method
–Both the methods work for the Gregorian calendar.
Introduction
Christian Zeller
»Zeller’s Congruence
»Key-Value Method
–Both the methods work for the Gregorian calendar.
Introduction
Christian Zeller
Saturday Sunday Monday Tuesday Wednesday Thursday Friday
0 1 2 3 4 5 6
Mar Apr May Jun JulAug Sep Oct Nov Dec Jan Feb
3 4 5 6 7 8 9 10 11 12 13 14
Days Chart:
Months Chart:
0 1 2 3 4 5 6
Mar Apr May Jun JulAug Sep Oct Nov Dec Jan Feb
3 4 5 6 7 8 9 10 11 12 13 14
Days Chart:
Months Chart:
1) Zeller’s Congruence
where,
da y of the week
corresponding month number
�isthe required day of the week.
�is the given day of the month.
�is the corresponding month number.
�is the year of century (i.e., last two digits of the given year).
�is the century (i.e., first two digits of the year.)
� =�+
13�+1
5
+�+
�
4
+
�
4
+5� mod 7
� = ���?????? % 100
� = ���??????100
Note: an exception for both January and February, subtract 1 from the given year.
where,
da y of the week
corresponding month number
�isthe required day of the week.
�is the given day of the month.
�is the corresponding month number.
�is the year of century (i.e., last two digits of the given year).
�is the century (i.e., first two digits of the year.)
� =�+
13�+1
5
+�+
�
4
+
�
4
+5� mod 7
� = ���?????? % 100
� = ���??????100
Note: an exception for both January and February, subtract 1 from the given year.
Example: calculate the day for the date 1
st
April 1983.
�=1, �=4, �=1983 % 100=83, �= Τ1983100=19
1
st
April 19 83
����
� =1+
134+1
5
+83+
83
4
+
19
4
+519 mod 7
=216 mod 7
=6
6 is Friday according to the days chart.
� =�+
13�+1
5
+�+
�
4
+
�
4
+5� mod 7
� = ���?????? % 100
� = ���??????100
st
April 1983.
�=1, �=4, �=1983 % 100=83, �= Τ1983100=19
1
st
April 19 83
����
� =1+
134+1
5
+83+
83
4
+
19
4
+519 mod 7
=216 mod 7
=6
6 is Friday according to the days chart.
� =�+
13�+1
5
+�+
�
4
+
�
4
+5� mod 7
� = ���?????? % 100
� = ���??????100
Example: calculate the day for the date 2
nd
March 2004.
� =2+
133+1
5
+4+
4
4
+
20
4
+520 mod 7
=122 mod 7
=3
3 is Tuesday according to the days chart.
� =�+
13�+1
5
+�+
�
4
+
�
4
+5� mod 7
2
nd
March 20 04
����
�=2, �=3, �=2004 % 100=04, �= Τ2004100=20
� = ���?????? % 100
� = ���??????100
nd
March 2004.
� =2+
133+1
5
+4+
4
4
+
20
4
+520 mod 7
=122 mod 7
=3
3 is Tuesday according to the days chart.
� =�+
13�+1
5
+�+
�
4
+
�
4
+5� mod 7
2
nd
March 20 04
����
�=2, �=3, �=2004 % 100=04, �= Τ2004100=20
� = ���?????? % 100
� = ���??????100
Example: calculate the day for the date 27
th
February 2023.
27
th
February 20 23
����
� =�+
13�+1
5
+�+
�
4
+
�
4
+5� mod 7
� =27+
1314+1
5
+22+
22
4
+
20
4
+520 mod 7
=198 mod 7
=2
2 is Monday according to the days chart.
�=27, �=14, �=(2023−1) % 100=22, �= Τ(2023−1)100=20
� = ���?????? % 100
� = ���??????100
Exception for
February !
th
February 2023.
27
th
February 20 23
����
� =�+
13�+1
5
+�+
�
4
+
�
4
+5� mod 7
� =27+
1314+1
5
+22+
22
4
+
20
4
+520 mod 7
=198 mod 7
=2
2 is Monday according to the days chart.
�=27, �=14, �=(2023−1) % 100=22, �= Τ(2023−1)100=20
� = ���?????? % 100
� = ���??????100
Exception for
February !
Python Code
2) Key-Value Method
where,
da y of the week
month k ey v a lue number
century k ey v a lue
�isthe required day of the week.
�is the given day of the month.
�is the month key value number.
�is the year of century (i.e., last two digits of the given year).
�is the century key value (e.g., 0 for the 1900s)
� =�+�+�+
�
4
+� mod 7
where,
da y of the week
month k ey v a lue number
century k ey v a lue
�isthe required day of the week.
�is the given day of the month.
�is the month key value number.
�is the year of century (i.e., last two digits of the given year).
�is the century key value (e.g., 0 for the 1900s)
� =�+�+�+
�
4
+� mod 7
Saturday Sunday Monday Tuesday Wednesday Thursday Friday
0 1 2 3 4 5 6
Jan Feb Mar Apr May Jun JulAug Sep Oct Nov Dec
1 4 4 0 2 5 0 3 6 1 4 6
Days Chart:
Months Key-Value Chart:
1400-1499 2
1500-1599 0
1600-1699 6
1700-1799 4
Century Key-Value Chart:
1800-1899 2
1900-1999 0
2000-2099 6
2100-2199 4
2200-2299 2
2300-2399 0
2400-2499 6
2500-2599 4
…
0 1 2 3 4 5 6
Jan Feb Mar Apr May Jun JulAug Sep Oct Nov Dec
1 4 4 0 2 5 0 3 6 1 4 6
Days Chart:
Months Key-Value Chart:
1400-1499 2
1500-1599 0
1600-1699 6
1700-1799 4
Century Key-Value Chart:
1800-1899 2
1900-1999 0
2000-2099 6
2100-2199 4
2200-2299 2
2300-2399 0
2400-2499 6
2500-2599 4
…
Example: calculate the day for the date 1
st
April 1983.
�=1, �=0, �=83, �=0
1
st
April 19 83
����
� =1+0+83+
83
4
+0 mod 7
=104 mod 7
=6
6 is Friday according to the days chart.
� =�+�+�+
�
4
+� mod 7
Months Chart
Century Chart
st
April 1983.
�=1, �=0, �=83, �=0
1
st
April 19 83
����
� =1+0+83+
83
4
+0 mod 7
=104 mod 7
=6
6 is Friday according to the days chart.
� =�+�+�+
�
4
+� mod 7
Months Chart
Century Chart
Example: calculate the day for the date 2
nd
March 2004.
�=2, �=4, �=04, �=6
� =2+4+4+
4
4
+6 mod 7
=17 mod 7
=3
� =�+�+�+
�
4
+� mod 7
Months Chart
Century Chart
3 is Tuesday according to the days chart.
2
nd
March 20 04
����
nd
March 2004.
�=2, �=4, �=04, �=6
� =2+4+4+
4
4
+6 mod 7
=17 mod 7
=3
� =�+�+�+
�
4
+� mod 7
Months Chart
Century Chart
3 is Tuesday according to the days chart.
2
nd
March 20 04
����
Example: calculate the day for the date 27
th
February 2023.
�=27, �=4, �=23, �=6
� =27+4+23+
23
4
+6 mod 7
=65 mod 7
=2
� =�+�+�+
�
4
+� mod 7
Months Chart
Century Chart
2 is Monday according to the days chart.
27
th
February 20 23
����
th
February 2023.
�=27, �=4, �=23, �=6
� =27+4+23+
23
4
+6 mod 7
=65 mod 7
=2
� =�+�+�+
�
4
+� mod 7
Months Chart
Century Chart
2 is Monday according to the days chart.
27
th
February 20 23
����
Graph are versatile data structures used in many real-world applications.
Graphs Theory Concept
Social Networks
•Nodes: People.
•Edges: connection.
•Application: suggesting friends based on shortest path (i.e., nearby located friends).
Computer Networks
•Nodes: Computers or Routers.
•Edges: Network connections.
•Application: finding the shortest route for data packets.
Ahmed Ali
Saad Omar
3
1 5
Graphs Theory Concept
Social Networks
•Nodes: People.
•Edges: connection.
•Application: suggesting friends based on shortest path (i.e., nearby located friends).
Computer Networks
•Nodes: Computers or Routers.
•Edges: Network connections.
•Application: finding the shortest route for data packets.
Ahmed Ali
Saad Omar
3
1 5
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
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
Graph
Directed Undirected
Weighted Unweighted Weighted Unweighted
Positive Negative Positive Negative
Graph Types
Directed Undirected
Weighted Unweighted Weighted Unweighted
Positive Negative Positive Negative
Graph Types
Graphs Types
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
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
#include <iostream>
using namespace std;
void print(int arr[][5], int rows, int cols);
int main(void) {
int graph[][5] = { { 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0 },
{ 1, 0, 1, 0, 0 },
{ 0, 0, 0, 1, 0 } };
int rows = sizeof(graph) / sizeof(graph[0]);
int cols = sizeof(graph[0]) / sizeof(graph[0][0]);
print(graph, rows, cols);
return 0;
}
void print(int arr[][5], int rows, int cols) {
for(inti = 0; i < rows; i++) {
for (int j = 0; j < cols; j++)
cout << arr[i][j] << " ";
cout << endl;
}
}
C++
implementation
using namespace std;
void print(int arr[][5], int rows, int cols);
int main(void) {
int graph[][5] = { { 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0 },
{ 1, 0, 1, 0, 0 },
{ 0, 0, 0, 1, 0 } };
int rows = sizeof(graph) / sizeof(graph[0]);
int cols = sizeof(graph[0]) / sizeof(graph[0][0]);
print(graph, rows, cols);
return 0;
}
void print(int arr[][5], int rows, int cols) {
for(inti = 0; i < rows; i++) {
for (int j = 0; j < cols; j++)
cout << arr[i][j] << " ";
cout << endl;
}
}
C++
implementation
–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
–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
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
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
Breadth First Search (BFS)
◼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
◼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
◼A,
A
B C ED
Breadth First Search (BFS)
A
B C ED
Breadth First Search (BFS)
◼A,
◼B,
A
B C ED
F G
Breadth First Search (BFS)
◼B,
A
B C ED
F G
Breadth First Search (BFS)
◼A,
◼B,C
A
B C ED
F G H
Breadth First Search (BFS)
◼B,C
A
B C ED
F G H
Breadth First Search (BFS)
◼A,
◼B,C,D
A
B C ED
F G H I J
Breadth First Search (BFS)
◼B,C,D
A
B C ED
F G H I J
Breadth First Search (BFS)
◼A,
◼B,C,D,E
A
B C ED
F G H I J
Breadth First Search (BFS)
◼B,C,D,E
A
B C ED
F G H I J
Breadth First Search (BFS)
◼A,
◼B,C,D,E,
◼F,
A
B C ED
F G H I J
Breadth First Search (BFS)
◼B,C,D,E,
◼F,
A
B C ED
F G H I J
Breadth First Search (BFS)
◼A,
◼B,C,D,E,
◼F,G
A
B C ED
F G H I J
K L
Breadth First Search (BFS)
◼B,C,D,E,
◼F,G
A
B C ED
F G H I J
K L
Breadth First Search (BFS)
◼A,
◼B,C,D,E,
◼F,G,H
A
B C ED
F G H I J
K L
Breadth First Search (BFS)
◼B,C,D,E,
◼F,G,H
A
B C ED
F G H I J
K L
Breadth First Search (BFS)
◼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)
◼B,C,D,E,
◼F,G,H,I
A
B C ED
F G H I J
K L M
Breadth First Search (BFS)
◼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)
◼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)
◼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)
◼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)
◼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)
◼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)
◼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)
◼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)
◼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)
◼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)
◼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)
◼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)
◼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)
A, B, G, L, O
A
B C ED
F G H I J
K L
O
M
N
Breadth First Search (BFS)
Complete? No
Optimal? No
Time Complexity: O(b
m
)
Space Complexity: O(b ×m)
Optimal? No
Time Complexity: O(b
m
)
Space Complexity: O(b ×m)
◼Application 2:
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)
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)
◼A,
A
B C ED
Depth First Search (DFS)
A
B C ED
Depth First Search (DFS)
◼A,B,
A
B C ED
F G
Depth First Search (DFS)
A
B C ED
F G
Depth First Search (DFS)
◼A,B,F,
A
B C ED
F G
Depth First Search (DFS)
A
B C ED
F G
Depth First Search (DFS)
◼A,B,F,
◼G,
A
B C ED
F G
K L
Depth First Search (DFS)
◼G,
A
B C ED
F G
K L
Depth First Search (DFS)
◼A,B,F,
◼G,K,
A
B C ED
F G
K L
Depth First Search (DFS)
◼G,K,
A
B C ED
F G
K L
Depth First Search (DFS)
◼A,B,F,
◼G,K,
◼L,
A
B C ED
F G
K L
O
Depth First Search (DFS)
◼G,K,
◼L,
A
B C ED
F G
K L
O
Depth First Search (DFS)
◼A,B,F,
◼G,K,
◼L, O: Goal State
A
B C ED
F G
K L
O
Depth First Search (DFS)
◼G,K,
◼L, O: Goal State
A
B C ED
F G
K L
O
Depth First Search (DFS)
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)
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)
Complete? Yes, if there is a goal state at a depth less than L
Optimal? No
Time Complexity: O(b
L
)
Space Complexity: O(bL)
Optimal? No
Time Complexity: O(b
L
)
Space Complexity: O(bL)
◼Application 3:
Given the following state space (tree search), give the sequence of visited nodes when
using DLS (Limit = 2).
A
B C ED
F G H I J
K L
O
M
N
Limit = 0
Limit = 1
Limit = 2
Depth-Limited Search (DLS)
Given the following state space (tree search), give the sequence of visited nodes when
using DLS (Limit = 2).
A
B C ED
F G H I J
K L
O
M
N
Limit = 0
Limit = 1
Limit = 2
Depth-Limited Search (DLS)
◼A,
A
B C ED
Limit = 2
Limit = 0
Limit = 1
Depth-Limited Search (DLS)
A
B C ED
Limit = 2
Limit = 0
Limit = 1
Depth-Limited Search (DLS)
◼A,B,
A
B C ED
F G
Limit = 2
Limit = 0
Limit = 1
Limit = 2
Depth-Limited Search (DLS)
A
B C ED
F G
Limit = 2
Limit = 0
Limit = 1
Limit = 2
Depth-Limited Search (DLS)
◼A,B,F,
A
B C ED
F G
Limit = 2
Limit = 0
Limit = 1
Limit = 2
Depth-Limited Search (DLS)
A
B C ED
F G
Limit = 2
Limit = 0
Limit = 1
Limit = 2
Depth-Limited Search (DLS)
◼A,B,F,
◼G,
A
B C ED
F G
Limit = 2
Limit = 0
Limit = 1
Limit = 2
Depth-Limited Search (DLS)
◼G,
A
B C ED
F G
Limit = 2
Limit = 0
Limit = 1
Limit = 2
Depth-Limited Search (DLS)
◼A,B,F,
◼G,
◼C,
A
B C ED
F G HLimit = 2
Limit = 0
Limit = 1
Limit = 2
Depth-Limited Search (DLS)
◼G,
◼C,
A
B C ED
F G HLimit = 2
Limit = 0
Limit = 1
Limit = 2
Depth-Limited Search (DLS)
◼A,B,F,
◼G,
◼C,H,
A
B C ED
F G HLimit = 2
Limit = 0
Limit = 1
Limit = 2
Depth-Limited Search (DLS)
◼G,
◼C,H,
A
B C ED
F G HLimit = 2
Limit = 0
Limit = 1
Limit = 2
Depth-Limited Search (DLS)
◼A,B,F,
◼G,
◼C,H,
◼D, A
B C ED
F G H I JLimit = 2
Limit = 0
Limit = 1
Limit = 2
Depth-Limited Search (DLS)
◼G,
◼C,H,
◼D, A
B C ED
F G H I JLimit = 2
Limit = 0
Limit = 1
Limit = 2
Depth-Limited Search (DLS)
◼A,B,F,
◼G,
◼C,H,
◼D,I A
B C ED
F G H I JLimit = 2
Limit = 0
Limit = 1
Limit = 2
Depth-Limited Search (DLS)
◼G,
◼C,H,
◼D,I A
B C ED
F G H I JLimit = 2
Limit = 0
Limit = 1
Limit = 2
Depth-Limited Search (DLS)
◼A,B,F,
◼G,
◼C,H,
◼D,I
◼J,
A
B C ED
F G H I JLimit = 2
Limit = 0
Limit = 1
Limit = 2
Depth-Limited Search (DLS)
◼G,
◼C,H,
◼D,I
◼J,
A
B C ED
F G H I JLimit = 2
Limit = 0
Limit = 1
Limit = 2
Depth-Limited Search (DLS)
◼A,B,F,
◼G,
◼C,H,
◼D,I
◼J,
◼E
A
B C ED
F G H I JLimit = 2
Limit = 0
Limit = 1
Limit = 2
Depth-Limited Search (DLS)
◼G,
◼C,H,
◼D,I
◼J,
◼E
A
B C ED
F G H I JLimit = 2
Limit = 0
Limit = 1
Limit = 2
Depth-Limited Search (DLS)
◼A,B,F,
◼G,
◼C,H,
◼D,I
◼J,
◼E, Failure
A
B C ED
F G H I JLimit = 2
Limit = 2
Depth-Limited Search (DLS)
◼G,
◼C,H,
◼D,I
◼J,
◼E, Failure
A
B C ED
F G H I JLimit = 2
Limit = 2
Depth-Limited Search (DLS)
◼DLS algorithm returns Failure (no solution)
◼The reason is that the goal is beyond the limit (Limit =2): the goal depth is (d=4)
A
B C ED
F G H I J
K L
O
M
N
Limit = 2
Solution: use IDS!
Depth-Limited Search (DLS)
◼The reason is that the goal is beyond the limit (Limit =2): the goal depth is (d=4)
A
B C ED
F G H I J
K L
O
M
N
Limit = 2
Solution: use IDS!
Depth-Limited Search (DLS)
Complete? Yes
Optimal? Yes
Time Complexity: O(b
d
)
Space Complexity: O(bd)
Optimal? Yes
Time Complexity: O(b
d
)
Space Complexity: O(bd)
◼Application 4:
Given the following state space (tree search), give the sequence of visited nodes when
using IDS.
A
B C ED
F G H I J
K L
O
M
N
Limit = 0
Limit = 1
Limit = 2
Limit = 3
Limit = 4
Iterative Deepening Search (IDS)
Given the following state space (tree search), give the sequence of visited nodes when
using IDS.
A
B C ED
F G H I J
K L
O
M
N
Limit = 0
Limit = 1
Limit = 2
Limit = 3
Limit = 4
Iterative Deepening Search (IDS)
Iterative Deepening Search (IDS)
DLS with bound = 0
DLS with bound = 0
◼A,
A
Limit = 0
Iterative Deepening Search (IDS)
A
Limit = 0
Iterative Deepening Search (IDS)
◼A, Failure
A
Limit = 0
Iterative Deepening Search (IDS)
A
Limit = 0
Iterative Deepening Search (IDS)
Iterative Deepening Search (IDS)
DLS with bound = 1
DLS with bound = 1
◼A,
A
B C EDLimit = 1
Iterative Deepening Search (IDS)
A
B C EDLimit = 1
Iterative Deepening Search (IDS)
◼A,B,
A
B C EDLimit = 1
Iterative Deepening Search (IDS)
A
B C EDLimit = 1
Iterative Deepening Search (IDS)
◼A,B,
◼C,
A
B C EDLimit = 1
Iterative Deepening Search (IDS)
◼C,
A
B C EDLimit = 1
Iterative Deepening Search (IDS)
◼A,B,
◼C,
◼D,
A
B C EDLimit = 1
Iterative Deepening Search (IDS)
◼C,
◼D,
A
B C EDLimit = 1
Iterative Deepening Search (IDS)
◼A,B
◼C,
◼D,
◼E, A
B C EDLimit = 1
Iterative Deepening Search (IDS)
◼C,
◼D,
◼E, A
B C EDLimit = 1
Iterative Deepening Search (IDS)
◼A,B,
◼C,
◼D,
◼E, Failure A
B C EDLimit = 1
Iterative Deepening Search (IDS)
◼C,
◼D,
◼E, Failure A
B C EDLimit = 1
Iterative Deepening Search (IDS)
Iterative Deepening Search (IDS)
DLS with bound = 2
DLS with bound = 2
◼A,
A
B C ED
Limit = 2
Iterative Deepening Search (IDS)
A
B C ED
Limit = 2
Iterative Deepening Search (IDS)
◼A,B,
A
B C ED
F GLimit = 2
Iterative Deepening Search (IDS)
A
B C ED
F GLimit = 2
Iterative Deepening Search (IDS)
◼A,B,F,
A
B C ED
F GLimit = 2
Iterative Deepening Search (IDS)
A
B C ED
F GLimit = 2
Iterative Deepening Search (IDS)
◼A,B,F,
◼G,
A
B C ED
F GLimit = 2
Iterative Deepening Search (IDS)
◼G,
A
B C ED
F GLimit = 2
Iterative Deepening Search (IDS)
◼A,B,F,
◼G,
◼C,
A
B C ED
F G HLimit = 2
Iterative Deepening Search (IDS)
◼G,
◼C,
A
B C ED
F G HLimit = 2
Iterative Deepening Search (IDS)
◼A,B,F,
◼G,
◼C,H,
A
B C ED
F G HLimit = 2
Iterative Deepening Search (IDS)
◼G,
◼C,H,
A
B C ED
F G HLimit = 2
Iterative Deepening Search (IDS)
◼A,B,F,
◼G,
◼C,H,
◼D, A
B C ED
F G H I JLimit = 2
Iterative Deepening Search (IDS)
◼G,
◼C,H,
◼D, A
B C ED
F G H I JLimit = 2
Iterative Deepening Search (IDS)
◼A,B,F,
◼G,
◼C,H,
◼D,I A
B C ED
F G H I JLimit = 2
Iterative Deepening Search (IDS)
◼G,
◼C,H,
◼D,I A
B C ED
F G H I JLimit = 2
Iterative Deepening Search (IDS)
◼A,B,F,
◼G,
◼C,H,
◼D,I
◼J,
A
B C ED
F G H I JLimit = 2
Iterative Deepening Search (IDS)
◼G,
◼C,H,
◼D,I
◼J,
A
B C ED
F G H I JLimit = 2
Iterative Deepening Search (IDS)
◼A,B,F,
◼G,
◼C,H,
◼D,I
◼J,
◼E
A
B C ED
F G H I JLimit = 2
Iterative Deepening Search (IDS)
◼G,
◼C,H,
◼D,I
◼J,
◼E
A
B C ED
F G H I JLimit = 2
Iterative Deepening Search (IDS)
◼A,B,F,
◼G,
◼C,H,
◼D,I
◼J,
◼E, Failure
A
B C ED
F G H I J
K L
O
M
N
Limit = 2
Iterative Deepening Search (IDS)
◼G,
◼C,H,
◼D,I
◼J,
◼E, Failure
A
B C ED
F G H I J
K L
O
M
N
Limit = 2
Iterative Deepening Search (IDS)
Iterative Deepening Search (IDS)
DLS with bound = 3
DLS with bound = 3
◼A,
A
B C ED
Limit = 3
Iterative Deepening Search (IDS)
A
B C ED
Limit = 3
Iterative Deepening Search (IDS)
◼A,B,
A
B C ED
F G
Limit = 3
Iterative Deepening Search (IDS)
A
B C ED
F G
Limit = 3
Iterative Deepening Search (IDS)
◼A,B,F,
A
B C ED
F G
Limit = 3
Iterative Deepening Search (IDS)
A
B C ED
F G
Limit = 3
Iterative Deepening Search (IDS)
◼A,B,F,
◼G,
A
B C ED
F G
K LLimit = 3
Iterative Deepening Search (IDS)
◼G,
A
B C ED
F G
K LLimit = 3
Iterative Deepening Search (IDS)
◼A,B,F,
◼G,K,
A
B C ED
F G
K LLimit = 3
Iterative Deepening Search (IDS)
◼G,K,
A
B C ED
F G
K LLimit = 3
Iterative Deepening Search (IDS)
◼A,B,F,
◼G,K,
◼L,
A
B C ED
F G
K LLimit = 3
Iterative Deepening Search (IDS)
◼G,K,
◼L,
A
B C ED
F G
K LLimit = 3
Iterative Deepening Search (IDS)
◼A,B,F,
◼G,K,
◼L,
◼C, A
B C ED
F G H
K LLimit = 3
Iterative Deepening Search (IDS)
◼G,K,
◼L,
◼C, A
B C ED
F G H
K LLimit = 3
Iterative Deepening Search (IDS)
◼A,B,F,
◼G,K,
◼L,
◼C,H, A
B C ED
F G H
K LLimit = 3
Iterative Deepening Search (IDS)
◼G,K,
◼L,
◼C,H, A
B C ED
F G H
K LLimit = 3
Iterative Deepening Search (IDS)
◼A,B,F,
◼G,K,
◼L,
◼C,H,
◼D,
A
B C ED
F G H I J
K LLimit = 3
Iterative Deepening Search (IDS)
◼G,K,
◼L,
◼C,H,
◼D,
A
B C ED
F G H I J
K LLimit = 3
Iterative Deepening Search (IDS)
◼A,B,F,
◼G,K,
◼L,
◼C,H,
◼D,I,
A
B C ED
F G H I J
K L MLimit = 3
Iterative Deepening Search (IDS)
◼G,K,
◼L,
◼C,H,
◼D,I,
A
B C ED
F G H I J
K L MLimit = 3
Iterative Deepening Search (IDS)
◼A,B,F,
◼G,K,
◼L,
◼C,H,
◼D,I,M,
A
B C ED
F G H I J
K L MLimit = 3
Iterative Deepening Search (IDS)
◼G,K,
◼L,
◼C,H,
◼D,I,M,
A
B C ED
F G H I J
K L MLimit = 3
Iterative Deepening Search (IDS)
◼A,B,F,
◼G,K,
◼L,
◼C,H,
◼D,I,M,
◼J,
A
B C ED
F G H I J
K L M
N
Limit = 3
Iterative Deepening Search (IDS)
◼G,K,
◼L,
◼C,H,
◼D,I,M,
◼J,
A
B C ED
F G H I J
K L M
N
Limit = 3
Iterative Deepening Search (IDS)
◼A,B,F,
◼G,K,
◼L,
◼C,H,
◼D,I,M,
◼J,N,
A
B C ED
F G H I J
K L M
N
Limit = 3
Iterative Deepening Search (IDS)
◼G,K,
◼L,
◼C,H,
◼D,I,M,
◼J,N,
A
B C ED
F G H I J
K L M
N
Limit = 3
Iterative Deepening Search (IDS)
◼A,B,F,
◼G,K,
◼L,
◼C,H,
◼D,I,M,
◼J,N,
◼E,
A
B C ED
F G H I J
K L M
N
Limit = 3
Iterative Deepening Search (IDS)
◼G,K,
◼L,
◼C,H,
◼D,I,M,
◼J,N,
◼E,
A
B C ED
F G H I J
K L M
N
Limit = 3
Iterative Deepening Search (IDS)
◼A,B,F,
◼G,K,
◼L,
◼C,H,
◼D,I,M,
◼J,N,
◼E,Failure
A
B C ED
F G H I J
K L
O
M
N
Limit = 3
Iterative Deepening Search (IDS)
◼G,K,
◼L,
◼C,H,
◼D,I,M,
◼J,N,
◼E,Failure
A
B C ED
F G H I J
K L
O
M
N
Limit = 3
Iterative Deepening Search (IDS)
Iterative Deepening Search (IDS)
DLS with bound = 4
DLS with bound = 4
◼A,
A
B C ED
Limit = 4
Iterative Deepening Search (IDS)
A
B C ED
Limit = 4
Iterative Deepening Search (IDS)
◼A,B,
A
B C ED
F G
Limit = 4
Iterative Deepening Search (IDS)
A
B C ED
F G
Limit = 4
Iterative Deepening Search (IDS)
◼A,B,F,
A
B C ED
F G
Limit = 4
Iterative Deepening Search (IDS)
A
B C ED
F G
Limit = 4
Iterative Deepening Search (IDS)
◼A,B,F,
◼G,
A
B C ED
F G
K L
Limit = 4
Iterative Deepening Search (IDS)
◼G,
A
B C ED
F G
K L
Limit = 4
Iterative Deepening Search (IDS)
◼A,B,F,
◼G,K,
A
B C ED
F G
K L
Limit = 4
Iterative Deepening Search (IDS)
◼G,K,
A
B C ED
F G
K L
Limit = 4
Iterative Deepening Search (IDS)
◼A,B,F,
◼G,K,
◼L,
A
B C ED
F G
K L
OLimit = 4
Iterative Deepening Search (IDS)
◼G,K,
◼L,
A
B C ED
F G
K L
OLimit = 4
Iterative Deepening Search (IDS)
◼A,B,F,
◼G,K,
◼L, O: Goal State
A
B C ED
F G
K L
OLimit = 4
Iterative Deepening Search (IDS)
◼G,K,
◼L, O: Goal State
A
B C ED
F G
K L
OLimit = 4
Iterative Deepening Search (IDS)
The returned solution is the sequence of operators in the path:
A, B, G, L, O
A
B C ED
F G
K L
O
Iterative Deepening Search (IDS)
A, B, G, L, O
A
B C ED
F G
K L
O
Iterative Deepening Search (IDS)
Game Playing
•Minimax uses DFS to evaluate nodes.
•Perfect play for deterministic games.
•Idea: choose a move to position with highest minimax value (i.e., best achievable
payoff against best play.
•e.g., 2-play games.
•Minimax Visualizer
Minimax Algorithm
•Perfect play for deterministic games.
•Idea: choose a move to position with highest minimax value (i.e., best achievable
payoff against best play.
•e.g., 2-play games.
•Minimax Visualizer
Minimax Algorithm
Game tree (2-player, deterministic, turns)
Tic Tac Teo
Tic Tac Teo
max
max
min
min
© Patrick Winston
max
min
min
© Patrick Winston
© Patrick Winston
max
max
min
min
max
max
min
min
max
max
min
min
© Patrick Winston
max
min
min
© Patrick Winston
max
max
min
min
© Patrick Winston
max
min
min
© Patrick Winston
max
max
min
min
© Patrick Winston
max
min
min
© Patrick Winston
max
max
min
min
© Patrick Winston
max
min
min
© Patrick Winston
max
max
min
min
© Patrick Winston
max
min
min
© Patrick Winston
max
max
min
min
© Patrick Winston
max
min
min
© Patrick Winston
max
max
min
min
© Patrick Winston
max
min
min
© Patrick Winston
max
max
min
min
© Patrick Winston
max
min
min
© Patrick Winston
max
max
min
min
© Patrick Winston
max
min
min
© Patrick Winston
#include <iostream>
using namespace std;
int log2(int n);
intmax(inta, intb);
intmin(inta, intb);
int minimax(int depth, int nodeIndex, bool isMax, int scores[], int h);
int main()
{
// The number of elements in scores must be a power of 2
intscores[] = { 84, -29, -37, -25, 1, -43, -75, 49, -21, -51, 58, -46, -3, -13, 26, 79 };
int n = sizeof(scores) / sizeof(scores[0]);
int height = log2(n);
intres= minimax(0, 0, true, scores, height);
cout << "The optimal value is " << res << endl;
return 0;
}
/*
depth: current depth in game tree.
nodeIndex: index of current node in scores[].
isMax: true if current move is of maximizer, else false.
scores[]: stores leaves of Game tree.
h: maximum height of Game tree.
*/
int minimax(int depth, int nodeIndex, bool isMax, int scores[], int h)
{
// terminating condition ( i.e leaf node is reached)
if (depth == h)
return scores[nodeIndex];
// if current move is maximizer, find the maximum attainable value
if (isMax)
return max(minimax(depth + 1, nodeIndex * 2, false, scores, h), minimax(depth + 1, nodeIndex * 2 + 1, false, scores, h));
// else (if current move is Minimizer), find the minimum attainable value
else
return min(minimax(depth + 1, nodeIndex * 2, true, scores, h), minimax(depth + 1, nodeIndex * 2 + 1, true, scores, h));
}
// function to find Log n in base 2 using recursion
int log2(int n) {
return(n== 1) ? 0 : 1 + log2(n/ 2);
}
// maximum element function
intmax(inta, intb) {
return (a > b) ? a : b;
}
// minimum element function
intmin(inta, intb) {
return (a < b) ? a : b;
}
Minimax
C++
implementation
using namespace std;
int log2(int n);
intmax(inta, intb);
intmin(inta, intb);
int minimax(int depth, int nodeIndex, bool isMax, int scores[], int h);
int main()
{
// The number of elements in scores must be a power of 2
intscores[] = { 84, -29, -37, -25, 1, -43, -75, 49, -21, -51, 58, -46, -3, -13, 26, 79 };
int n = sizeof(scores) / sizeof(scores[0]);
int height = log2(n);
intres= minimax(0, 0, true, scores, height);
cout << "The optimal value is " << res << endl;
return 0;
}
/*
depth: current depth in game tree.
nodeIndex: index of current node in scores[].
isMax: true if current move is of maximizer, else false.
scores[]: stores leaves of Game tree.
h: maximum height of Game tree.
*/
int minimax(int depth, int nodeIndex, bool isMax, int scores[], int h)
{
// terminating condition ( i.e leaf node is reached)
if (depth == h)
return scores[nodeIndex];
// if current move is maximizer, find the maximum attainable value
if (isMax)
return max(minimax(depth + 1, nodeIndex * 2, false, scores, h), minimax(depth + 1, nodeIndex * 2 + 1, false, scores, h));
// else (if current move is Minimizer), find the minimum attainable value
else
return min(minimax(depth + 1, nodeIndex * 2, true, scores, h), minimax(depth + 1, nodeIndex * 2 + 1, true, scores, h));
}
// function to find Log n in base 2 using recursion
int log2(int n) {
return(n== 1) ? 0 : 1 + log2(n/ 2);
}
// maximum element function
intmax(inta, intb) {
return (a > b) ? a : b;
}
// minimum element function
intmin(inta, intb) {
return (a < b) ? a : b;
}
Minimax
C++
implementation
–Time complexity: O(b
m
)
–Space complexity: O(b m)
Mini-Max Properties
Minimax uses DFS to evaluate nodes !
Same as DFS
m
)
–Space complexity: O(b m)
Mini-Max Properties
Minimax uses DFS to evaluate nodes !
Same as DFS
function minimax(node, depth, maximizingPlayer):
if depth = 0 or node is a terminal node:
return the heuristic value of the node
if maximizingPlayer:
bestValue = -infinity
for each child node of node:
v = minimax(child, depth - 1, FALSE)
bestValue = max(bestValue, v)
return bestValue
else:
bestValue = +infinity
for each child node of node:
v = minimax(child, depth - 1, TRUE)
bestValue = min(bestValue, v)
return bestValue
Minimax
Algorithm
if depth = 0 or node is a terminal node:
return the heuristic value of the node
if maximizingPlayer:
bestValue = -infinity
for each child node of node:
v = minimax(child, depth - 1, FALSE)
bestValue = max(bestValue, v)
return bestValue
else:
bestValue = +infinity
for each child node of node:
v = minimax(child, depth - 1, TRUE)
bestValue = min(bestValue, v)
return bestValue
Minimax
Algorithm
Tic Tac Teo Game using
Minimax algorithm
Minimax algorithm
End of lecture 2
Thank You!
Thank You!
Download
Download Slideshow Get the original presentation fileQuick Actions
Statistics
- Views 146
- Slides 161
- Age 452 days
Related Slideshows
11
8-top-ai-courses-for-customer-support-representatives-in-2025.pptx
JeroenErne2
51 views
10
7-essential-ai-courses-for-call-center-supervisors-in-2025.pptx
JeroenErne2
49 views
13
25-essential-ai-courses-for-user-support-specialists-in-2025.pptx
JeroenErne2
39 views
11
8-essential-ai-courses-for-insurance-customer-service-representatives-in-2025.pptx
JeroenErne2
38 views
21
Know for Certain
DaveSinNM
24 views
17
PPT OPD LES 3ertt4t4tqqqe23e3e3rq2qq232.pptx
novasedanayoga46
27 views