TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI Course outline

VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

Chapter 1. Fundamentals
Chapter 2. Algorithmic paradigms
Chapter 3. Basic data structures
Data structures and Algorithms Chapter 4. Tree
Chapter 5. Sorting
Nguyễn Khánh Phương

Computer Science department

Chapter 6. Searching
School of Information and Communication technology
E-mail: phuongnk@soict.hust.edu.vn Chapter 7. Graph
2

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
Contents
1. Brute force
2. Recursion
3. Backtracking
4. Divide and conquer
Chapter 2. Algorithmic paradigms
5. Dynamic programming
Nguyễn Khánh Phương

Computer Science department

School of Information and Communication technology
E-mail: phuongnk@soict.hust.edu.vn

1
Contents 1. Brute force (Exhaustive search)
Brute force – Exhaustive search:
1. Brute force • When the problem requires finding objects that satisfy a certain properties from
2. Recursion a given se of projects, we can apply the brute force:
– Browse all the objects: for each object, check whether it satisfies the
3. Backtracking required properties or not, if so, that object is the solution to find, if not,
keep searching.
4. Divide and conquer Example (Traveling Salesman Problem): A tourist wants to visit n cities T1, T2, ...,
Tn. Itinerary is a way of going from a certain city through all the remaining cities,
5. Dynamic programming each city exactly once, and then back to the starting city. Let dij the cost of going
fron Ti to Tj (i, j = 1, 2,..., n). Find itinerary with minimum total cost.
Answer: browse all n! possible itineraries, each itinerary calculates the
corresponding trip cost, and compares these n! values to get the one with minimum
value.
• Brute force: simple, but computation time is inefficient.

5 NGUYỄN KHÁNH PHƯƠNG

CS - SOICT-HUST

Example: Stock span problem Contents

This problem is often asked in interviews of Google and Amazon:
1. Brute force
2. Recursion
Example:
3. Backtracking
Prices of stock in period of 6 days are {100, 60, 70, 65, 80, 85}, then stock span 4. Divide and conquer
= {0,0,1,0,3,4}.
Solve by brute force: 5. Dynamic programming
Browse for each day i (from left to right for i = 0,..,5):
• span[i] = 0;
• scan each previous day j of i (for j = i-1,..,0):
– if price[j] <= price[i] then span[i]++;
– else break;
Complexity: O(N2) where N is number of days.
Exercise: propose algorithm with complexity of O(N) and memory O(N) 7 NGUYỄN KHÁNH PHƯƠNG 8
CS - SOICT-HUST

2
2. Recursion 2.1. The concept of recursion
2.1. The concept of recursion • In practice, we often encounter objects that include themselves or are
defined in terms of themselves. We say those objects are defined
2.2. Recursive algorithm diagram recursively.
• Example
2.3. Some illustrative examples
– Check attendance
2.4. Analysis of recursive algorithm – Fractal
– Recursive function
2.5. Recursion and memorization
– Sets are defined recursively
– Trees are defined recursively
– ...

NGUYỄN KHÁNH PHƯƠNG 9 NGUYỄN KHÁNH PHƯƠNG

CS - SOICT-HUST CS - SOICT-HUST

Recursive example: Check attendance Recursive example: Check attendance

NGUYỄN KHÁNH PHƯƠNG NGUYỄN KHÁNH PHƯƠNG

CS - SOICT-HUST CS - SOICT-HUST

3
Recursive example: Check attendance Recursive example: Check attendance

NGUYỄN KHÁNH PHƯƠNG NGUYỄN KHÁNH PHƯƠNG

CS - SOICT-HUST CS - SOICT-HUST

Recursive example: Check attendance Recursive example: Check attendance

NGUYỄN KHÁNH PHƯƠNG NGUYỄN KHÁNH PHƯƠNG

CS - SOICT-HUST CS - SOICT-HUST

4
Recursive example: Check attendance Recursive example: Check attendance

NGUYỄN KHÁNH PHƯƠNG NGUYỄN KHÁNH PHƯƠNG

CS - SOICT-HUST CS - SOICT-HUST

Recursive example: Check attendance Recursive example: Check attendance

NGUYỄN KHÁNH PHƯƠNG NGUYỄN KHÁNH PHƯƠNG

CS - SOICT-HUST CS - SOICT-HUST

5
Recursive example: Check attendance Example: The Handshake Problem
There are n people in the room. Everyone shakes hands with
n-1 others, each exactly once. Calculate h(n) the total number
of possible handshakes
h(n) = h(n-1) + n-1 h(4) = h(3) + 3 h(3) = h(2) + 2 h(2) = 1

NGUYỄN KHÁNH PHƯƠNG

CS - SOICT-HUST
h(n): The sum of integers from 1 to n-1 = n(n-1) / 2

Recursive example: Fractals Recursive Functions

Recursive functions are determined depending on the non-negative integer variables n
according to the following diagram:
Basic Step: Determine the value of function when n=0: f(0).
Recursive Step: Given values of f(k), k ≤ n, give the rules to calculate the value of
f(n+1).

Example 1:
f(0) = 3, n=0
f(n+1) = 2f(n) + 3, n>0
Fractals are examples of recursively constructed
Then we have: f(1) = 2 × 3 + 3 = 9, f(2) = 2 × 9 + 3 = 21, ...
images (objects that repeat recursively).

6
Recursive Functions factorial(3);
Example 2: Recursive definition to calculate n! int factorial(int n){
if (n==0)
f(0) = 1 return 1;
f(n) = n * f(n-1) else
return n*factorial(n-1);
}
To calculate the value of recursive function, we replace it gradually according to the
recursive definition to obtain the expression with smaller and smaller arguments until (7) Return 6 Execution of the factorial
we get the first condition. (3) function will stop
until factorial (2) returns
For example: factorial(3):
the result
recursive 3 == 0 ? NO
return factorial(2)*3 (1) Inside function factorial(3) When factorial (2)
(6) return 2 call to factorial(2) returns the result, the
factorial(2): factorial (3) function
2 == 0 ? NO continues to be executed
return factorial(1)*2 (2) Inside function factorial(2)
(5) return 1 call to factorial(1)
5! = 5 · 4! = 5 · 4 · 3! = 5 · 4 · 3 · 2! = 5 · 4 · 3 · 2 · 1! factorial(1):
= 5 · 4 · 3 · 2 · 1 · 0! = 5 · 4 · 3 · 2 · 1 · 1 = 120 1 == 0 ? NO
return factorial(0)*1 (3) Inside function factorial(1)
int factorial(int n){
call to factorial(0)
if (n==0)
(4) return 1
First condition return 1; factorial(0):
0 == 0 ? YES
else return 1
return n*factorial(n-1);
}

factorial(4); factorial(4);
int factorial(int n){ int factorial(int n){
if (n==0) if (n==0)
factorial(4) else
return 1; factorial(4) else
return 1;

return n*factorial(n-1); return n*factorial(n-1);

} }

n=4
Returns 4*factorial(3)

Execution of the factorial (4) function

will stop until factorial (3) returns the
result
When factorial (3) returns the result,
the factorial (4) function continues to
be executed

7
factorial(4); factorial(4);
int factorial(int n){ int factorial(int n){
if (n==0) if (n==0)
factorial(4) else
return 1; factorial(4) else
return 1;

return n*factorial(n-1); return n*factorial(n-1);

} }

n=4 n=4
Returns 4*factorial(3) Returns 4*factorial(3)
n=3 n=3
Returns 3*factorial(2) Returns 3*factorial(2)
n=2
Returns 2*factorial(1)

factorial(4); factorial(4);
int factorial(int n){ int factorial(int n){
if (n==0) if (n==0)
factorial(4) else
return 1; factorial(4) else
return 1;

return n*factorial(n-1); return n*factorial(n-1);

} }

n=4 n=4
Returns 4*factorial(3) Returns 4*factorial(3)
n=3 n=3
Returns 3*factorial(2) Returns 3*factorial(2)
n=2 n=2
Returns 2*factorial(1) Returns 2*factorial(1)

n=1 n=1
Returns 1*factorial(0) Returns 1*factorial(0)
n=0
Returns 1

8
factorial(4); factorial(4);
int factorial(int n){ int factorial(int n){
if (n==0) if (n==0)
factorial(4) else
return 1; factorial(4) else
return 1;

return n*factorial(n-1); return n*factorial(n-1);

} }

n=4 n=4
Returns 4*factorial(3) Returns 4*factorial(3)
n=3 n=3
Returns 3*factorial(2) Returns 3*factorial(2)
n=2 n=2
Returns 2*factorial(1) Returns 2*factorial(1)
n=1

1
Returns 1*factorial(0)

factorial(4); factorial(4);
int factorial(int n){ int factorial(int n){
if (n==0) if (n==0)
factorial(4) else
return 1; factorial(4) else
return 1;

return n*factorial(n-1); return n*factorial(n-1);

} }

n=4 n=4
Returns 4*factorial(3) Returns 4*factorial(3)
n=3

6
Returns 3*factorial(2)

9
factorial(4); Recursive functions are all re-implementable using the while / for loop

int factorial(int n){

if (n==0)
• We can also implement to calculate value of n! by using the while loop
factorial(4) else
return 1;

24
return n*factorial(n-1);
} int factorial (int n)
{
i=n; fact = 1;
int factorial(int n){
while(i >= 1) if (n==0)
{ return 1;
else
fact=fact*i; return n*factorial(n-1);
i--; }

}
return fact;
}
Note: Replacing a recursive function by a non-recursive function is often
called recursive reduction (khử đệ quy). Recursive reduction is not
always as easy to perform as it is in the case of factorial calculations.

Example 3 Recursive Functions

Write a recursive function helperProd to calculate the product of all
Exercise: Write recursive function to calculate the sum of numbers
numbers in the list n 1
Example: helperProd({1,3,3,4}) = 36 a0, a1, …, an-1 s n   ak
k 0

Suggest: Build recursive function:

helperProd(list, k) = list[k]*list[k+1]*…*list[list.size-1] Recursive definition of sum:
s1 = a0
list[0] * list[1] * list[2] * list[3]
helperProd(list, 3) sn = sn-1 + an-1
helperProd(list, 2)

helperProd(list, 1)

helperProd(list, 0)

NGUYỄN KHÁNH PHƯƠNG NGUYỄN KHÁNH PHƯƠNG

CS - SOICT-HUST CS - SOICT-HUST

10
Example 4. Fibonacci 2. Recursion
Recursive function F(n) :
• First values : F(n=0) =0; F(n=1) = 1
2.1. The concept of recursion
• Recursive formular: F(n) = F(n-1) + F(n-2)
Recursive implementation Implement by using loop
2.2. Recursive algorithm diagram
int F(int n) int F(int n) 2.3. Some illustrative examples
if n < 2 then if n < 2 then return n;
return n; else
{
2.4. Analysis of recursive algorithm
else x= 0; F(n-2)
return F(n-1) + F(n-2); y= 1; F(n-1) 2.5. Recursion and memorization
for k = 1 to n-1
{ z = x+y; F(n)
x = y;
y = z;
}
} NGUYỄN KHÁNH PHƯƠNG
return y; //y isBộF(n)
môn KHMT – ĐHBK HN
41 NGUYỄN KHÁNH PHƯƠNG 42
CS - SOICT-HUST

Recursive algorithm diagram 2. Recursion

procedure RecAlg(input)
{ 2.1. The concept of recursion
if (the size of input is minimum) then
Do basic step; //solve problem with smallest input size 2.2. Recursive algorithm diagram
else
{
RecAlg(input with smaller size) ; // recursive step
2.3. Some illustrative examples
//could have more than one call to RecAlg
Combine solution of subproblem to obtain solution; 2.4. Analysis of recursive algorithm
return (solution) ;

}
} 2.5. Recursion with memorization
Computation time:
T(n) = if (base case) then const cost
else ( time to solve all subproblems +
time to combine solutions)
Computation time depends on:
– Number of subproblems
– Size of subproblem NGUYỄN KHÁNH PHƯƠNG NGUYỄN KHÁNH PHƯƠNG 44
CS - SOICT-HUST CS - SOICT-HUST
– Time to combine solutions of subproblems

11
Example 1: Calculate the binomial coefficient Example 2: Recursive Binary Search
• The binomial coefficient C(n,k) is defined recursively as Input: An array S consists of n elements: S[0],…,S[n-1] in ascending
following: order; Value key with the same data type as array S.
Output: the index in array if key is found, -1 if key is not found
C(n,0) = 1, C(n,n) =1; where n >=0,
Binary search algorithm: The value key either
C(n,k) = C(n-1,k-1)+C(n-1,k), where 0 < k < n equals to the element at the middle of the array S,
or is at the left half (L) of the array S,
or is at the right half (R) of the array S.
• Recursive implementation on C:
(The situation L (R) happen only when key is smaller (larger) than the element at
int C(int n, int k){ the middle of the array S)
if ((k==0)||(k==n)) return 1;
int binsearch(int low, int high, int S[], int key)
else return C(n-1,k-1)+C(n-1,k);
6 13 14 25 33 43 51 53 64 72 84 93 95 96 97 key = 33
} 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

NGUYỄN KHÁNH PHƯƠNG

CS - SOICT-HUST low
binsearch(0, 14, S, 33); high
46

Example 2: Recursive Binary Search Example: Binary Search

Input: An array S consists of n elements: S[0],…,S[n-1] in ascending int binsearch(int low, int high, int S[], int key)
{
order; Value key with the same data type as array S. if (low <= high)
{
Output: the index in array if key is found, -1 if key is not found int mid = (low + high) / 2;
if (S[mid]== key) return mid;
else if (key < S[mid])
key=33
int binsearch(int low, int high, int S[], int key) return binsearch(low, mid-1, S, key);
{ else
if (low <= high) return binsearch(mid+1, high, S, key);
}
{ else return -1;
int mid = (low + high) / 2; }
if (S[mid]==key) return mid;
else if (key < S[mid]) 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
return binsearch(low, mid-1, S, key); 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
else
return binsearch(mid+1, high, S, key); lo hi
} binsearch(0, 14, S, 33);
else return -1;
}
NGUYỄN KHÁNH PHƯƠNG 47 48
CS - SOICT-HUST

12
Example: Binary Search Example: Binary Search
int binsearch(int low, int high, int S[], int key) int binsearch(int low, int high, int S[], int key)
{ {
if (low <= high) if (low <= high)
{ {
int mid = (low + high) / 2; int mid = (low + high) / 2;
if (S[mid]== key) return mid;
else if (key < S[mid])
key=33 if (S[mid]== key) return mid;
else if (key < S[mid])
key=33
return binsearch(low, mid-1, S, key); return binsearch(low, mid-1, S, key);
else else
return binsearch(mid+1, high, S, key); return binsearch(mid+1, high, S, key);
} }
else return -1; else return -1;
} }

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

lo mid hi lo hi
binsearch(0, 14, S, 33); binsearch(0, 14, S, 33);
The section to be binsearch(0, 6, S, 33); binsearch(0, 6, S, 33);
investigated is halved
49 50
after each iteration

Example: Binary Search Example: Binary Search

int binsearch(int low, int high, int S[], int key) int binsearch(int low, int high, int S[], int key)
{ {
if (low <= high) if (low <= high)
{ {
int mid = (low + high) / 2; int mid = (low + high) / 2;
if (S[mid]== key) return mid;
else if (key < S[mid])
key=33 if (S[mid]== key) return mid;
else if (key < S[mid])
key=33
return binsearch(low, mid-1, S, key); return binsearch(low, mid-1, S, key);
else else
return binsearch(mid+1, high, S, key); return binsearch(mid+1, high, S, key);
} }
else return -1; else return -1;
} }

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

lo mid hi lo hi
binsearch(0, 14, S, 33); binsearch(0, 14, S, 33);
The section to be binsearch(0, 6, S, 33); binsearch(0, 6, S, 33);
investigated is halved binsearch(4, 6, S, 33); binsearch(4, 6, S, 33);
51 52
after each iteration

13
Example: Binary Search Example: Binary Search
int binsearch(int low, int high, int S[], int key) int binsearch(int low, int high, int S[], int key)
{ {
if (low <= high) if (low <= high)
{ {
int mid = (low + high) / 2; int mid = (low + high) / 2;
if (S[mid]== key) return mid;
else if (key < S[mid])
key=33 if (S[mid]== key) return mid;
else if (key < S[mid])
key=33
return binsearch(low, mid-1, S, key); return binsearch(low, mid-1, S, key);
else else
return binsearch(mid+1, high, S, key); return binsearch(mid+1, high, S, key);
} }
else return -1; else return -1;
} }

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

lo mid hi lo
hi
binsearch(0, 14, S, 33); binsearch(0, 14, S, 33);
The section to be binsearch(0, 6, S, 33); binsearch(0, 6, S, 33);
investigated is halved binsearch(4, 6, S, 33); binsearch(4, 6, S, 33);
53 54
after each iteration binsearch(4, 4, S, 33); binsearch(4, 4, S, 33);

Example: Binary Search Example 3: Palindrome

int binsearch(int low, int high, int S[], int key)
{ • Definition. Palindrome is a string that reads it from left
if (low <= high)
{ to right is the same as reading it from right to left.
int mid = (low + high) / 2;
if (S[mid]== key) return mid;
else if (key < A[mid])
key=33 Example: NOON, DEED, RADAR, MADAM
else
return binsearch(low, mid-1, S, key);
Able was I ere I saw Elba
return binsearch(mid+1, high, S, key);
} • To determine if a given string is palindrome:
else return -1;
} – Compare the first character and the last character of
6 13 14 25 33 43 51 53 64 72 84 93 95 96 97 the string.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
• If they are equal: new string = old string that
lo removes the first and last characters. Repeat
hi
mid binsearch(0, 14, S, 33); comparison step.
binsearch(0, 6, S, 33);
binsearch(4, 6, S, 33); • If they are different: given string is not palindrome
55
binsearch(4, 4, S, 33);

14
Example 3: Palindrome: str[start….end] Example 4: Path on grid
• Base case : string has <=1 character (start >= end) • Given the grid of size D*C.
return true • You are only allowed to move from one node to other node on the grid in
• Recursive step: either direction downwards or to the right.
return true if (str[start]==str[end] && • How many paths are there from node (i, j) to node (D, C).
palindrome(str, start+1, end-1)) – Write function: int CountPaths(int i, int j, int D, int C)

(0,0) (0,C)

(i, j)

(D,0) (D,C)
NGUYỄN KHÁNH PHƯƠNG
CS - SOICT-HUST

Example 5: Path on grid Basic case

(0,0) (0,C)

(i, j)

• If you step over the edge of the grid (no longer on the grid), there is no path to the node
(D,0) (D,C) (D, C):
– if (i > D) OR (j > C): CountPaths(i,j, D, C) return 0
• To solve the problem CountPaths(i,j, D, C), we need to solve which
subproblems ?
– From node (i, j) there are only 2 ways: DONE ?
• Go down: to node (i+1, j) CountPaths(i+1,j, D, C) NO: because all subproblems
• Go right: to node (i, j+1) CountPaths(i,j+1, D, C) will return 0
CountPaths(i,j, D, C) = CountPaths(i+1,j, D, C)
+ CountPaths(i,j+1, D, C) One more special case should be considered: when you are at line D or column C 
there is a path (this path does not need any steps) 60

15
Example 5: Path on grid Example 5: Path on grid: VARIATION
• Given the grid of size D*C. • Besides going either downwards or to the right, we can also go diagonally.
• You are only allowed to move from one node to other node on the grid in • How many paths are there from node (i, j) to node (D, C).
either direction downwards or to the right. – Function: int CountPaths(int i, int j, int D, int C)
• How many paths are there from node (i, j) to node (D, C).
– Function: int CountPaths(int i, int j, int D, int C)

Example 5: Path on grid: VARIATION 2. Recursion

2.1. The concept of recursion
2.2. Recursive algorithm diagram
2.3. Some illustrative examples
2.4. Analysis of recursive algorithm
2.5. Recursion and memorization

63 NGUYỄN KHÁNH PHƯƠNG 64

CS - SOICT-HUST

16
2.4. Analysis of recursive algorithm Example: Recursive Binary Search
int binsearch(int low, int high, int S[], int key)
• To analyze the computation time of recursive algorithm, we usually proceed {
if (low <= high)
as follows:
{
– Let T(n) be the computation time of the algorithm int mid = (low + high) / 2;
if (S[mid]==key) return mid;
– Build a recursive formula for T(n). else if (key < S[mid])
return binsearch(low, mid-1, S, key);
– Solve this recursive formula to get the evaluation for T(n) else
return binsearch(mid+1, high, S, key);
• Generally, we only need a close assessment of the growth rate of T(n), so }
else return -1;
solving the recursive formula for T(n) is to evaluate the growth rate of T(n) }
 binsearch(0, n-1, S, key);
in the asymptotic notation Let T(n): the computation time of binary search when when array S has n
elements
T(n) = T(n/2) + K
T(1) = c
where c and K are constants NGUYỄN KHÁNH PHƯƠNG 66
CS - SOICT-HUST

Solving recurrence Example: Recursive Binary Search

• Three methods for solving recurrences--that is, for obtaining Backward substitution: this works exactly as its name suggests. Starting from the
asymptotic "" or "O" bounds on the solution: equation itself, work backwards, substituting values of the function for previous ones
T(n)= T(n/2) + K
– Backward substitution starts from the equation itself, work
where T(1) = c
backwards, substituting values of the function for previous ones
T(n) = T(n/2) + K substitute for T(n/2)
– Recurrence trees involves mapping out the recurrence tree for an = T(n/4) + K + K substitute for T(n/4)
equation. Starting from the equation, you unfold each recursive = T(n/8) + K + K + K
call to the function and calculate the non-recursive cost at each = T(n/23) + 3*K in more compact form
level of the tree. Then, you find a general formula for each level =…
and take a summation over all such levels = T(n/2i) + i*K “inductive leap”
– Master theorem provides bounds for recurrences of the form
T(n) = T(n/2logn) + K*logn “choose i = logn”
= T(n/n) + K*logn
= T(1) + K*logn = c +K*logn

NGUYỄN KHÁNH PHƯƠNG NGUYỄN KHÁNH PHƯƠNG

CS - SOICT-HUST CS - SOICT-HUST

17
 Solve recursive formula:
Solving recurrence T(n) = T(n/2) + K, T(1) = c
• Three methods for solving recurrences--that is, for obtaining Iteration Cost
asymptotic "" or "O" bounds on the solution: 0 T(n) 0
– Backward substitution starts from the equation itself, work
backwards, substituting values of the function for previous ones 1 T(n/2) K
– Recurrence trees involves mapping out the recurrence tree for an
2 T(n/4) K
equation. Starting from the equation, you unfold each recursive
call to the function and calculate the non-recursive cost at each ………
level of the tree. Then, you find a general formula for each level
and take a summation over all such levels log2n T(1) K
– Master theorem provides bounds for recurrences of the form
• Value of T(n) is equal to cost at all iterations:
𝑇 𝑛 =𝑇 1 + ∑ 𝐾 = c + Klog2n

 So we have T(n) = O(log2n)

NGUYỄN KHÁNH PHƯƠNG
CS - SOICT-HUST

1.6. Solving recurrence Master Theorem

• Three methods for solving recurrences--that is, for obtaining • Let T(n) be a monotonically increasing function that satisfies
asymptotic "" or "O" bounds on the solution: T(n) = a T(n/b) + f(n)
– Backward substitution starts from the equation itself, work
T(1) = c
backwards, substituting values of the function for previous ones
– Recurrence trees involves mapping out the recurrence tree for an
where a  1, b  2, c>0. If f(n)=cnd (in other words, f(n) is
equation. Starting from the equation, you unfold each recursive (nd)) where d  0 then
call to the function and calculate the non-recursive cost at each
level of the tree. Then, you find a general formula for each level if a < bd
and take a summation over all such levels T(n) = If a = bd
– Master theorem provides bounds for recurrences of the form if a > bd

NGUYỄN KHÁNH PHƯƠNG

CS - SOICT-HUST

18
Example: Recursive Binary Search Master Theorem: Pitfalls
• Let T(n)= T(n/2) + K. What are the parameters?
a= 1
b= 2
d= 0
Therefore, which condition applies?
• You cannot use the Master Theorem if
1 = 20, case 2 applies
– T(n) is not monotone, e.g. T(n) = sin(n)
• We conclude that 𝑇(𝑛)𝜖 𝚯(𝑛 log 𝑛) = 𝚯 (log𝑛)
– f(n) is not a polynomial, e.g. T(n) = 2T(n/2)+ 2n
– b cannot be expressed as a constant, e.g.

NGUYỄN KHÁNH PHƯƠNG

CS - SOICT-HUST

Master Theorem: Example 1 Master Theorem: Example 2

• Let T(n) = T(n/2) + ½ n2 + n. What are the parameters? • Let T(n)= 2 T(n/4) + √𝑛 + 42. What are the parameters?
a= 1 a= 2
b= 2 b= 4
d= 2 d = 1/2
Therefore, which condition applies? Therefore, which condition applies?
1 < 22, case 1 applies 2 = 41/2, case 2 applies
• We conclude that T(n)  (nd) = (n2) • We conclude that

19
Master Theorem: Example 3 Exercise 1
• Let T(n)= 3 T(n/2) + (3/4)n + 1. What are the parameters? Consider the following example
a= 3 T(n) = 2T(n/2) + n, T(1)= 4
b= 2 • Apply these methods for solving above recurrence:
d= 1
– Backward substitution starts from the equation itself, work
Therefore, which condition applies? backwards, substituting values of the function for previous ones
3 > 21, case 3 applies – Recurrence trees involves mapping out the recurrence tree for an
• We conclude that equation. Starting from the equation, you unfold each recursive call
to the function and calculate the non-recursive cost at each level of
the tree. Then, you find a general formula for each level and take a
• Note that log231.584…, can we say that T(n)   (n1.584) ???? summation over all such levels
No, because log231.5849… and n1.584   (n1.5849)
– Master theorem provides bounds for recurrences of the form

NGUYỄN KHÁNH PHƯƠNG

CS - SOICT-HUST

Exercise 2: Tower of Hanoi Tower of Hanoi: n=5

The Tower of Hanoi, consists of three towers (a), (b), (c) together with n disks of The objective of the game is to move all the disks from tower (a) to tower (c), following
3 rules:
different sizes. Initially these disks are stacked on the tower (a) in an ascending
1. Only one disk can be moved at a time.
order, i.e. the smaller one sits over the larger one. 2. Only the top disk can be moved
The objective of the game is to move all the disks from tower (a) to tower (c), 3. No large disk can be sit over a smaller disk.
following 3 rules:
• Only one disk can be moved at a time.
• Only the top disk can be moved
• No large disk can be sit over a smaller disk.
Let hn denote the minimum number of moves needed to solve the Tower of Hanoi
problem with n disks. What is the recurrence relation for hn?

79
Tower a Tower c
Toán rời rạc
Tower b
Tower a Tower c Tower b

20
Exercise: Tower of Hanoi Exercise: Tower of Hanoi
• h1 = 1 • h1 = 1
• For n ≥ 2, we need to do 3 following steps to transfer all disks from tower (a) to tower (c): • For n ≥ 2, we need to do 3 following steps to transfer all disks from tower (a) to tower (c):
(1) Move the top n - 1 disks (following the rules of the game) from tower (a) to tower (b) (1) Move the top n - 1 disks (following the rules of the game) from tower (a) to tower (b)
The problem of n-1 disks  #moves = hn-1
(2) Move the largest disk to the tower (c) (2) Move the largest disk to the tower (c)
 #moves = 1
(3) Move the n-1 disks (following the rules of the game) from tower (b) to tower (c), placing (3) Move the n-1 disks (following the rules of the game) from tower (b) to tower (c), placing
them on top of the largest disk them on top of the largest disk
The problem of n-1 disks #moves = hn-1

hn = 2hn-1 + 1, n ≥ 2
h1 = 1

Tower a Tower c
Toán rời rạc
Tower b Tower a Tower c
Toán rời rạc
Tower b

Tower of Hanoi: n=5 Tower of Hanoi

(1) Move the top n - 1 disks (following the rules of the game) from tower (a) to tower (b) The algorithm could be implemented as following:
The problem of n-1 disks  #moves = hn-1 //move n disks from tower a to tower c using tower b as an intermediary:
(2) Move the largest disk to the tower (c)
HanoiTower(n, a, c, b);
 #moves = 1
(3) Move the n-1 disks (following the rules of the game) from tower (b) to tower (c) , placing
{
them on top of the largest disk if (n==1) then <move disk from tower a to tower c>
The problem of n-1 disks  #moves = hn-1 else
{
HanoiTower(n-1,a,b,c);
HanoiTower(1,a,c,b);
HanoiTower(n-1,b,c,a);
}
}

Tower a Tower c
Toán rời rạc
Tower b

21
Tower of Hanoi: Implementation Exercise: Tower of Hanoi
• Let T(n) = 2T(n-1) + 1. What are the parameters?
a=
b= hn = 2 hn−1 + 1
d=
Therefore, which condition applies?

Exercise 2: Tower of Hanoi 2. Recursion

Backward substitution: this works exactly as its name suggests. Starting from the
equation itself, work backwards, substituting values of the function for previous ones 2.1. The concept of recursion
T(n) = 2 T(n−1) + 1
2.2. Recursive algorithm diagram
= 2 (2 T(n−2) + 1) + 1 = 22 T(n−2) + 2 + 1
= 22(2 T(n−3) + 1) + 2 + 1 = 23 T(n−3) + 22 + 2 + 1 2.3. Some illustrative examples
…
= 2n−1 T(1) + 2n−2 + … + 2 + 1 2.4. Analysis of recursive algorithm
= 2n−1 + 2n−2 + … + 2 + 1 (because T(1) = 1)
= 2n − 1
2.5. Recursion with memorization

 Time complexity: O(2n) which is exponential

NGUYỄN KHÁNH PHƯƠNG NGUYỄN KHÁNH PHƯƠNG 88

CS - SOICT-HUST CS - SOICT-HUST

22
2.5. Recursion with memorization Duplication of subproblems
• In the previous section, we see that recursive algorithms for • Realizing that in recursive algorithms, whenever we need the
calculating Fibonacci numbers and calculating binomial solution of a subproblem, we must solve it recursively.
coefficients were inefficient. To increase the efficiency of Therefore, there are subproblems that are solved repeatedly. That
recursive algorithms without having to build iterative or leads to inefficiency of the algorithm. This phenomenon is called
recursive reduction procedures, we can use “recursion with duplication of subproblem.
memorization” technique. Example: Recursive algorithm to calculate C (5,3). The recursive
tree that executes the call to function C (5,3) is shown in the
• Using this technique, in many cases, we maintain the
following:
recursive structure of the algorithm and at the same time
ensure its effectiveness. The biggest downside to this
approach is the memory requirement.

NGUYỄN KHÁNH PHƯƠNG NGUYỄN KHÁNH PHƯƠNG

CS - SOICT-HUST CS - SOICT-HUST

Example: Duplication of subproblems when calculating C(5,3) Example: Duplication of subproblems when calculating Fibonacci F(4)

int F (int n) {
if (n < 2) return n;
else return F(n-1)+F(n-2);
}
C(5,3)
F (4)
C(4,2) C(4,3)

F (3) F (2)
C(3,1) C(3,2) C(3,2) C(3,3)

F (2) F (1) F (1) F(0)

C(2,0) C(2,1) C(2,1) C(2,2) C(2,1) C(2,2)

F (1) F (0)
C(1,0) C(1,1) C(1,0) C(1,1) C(1,0) C(1,1)

23
Recursive with memorization Example: Recursive with memorization to calculate C(n,k)
• To overcome this phenomenon, the idea of recursive with memorization int C(int n,int k){
is: We will use the variable to memorize information about the solution if (D[n][k]>0) return D[n][k];
of subproblem right after the first time it is solved. This allows to shorten else{
the computation time of the algorithm, because, whenever needed, it can D[n][k] = C(n-1,k-1)+C(n-1,k);
be looked up without having to solve the subproblems that have been return D[n][k];
solved before. }
Example: Recursive algorithm calculates binomial coefficients, we put a }
variable Before calling function C(n, k), we need to initialize array D[ ][ ] as following:
• D[n][k] to record calculated value of C(n, k). • D[i][0] = 1, D[i][n]=1, where i = 0,1,..., n;
• Initially D[n][k]=0, when C(n, k) is calculated, this value will be stored in • D[i][j] = 0, for remaining values of i, j
D[n][k]. Therefore, if D[n][k]>0 then it means there is no need to
recursively call function C(n, k)

Contents Backtracking (Thuật toán quay lui)

1. Brute force 3.1. Algorithm diagram
2. Recursion 3.2. Generate basic combinatorial configurations
– Generate binary strings of length n
3. Backtracking
– Generate m-element subsets of the set of n elements
4. Divide and conquer
– Generate permutations of n elements
5. Dynamic programming

NGUYỄN KHÁNH PHƯƠNG 95 NGUYỄN KHÁNH PHƯƠNG

CS - SOICT-HUST CS - SOICT-HUST

24
Backtracking idea Backtracking idea
• A clever form of exhaustive search. • Clearly, at a single junction you could
• Backtracking is a technique used to solve problems with a large search have even more than 2 choices.
space, by systematically trying and eliminating possibilities.
Example of backtracking would be going through a maze. • The backtracking strategy says to try
• At some point in a maze, you might have two options of which direction each choice, one after the other,
to go: Junction – if you ever get stuck, "backtrack"
o One strategy would be to try going Portion B to the junction and try the next
through Portion A of the maze.
choice.
Portion A

o If you get stuck before you A B

find your way out, then you C
"backtrack" to the junction. • If you try all choices and never found B
stuck A
o At this point in time you know that a way out, then there IS no solution to
Portion A will NOT lead you out the maze.
of the maze,
o so you then start searching in
Portion B

Backtracking (animation) Backtracking idea

dead end • Dealing with the maze:
? – From your start point, you will iterate through each possible
dead end starting move.
dead end
1 – From there, you recursively move forward.
? – If you ever get stuck, the recursion takes you back to where you
start ? ?
a
dead end were, and you try the next possible move.
2
dead end
?
• Make sure you don't try too many possibilities,
success! – Mark which locations in the maze have been visited already so that
Pseudo code for recursive backtracking algorithm: no location in the maze gets visited twice.
Backtrack(S)
If S is a complete solution, report success – If a place has already been visited, there is no point in trying to
For ( every possible choice e from current state / node) a reach the end of the maze from there again.
If (S∪{e}) is not go to a dead end then Backtrack(S ∪{e}) 1 2
Back out of the current choice to restore the state at the beginning of the loop. a

25
Backtracking diagram Backtracking diagram
• Enumeration problem (Q): Given A1, A2,..., An be finite sets. All basic combinatorial enumeration problem could be rephrased in the
Denote form of Enumeration problem (Q).
A = A1 A2  ... An = { (a1, a2, ..., an): ai  Ai , i=1, 2, ..., n}. Example:
Assume P is a property on the set A. The problem is to enumerate • The problem of enumerating all binary string of length n leads to the
all elements of the set A that satisfies the property P: enumeration of elements of the set:
D = { a = (a1, a2, ..., an)  A: a satisfy property P }. Bn = {(a1, ..., an): ai  {0, 1}, i=1, 2, ..., n}.

• Elements of the set D are called feasible solution (lời giải chấp • The problem of enumerating all m-element subsets of set N = {1, 2, ...,
nhận được). n} requires to enumerate elements of the set:
S(m,n) = {(a1,..., am)Nm: 1 ≤ a1 < ... < am ≤ n }.
• The problem of enumerating all permutations of natural numbers 1, 2,
..., n requires to enumerate elements of the set
n = {(a1,..., an)  Nn: ai ≠ aj ; i ≠ j }.
NGUYỄN KHÁNH PHƯƠNG
CS - SOICT-HUST

Partial solution (Lời giải bộ phận) Backtracking diagram

The solution to the problem is an ordered tuple of n elements Backtracking algorithm is built based on the construction each
(a1, a2, ..., an), where ai  Ai , i = 1, 2, ..., n. component of solution one by one.
• Algorithm starts with empty solution ( ).
Definition. The k-level partial solution (0 ≤ k ≤ n) is an
• Based on the property P, we determine which elements of set A1 could
ordered tuple of k elements be selected as the first component of solution. Such elements are
(a1, a2, ..., ak), called as candidates for the first component of solution. Denote
candidates for the first component of solution as S1. Take an element
where ai  Ai , i = 1, 2, ..., k. a1  S1, insert it into empty solution, we obtain 1-level partial
• When k = 0, 0-level partial solution is denoted as ( ), and solution: (a1).
called as the empty solution.
• When k = n, we have a complete solution to a problem.

26
Backtracking diagram Backtracking diagram
• General step: Assume we have k-1 level partial solution: • Sk ≠ : Take ak  Sk to insert it into current (k-1)-level partial solution (a1,
a2, ..., ak-1), we obtain k-level partial solution (a1, a2, ..., ak-1, ak). Then
(a1, a2, ..., ak-1),
– If k = n, then we obtain a complete solution to the problem,
Now we need to build k-level partial solution: – If k < n, we continue to build the (k+1)th component of solution.
(a1, a2, ..., ak-1, ak) • Sk=: It means the partial solution (a1, a2, ..., ak-1) can not continue to
– Based on the property P, we determine which elements of set Ak could be develop into the complete solution. In this case, we backtrack to find new
candidate for (k-1)th position of solution (note: this new candidate must be
selected as the kth component of solution.
an element of Sk-1)
– Such elements are called as candidates for the kth position of solution
– If one could find such candidate, we insert it into (k-1)th position, then
when k-1 first components have been chosen as (a1, a2, ..., ak-1). Denote continue to build the kth component.
these candidates by Sk.
– If such candidate could not be found, we backtrack one more step to find
– Consider 2 cases: new candidate for (k-2)th position,… If backtrack till the empty solution,
we still can not find new candidate for 1st position, then the algorithm is
• Sk ≠ 
finished.
• Sk = 

Backtracking algorithm Backtracking algorithm

Decision tree for backtracking
(recursive) (not recursive)
void Try(int k) void Backtracking ( )
{ {
<Build Sk as the set to consist of candidates for the kth
k=1;
component of solution>; <Build Sk>;
Root (empty solution)
for y  Sk //Each candidate y of Sk while (k > 0) {
Candidate set S1 {
a1 𝑎 while (Sk   ) {
ak = y; ak  Sk; // Take ak from Sk
[maybe: update values of variables] if (k == n)> then <Record (a1,a2,...,ak) as a
(a1) (𝑎 ) if (k == n) then <Record (a1, a2, ..., ak) as a
Candidate set S2 when there complete solution >;
complete solution >;
is (a1) else {
a2 𝑎 𝑎 else Try(k+1);
𝑎 [maybe: return the variables to their old values]
k = k+1;
} <Build Sk>;
(a1, a2) (a1, 𝑎 ) (𝑎 , 𝑎 ) } }
The call to execute backtracking algorithm: Try(1); }
Candidate set S3 a3 k = k - 1; // Backtracking
𝑎 • If only one solution need to be found, then it is
when there is (a1, a2) 𝑎 }
necessary to find a way to terminate the nested }
(a1, a2, a3) (a1, a2, 𝑎 )
recursive calls generated by the call to Try(1)
(a1, 𝑎 , 𝑎 ) once the first solution has just been recorded. The call to execute backtracking algorithm:
Backtracking ( );
• If at the end of the algorithm, we obtain no
solution, it means that the problem does not
have any solution.

27
Two key issues Note
• In order to implement a backtracking algorithm to solve a • If the length of complete solution is not known in advanced, and solutions are not
needed to have the same length:
specific combinatorial problems, we need to solve the
following two basic problems:
– Find algorithm to build candidate set Sk
– Find a way to describe these sets so that you can implement the
operation to enumerate all their elements (implement the loop for
y ∈ Sk).
• Then we need to modify statement
• The efficiency of the enumeration algorithm depends on whether we if (k == n) then <Record (a1, a2, ..., ak) as a complete solution >;
can accurately identify these candidate sets. else Try(k+1);
to
if <(a1, a2, ..., ak) is a complete solution> then <Record (a1, a2, ..., ak) as a complete solution >;
else Try(k+1);

NGUYỄN KHÁNH PHƯƠNG

 Need to build a function to check whether (a1, a2, ..., ak) is the complete solution.
CS - SOICT-HUST

Backtracking (Thuật toán quay lui) Example 1: Enumerate all binary string of length n
3.1. Algorithm diagram • Problem to enumerate all binary string of length n leads to the
enumeration of all elements of the set:
3.2. Generate basic combinatorial configurations An = {(a1, ..., an): ai  {0, 1}, i=1, 2, ..., n}.
– Generate binary strings of length n • We consider how to solve two issue keys to implement backtracking
algorithm:
– Generate m-element subsets of the set of n elements – Build candidate set Sk: We have S1 = {0, 1}. Assume we have
– Generate permutations of n elements binary string of length k-1 (a1, ..., ak-1), then Sk = {0,1}. Thus, the
candidate sets for each position of the solution are determined.
– Implement the loop to enumerate all elements of Sk: we can use the
loop for
for (y=0; y<=1; y++) in C/C++

NGUYỄN KHÁNH PHƯƠNG NGUYỄN KHÁNH PHƯƠNG

CS - SOICT-HUST CS - SOICT-HUST

28
Decision tree to enumerate binary strings of length 3 Program in C++ (Recursive)
#include <iostream> void Try(int k)

()
Sk = {0,1} using namespace std;
int n, count;
{
for (int j = 0; j<=1; j++)
int a[100]; {
a[k] = j;
0 1 void PrintSolution() if (k == n) PrintSolution();
else Try(k+1);
{
}
(0) int i, j;
}
(1) count++;

0 1 0 1 cout<<“String # " <<count<<": ";

for (i=1 ; i<= n ;i++)
int main()
{
(00) (01) (10) (11) { cout<<“Enter n = ";cin>>n;
j=a[i]; count = 0; Try(1);
0 1 0 1 0 1 0 1 }
cout<<j<<" ";
}
cout<<“Number of strings "<<count;

cout<<endl;
}
(000) (001) (010) (011) (100) (101) (110) (111)

NGUYỄN KHÁNH PHƯƠNG NGUYỄN KHÁNH PHƯƠNG

CS - SOICT-HUST CS - SOICT-HUST

Decision tree to enumerate binary strings of length 3 Program in C++ (non recursive)

#include <iostream> void GenerateString( )

Try(1) ()
Sk = {0,1} using namespace std; {
int n, count,k; k=1; s[k]=0;
int a[100], s[100]; while (k > 0)
0 1 {
void PrintSolution() while (s[k] <= 1)
(0) Try(2) Try(2) (1) { {
1 int i, j; a[k]=s[k];
0 1 0 count++; s[k]=s[k]+1;
(00) (01) Try(3) (10) Try(3) (11) cout<<“String # " << count<<": "; if (k==n) PrintSolution();
Try(3) Try(3)
for (i=1 ; i<= n ;i++) else
0 1 0 1 0 1 0 1
cout<<a[i]<<" "; {
k++; s[k]=0;
(000) (001) (010) (011) (100) (101) (110) (111) cout<<endl; }
} }
k--; // BackTrack
}
NGUYỄN KHÁNH PHƯƠNG
CS - SOICT-HUST
}

29
Program in C++ (non recursive) Backtracking (Thuật toán quay lui)
int main() { 3.1. Algorithm diagram
cout<<“Enter value of n = ";cin>>n;
count = 0; GenerateString(); 3.2. Generate basic combinatorial configurations
cout<<“Number of strings = "<<count<<endl;
– Generate binary strings of length n
}
– Generate m-element subsets of the set of n elements
– Generate permutations of n elements

NGUYỄN KHÁNH PHƯƠNG NGUYỄN KHÁNH PHƯƠNG

CS - SOICT-HUST CS - SOICT-HUST

Example 2. Generate m-element subsets of the set of n elements Example 2. Generate m-element subsets of the set of n elements

Problem: Enumerate all m-element subsets of the set n elements N = We consider how to solve two issue keys to implement backtracking:
{1, 2, ..., n}. • Build candidate set Sk:
 With the condition: : 1  a1 < a2 < ... < am  n
Example: Enumerate all 3-element subsets of the set 5 elements N = {1, 2, 3, 4, 5} we have S1 = {1, 2, ..., n-(m-1) }.
Solution: (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3,  Assume the current subset is (a1, ..., ak-1), with the condition ak-1 <
5), (2, 4, 5), (3, 4, 5) ak < . . . < am ≤ n, we have Sk = {ak-1+1, ak-1+2, ..., n-(m-k)}.
• Implement the loop to enumerate all elements of Sk: we can
use the loop for
 Equivalent problem: Enumerate all elements of set: for (j=a[k-1]+1;j<=n-m+k;j++)
S(m,n)={(a1,..., am)Nm: 1 ≤ a1<...<am≤ n}

NGUYỄN KHÁNH PHƯƠNG NGUYỄN KHÁNH PHƯƠNG

CS - SOICT-HUST CS - SOICT-HUST

30
Program in C++ (Recursive) Program in C++ (Non Recursive)
#include <iostream> void MSet()
using namespace std; {
#include <iostream> void Try(int k){ k=1; s[k]=1;
using namespace std; int j; int n, m, count,k; while(k>0){
for (j = a[k-1] +1; j<= n-m+k; j++) {
int a[100], s[100]; while (s[k]<= n-m+k) {
int n, m, count; a[k] = j;
if (k==m) PrintSolution(); void PrintSolution() { a[k]=s[k]; s[k]=s[k]+1;
int a[100]; int i; if (k==m) PrintSolution();
else Try(k+1);
void PrintSolution() { } count++; else { k++; s[k]=a[k-1]+1; }
int i; } cout<<“The subset #" <<count<<": "; }
count++; int main() { for (i=1 ; i<= m ;i++) k--;
cout<<“The subset #" <<count<<": "; cout<<“Enter n, m = "; cin>>n; cin>>m; cout<<a[i]<<" "; }
for (i=1 ; i<= m ;i++) a[0]=0; count = 0; Try(1); cout<<endl; }
cout<<a[i]<<" "; cout<<“Number of "<<m<<“-element } int main() {
subsets of set "<<n<<“ elements =
cout<<endl; "<<count<<endl; cout<<“Enter n, m = "; cin>>n; cin>>m;
} } a[0]=0; count = 0; MSet();
cout<<“Number of "<<m<<“-element
subsets of set "<<n<<“ elements =
"<<count<<endl;
}

Decision tree S(5,3) Backtracking (Thuật toán quay lui)

Try(1); () 3.1. Algorithm diagram

3.2. Generate basic combinatorial configurations
1 3
2
– Generate binary strings of length n
(1) Try(2) (2) Try(2)
Try(2)
(3) – Generate m-element subsets of the set of n elements
2
3
4
3 4
4 – Generate permutations of n elements
Try(3) Try(3)
Try(3)
(1,2) Try(3) (1,3) Try(3) (1,4) (2,3) Try(3) (2,4)
(3,4)
3 4 5 5 5 4 5 5 5
4

(1,2,3) (1,2,4) (1,2,5) (1,3,4) (1,3,5) (1,4,5) (2,3,4) (2,3,5) (2,4,5) (3,4,5)

Sk = {ak-1+1, ak-1+2, ..., n-(m-k)}

NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN

31
Example 3. Enumerate permutations Example 3. Enumerate permutations
Permutation set of natural numbers 1, 2, ..., n is the set: • Build candidate set Sk:
n = {(x1,..., xn)  Nn: xi ≠ xj , i ≠ j }. – Actually S1 = N. Assume we have current partial permutation (a1,
a2, ..., ak-1), with the condition ai ≠ aj, for all i ≠ j , we have
Sk = N \ { a1, a2, ..., ak-1}.
Problem: Enumerate all elements of n

NGUYỄN KHÁNH PHƯƠNG NGUYỄN KHÁNH PHƯƠNG

CS - SOICT-HUST CS - SOICT-HUST

Describe Sk Example 3. Enumerate permutations

Build function to detect candidates: • Implement the loop to enumerate all elements of Sk:

for (j=1; j <= n; j++;)

bool candidate(int j, int k) if (candidate(j, k))
{ {
//function returns true if and only if j  Sk // j is candidate for position kth
int i; . . .
for (i=1;i++;i<=k-1) }
if (j == a[i]) return false;
return true;
}

32
Program in C++ (Recursive) Program in C++ (Recursive)
#include <iostream> bool candidate(int j, int k) void Try(int k)
using namespace std; { {
int i;
for (i=1; i<=k-1; i++) int j;
int n, m, count; if (j == a[i]) for (j = 1; j<=n; j++)
int a[100]; return false;
return true; if (candidate(j,k))
int PrintSolution() {
} { a[k] = j;
int i, j; if (k==n) PrintSolution( );
count++; else Try(k+1);
cout<<“Permutation #"<<count<<": "; }
for (i=1 ; i<= n ;i++) }
cout<<a[i]<<" ";
int main() {
cout<<endl;
} cout<<(“Enter n = "); cin>>n;
count = 0; Try(1);
cout<<“Number of permutations = " << count;
}

Decision tree to enumerate permutations of 1, 2, 3 Contents

Try(1);
() 1. Brute force
S1 = ? 2. Recursion
1 2 3
3. Backtracking
(1) (2) (3)
S2 = ?
2 3 1
4. Divide and conquer
1 3 2
(1,2) (1,3) (2,1) (2,3) (3,1) 5. Dynamic programming
(3,2)
S3 = ? 3 1
3 2 2 1

(1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1)

Sk = N \ { a1, a2, ..., ak-1} NGUYỄN KHÁNH PHƯƠNG 132

CS - SOICT-HUST

33
4. Divide and conquer 4.1. Algorithm diagram
• Divide and Conquer (Chia để trị): consists of 3 operations:
4.1. Algorithm diagram – Divide: Decompose the given problem S into some problems of
same form but with smaller input size (called a subproblem) S1,
4.2. Some illustrative examples S 2, …
– Conquer: Solve subproblem recursively
– Combine: Synthesize the solutions of subproblems S1, S2,.. to
obtain the solution of the original problem S.

• If the subproblem is small enough to be easily solved, then we

solve it directly, otherwise: the subproblem is solved again by
applying the above procedure recursively (i.e. dividing it again
into smaller problem). Therefore, the divide and conquer
algorithm is recursive algorithm => to analysis the complexity of
the algorithm we can use recursive formula.
NGUYỄN KHÁNH PHƯƠNG 133 NGUYỄN KHÁNH PHƯƠNG 134
CS - SOICT-HUST CS - SOICT-HUST

4.1. Algorithm diagram 4.1. Algorithm diagram

To get a detailed description of the divide and conquer algorithm, we need to define:
• Critical size n0 (problems with size less than n0 don’t need subdivision)
• Dimensions of each subproblem
• Number of subproblems
• Algorithm for synthesizing solutions of subproblems.

procedure D-and-C(n)
begin Let T(n) be the computation time of the algorithm to solve the problem of size n
if (n ≤ n0) then • D(n): time to divide
Solve the problem directly
• C(n): time to synthesize the solutions
else
begin Then
Divide the problem into K subproblems of size n/b 𝑐 𝑤ℎ𝑒𝑛 𝑛 ≤ 𝑛
for (each subproblem in K subproblems) do D-and-C(n/b) 𝑇 𝑛 = 𝑛
𝑘𝑇 + 𝐷 𝑛 + 𝐶 𝑛 𝑤ℎ𝑒𝑛 𝑛 > 𝑛
Synthesize the solutions of K subproblems to obtain the 𝑏
solution of the problem with size n.
where c is the constant
end; NGUYỄN KHÁNH PHƯƠNG135 136
Bộ môn KHMT – ĐHBK HN
end;

34
Example. 4. Divide and conquer
procedure D-and-C(int n)
4.1. Algorithm diagram
begin
if (n == 0) return; 4.2. Some illustrative examples
D-and-C(n/2);
– Example 1. Binary search
D-and-C(n/2);
for (int i =0 ; i < n; i++) – Example 2. Multiply integer numbers
begin
Perform operations requires constant time
end;
end;

What is the computation time of this procedure ?

137 NGUYỄN KHÁNH PHƯƠNG 138

CS - SOICT-HUST

Example 1: Binary Search 4. Divide and conquer

Input: An array S consists of n elements: S[0],…,S[n-1] in ascending order; Value key with the
same data type as array S. 4.1. Algorithm diagram
Output: the index in array if key is found, -1 if key is not found
• Binary search algorithm: The value key either
4.2. Some illustrative examples
– equals to the element at the middle of the array S, – Example 1. Binary search
– or is at the left half (L) of the array S,
– Example 2. Multiply integer numbers
– or is at the right half (R) of the array S.
(The situation L (R) happen only when key is smaller (larger) than the element at the
middle of the array S)

NGUYỄN KHÁNH PHƯƠNG 140

What is the computation time of binary search ? CS - SOICT-HUST

35
Example 2. Multiply 2 integer numbers Example 2. Multiply 2 integer numbers
• Problem: Given
x = xn-1 xn-2 ... x1 x0 and
9 8 1 y = yn-1 yn-2 ... y1 y0
• If each operand has n digits, then
1 2 3 4 computation time is (n2) 2 positive integer numbers with n digits. We need to calculate
3 9 2 4 • Is there a better way?
z = z2n-1 z2n-2 ... z1 z0
2 9 4 3 representing product of xy with 2n digits.

1 9 6 2
9 8 1
1 2 1 0 5 5 4

NGUYỄN KHÁNH PHƯƠNG 141 142

CS - SOICT-HUST

Example 2. Multiply 2 integer numbers - Karatsuba algorithm (1962) Example 2. Multiply 2 integer numbers - Karatsuba algorithm (1962)

• We have: x = xn-1 xn-2 ... x1 x0 và y = yn-1 yn-2 ... y1 y0 We have: x = xn-1 xn-2 ... x1 x0 và y = yn-1 yn-2 ... y1 y0
• Set: Then:


• Thus: z = z2n-1 z2n-2 ... z1 z0 = x * y • So:

To calculate ac, ad, bc, bd we must perform 4

multiplications of two n/2-digit numbers.
The given problem requires multiplication of two n-digit
numbers (x and y): is transferred to problem of calculating 4
143 multiplications of two n/2-digit numbers 144

36
Example 2. Multiply 2 integer numbers - Karatsuba algorithm (1962) Example 2. Multiply 2 integer numbers - Karatsuba algorithm (1962)

• Basic case: The multiplication of two 1-digit integers can be done Karatsuba discovered how to perform 2 integer n-digit numbers
directly; multiplication requires only 3 multiplications of n/2-digit
• Divide: if n>1 then the product of 2 integers with n digits can be numbers as following:
represented through 4 products of 4 integer numbers with n/2 digits: a*c, • Set: U = ac, V = bd, W =(a+b)(c+d)
a*d, b*c, b*d
Then: ad + bc = W – U – V,
• Combine: to calculate z = xy when we already know the above 4
products, we only need to perform additions (can be done in O(n)) and And calculate:
multiply with power of 10 (can be done in O(n), by inserting an z = x*y = (a10n/2 +b)  (c10n/2 +d)
appropriate number of digits 0 to the right). = (ac) 10n + (ad + bc) 10n/2 + bd
= U10n + (W-U-V)10n/2 + V.

• Evaluate the computation time T(n) of the algorithm:

T(1) =1, n = 1
Is it possible to
T(n) = 4T(n/2) + n, n>1
2
Using the master theorem: T(n) = O(n )
speed up??
145 146

Karatsuba algorithm Contents

function Karatsuba(x, y, n)
begin 1. Brute force
if n=1 then return x[0]*y[0]
else 2. Recursion
begin
a:= x[n-1] ... x[n/2]; 3. Backtracking
b:= x[n/2 -1] ... x[0];
c:= y[n-1] ... y[n/2]; 4. Divide and conquer
d:= y[n/2-1] ... y[0];
U:= Karatsuba(a, c, n/2); 5. Dynamic programming
V:= Karatsuba(b, d, n/2);
W:= Karatsuba(a+b, c+d, n/2);
return U*10n + (W-U-V)*10n/2 + V;
end;
end;
Evaluate the computation time T(n) of the algorithm:
T(1) =1, n = 1
T(n) = 3T(n/2) + cn, n>1
Using the master theorem: T(n) = O(𝑛 )
148
As log23=1.585 < 2 already speed up

37
5. Dynamic programming 5.1. Algorithm diagram
The development of algorithm based on dynamic programming consists of 3 phases:
5.1. Algorithm diagram • Decomposition:
– Divide the problem into smaller subproblems so that the smallest problem
5.2. Some illustrative examples subproblem can be solved directly.
– The original problem itself can be considered as the largest subproblem of this
family of subproblems.
• Store the solutions:
– Store the solutions of subproblems in a table. This is necessary because the
solution of subproblems is often reused many times, and it improves the
efficiency of the algorithm by not having to solve the same problem repeatedly.

• Combine solutions:
– From the solution of smaller subproblems, in turn, seek to construct the solution
of the problem of the larger size, until the solution of the original problem
(which is the subproblem of the largest size) is obtained.

149 NGUYỄN KHÁNH PHƯƠNG 150

CS - SOICT-HUST

5.1. Dynamic programming Algorithm diagram 5.1. Dynamic programming Algorithm diagram
There are many similarities with the Divide and Conquer: • The technique of solving subproblems of dynamic programming is
• Divide and conquer: a bottom-up process: small-sized subproblems are solved first,
– Divide the given problem into independent subproblems then use the solution of these subproblems to build the solution of
– Solve each subproblem (by recursion) the larger problem;
– Combine solutions of subproblems into solutions of given problems. • Divide and conquer method: big problems are broken down into
• Dynamic programming: subproblems, and subproblems are treated recursively (top-down).
– Divide the given problem into overlapping subproblems
– Solve each subproblem (by recursion)
– Combine solutions of subproblems into solutions of given problem.
– Each subproblem is only solved once by saving the solution in a table
and when the subproblem is called again, just look up the solution in
the table. NGUYỄN KHÁNH PHƯƠNG151 NGUYỄN KHÁNH PHƯƠNG 152
CS - SOICT-HUST CS - SOICT-HUST

38
Dynamic programming diagram Example: Fibonacci sequence
1. Find dynamic progamming formula for problems based on subproblems The first two numbers in the Fibonacci sequence are 1 and 1. The remaining numbers in the
sequence are calculated by the sum of the two numbers immediately preceding it in the sequence.
2. Implement dynamic programming formula: convert the formula into a recursive
function Requirements: Find the nth Fibonacci number.
3. Storing the results of calculation functions 1. Find dynamic programming formula
Comment: 1st step is difficult and most improtant. To perform 2nd and 3rd steps, we can 𝑓𝑖𝑏𝑜𝑛𝑎𝑐𝑐𝑖 1 = 1
𝑓𝑖𝑏𝑜𝑛𝑎𝑐𝑐𝑖 2 = 1
apply the following general scheme: 𝑓𝑖𝑏𝑜𝑛𝑎𝑐𝑐𝑖 𝑛 = 𝑓𝑖𝑏𝑜𝑛𝑎𝑐𝑐𝑖 𝑛 − 2 + 𝑓𝑖𝑏𝑜𝑛𝑎𝑐𝑐𝑖 𝑛 − 1

2. Implement dynamic programming formula

Complexity: exponential ~ O(2n)

NGUYỄN KHÁNH PHƯƠNG 153 NGUYỄN KHÁNH PHƯƠNG 154

CS - SOICT-HUST CS - SOICT-HUST

Example: Fibonacci sequence Example: Fibonacci sequence

3. Store the results of calculation functions

What is the complexity?

When call Fibonacci(n): there are n possibilities for input to the function: 1, 2, …, n
For each input:
• Either the result is taken directly from table if it has been calculated before: O(1) if
assume taking a value from memory just requires O(1)
• Or need to calculate the result and then store it: O(1) if assume each recursive call
and summing only take a constant amount of time
Each input is called up to 1 time
NGUYỄN KHÁNH PHƯƠNG 155
CS - SOICT-HUST
Total time is O(n) NGUYỄN KHÁNH PHƯƠNG 156
CS - SOICT-HUST

39
5. Dynamic programming Example 1: The maximum subarray problem
5.1. Algorithm diagram • Given an array of n numbers:

a1, a2, … , an
5.2. Some illustrative examples
The contiguous subarray ai, ai+1 , …, aj with 1 ≤ i ≤ j ≤ n is a subarray of
– Example 1. Maximum subarray problem the given array and ∑ 𝑎 is called as the value of this subarray
– Example 2. Longest common subsequence The task is to find the maximum value of all possible subarrays, in other
– Example 3. Travelling salesman problem words, find the maximum ∑ 𝑎 . The subarray with the maximum value is
called as the maximum subarray.
Example: Given the array -2, 11, -4, 13, -5, 2 then the maximum subarray is
11, -4, 13 with the value = 11+ (-4)+13 =20

157 158

Example 1: The maximum subarray problem Dynamic programming for maximum subarray problem

1.1.1. Brute force

1.1.2. Brute force with better implement

Step 1. Find dynamic programming formula
• Let max_sum(i) the value of maximum subarray of array a1, a2, ..., ai , i = 1, .., n.
1.1.3 Recursive algorithm • Basic case: max_sum(1) = max(0, a[1])
n log n • Find recursive formula for max_sum(i) = ?
– Relate to max_sum(i-1) ?
1.1.4. Dynamic programming – Is it possible to construct solution of problem size i from the solutions of problems size less than i
?
n

Let max_sum(i) be the value of the maximum subarray of array a1, a2, ..., ai , and
this subarray ends at ai (this subarray includes ai)
159 NGUYỄN KHÁNH PHƯƠNG 160
CS - SOICT-HUST

40
Dynamic programming for maximum subarray problem Dynamic programming for maximum subarray problem

Step 1. Find dynamic programming formula Step 2. Implement dynamic programming formula
• Let max_sum(i) the value of maximum subarray of array a1, a2, ...,
ai , i = 1, .., n and this subarray ends at ai (this subarray includes ai)
• Basic case: max_sum(1) = a[1]
• Find recursive formula for max_sum(i)
max_sum(i)= max(a[i], a[i] + max_sum(i-1))

Solution to problem: max max _𝑠𝑢𝑚(𝑖)

NGUYỄN KHÁNH PHƯƠNG 161 NGUYỄN KHÁNH PHƯƠNG 162

CS - SOICT-HUST CS - SOICT-HUST

Dynamic programming for maximum subarray problem The maximum subarray problem
In the main function, we need to call max_sum(n); this function will
calculate all values max_sum(i) for all 1 ≤ i ≤ n
Then, solution to the problem is the maximum of the max_sum(i) values
already stored in array mem[i]

Step 3. Storing the results of calculation functions

maximum = *max_element(mem+1, mem+n+1);

NGUYỄN KHÁNH PHƯƠNG 163 NGUYỄN KHÁNH PHƯƠNG 164

CS - SOICT-HUST CS - SOICT-HUST

41
Dynamic programming for maximum subarray problem The max subarray problem: Trace

Complexity ? How to know max subarray consists which elements?

When call max_sum(n): there are n possibilities input for function: 1, 2, …, n • Method 1: Trace using recursion
For each input:
• Either the result is taken directly from table if it has been calculated before: O(1) if
assume taking a value from memory just requires O(1)
• Or need to calculate the result and then store it: O(1) if assume each recursive call
and function max only take a constant amount of time
Each input is called up to 1 time
Total time is O(n) NGUYỄN KHÁNH PHƯƠNG 165
CS - SOICT-HUST
166

5. Dynamic programming Longest common subsequence ( LCS)

Given the sequence of n elements A = <a0, a1, ..., an-1>
5.1. Algorithm diagram Definition of subsequence: if you delete 0 element or some elements of sequence A then you will
get a sequence of A.
5.2. Some illustrative examples • Example: A = [5, 1, 8, 1, 9, 2]
– Some subsequence of A:
– Example 1. Maximum subarray problem • [5, 1, 8, 1, 9, 2]
• [5, 8, 9]
– Example 2. Longest common subsequence • [1, 1]
• []
– Not subsequence of A:
• [2, 5]
• [10]
Given 2 sequences A and B, we say sequence Z is common subsequence of A and B if Z is
subsequence of both A and B.
LCS problem: Given 2 sequences
A = <a0, a1, …, am-1>
B = <b0, b1,…, bn-1>
Find the longest common subsequences A and B.
167 Applications: In biology, when examining genes
NGUYỄN KHÁNH PHƯƠNG 168
CS - SOICT-HUST

42
Longest common subsequence (LCS) Longest common subsequence (LCS)

Example: LCS problem: Given 2 sequences

A = <K, J, C, D, E, F, G> A = <a0, a1, …, am-1> ,
B = <b0, b1,…, bn-1> .
B = <C, C, E, D, E, G, F>
Find the longest common subsequence of A and B.
• Sequence Z = <C, D, F> is a common subsequence.
• Sequence <B, F, G> is not common subsequence.
• Direct approach:
• Sequence <C, D, E, G> is the longest common subsequence as we can not
– Browse all subquences of A  number of subsequences = 2m
find and other common subsequence with length >=5.
– For each subsequence of A, we check if it is subsequence of B. Complexity: O(n)
Complexity of direct apporach: O(n.2m)

• Dynamic programming:
Step 1. Find dynamic programming formula
– Let lcs(i,j) the length of common subsequence of Ai = <a0, a1, ...,
ai> and Bj <b0, b1, ..., bj> where -1  i  m-1 và -1  j  n-1
– Basic case: lsc(i,-1) = 0 và lsc(-1,j) = 0
NGUYỄN KHÁNH PHƯƠNG 169
CS - SOICT-HUST – Recursive function to calculate lcs(i,j)? 170

Longest common subsequence (LCS): Dynamic programming Dynamic programming: Recursive implementation
• Clearly 0, if i  -1 or j  -1,
lcs(i, -1) = 0, i = -1, 0, 1, ..., m-1 
lcs(i, j )  lcs(i  1, j  1)  1, if i, j  0 and a i  bj
lcs(-1, j) = 0, j = -1, 0, 1, ..., n-1. 
max{lcs(i, j  1), lcs(i  1, j )}, if i, j  0 and ai  bj .
• Assume i ≥ 0, j ≥ 0, we need to calculate lcs(i, j) which is length of LCS of two
sequences Ai = <a0, a1, ..., ai> and Bj <b0, b1, ..., bj>. There are 2 possibilities:
– If ai = bj :
• LCS of Ai and Bj can obtain by including ai into LCS of 2 sequences Ai-1
and Bj-1  lcs(i, j) = lcs (i-1, j-1) + 1
– If ai  bj : LCS = “aninn”
• LCS of Ai and Bj is the longest subsequence among 2 LCS of (Ai and Bj-1)
and of (Ai-1 và Bj)  lcs(i, j) = max {lcs(i, j-1), lcs (i-1, j)}
• Therefore, we get the formula to calculate lcs(i, j):

0, if i  -1 or j  -1,

lcs(i, j )  lcs(i  1, j  1)  1, if i, j  0 and a i  bj

max{lcs(i, j  1), lcs(i  1, j )}, if i, j  0 and ai  bj . 171 NGUYỄN KHÁNH PHƯƠNG 172
CS - SOICT-HUST

43
Dynamic programming: Recursive implementation LCS: Dynamic programming

In the main function, we only need to call

lcs(a.length()-1, b.length()-1);

Complexity ?
When call lcs(len(a)-1, len(b)-1): there are m*n input possibilities for
function
For each input:
• Either the result is taken directly from table if it has been calculated before: O(1) if assume
taking a value from memory just requires O(1)
• Or need to calculate the result and then store it: O(1) if assume each recursive call and
function max, summing only take a constant amount of time
Each input is called up to 1 time
NGUYỄN KHÁNH PHƯƠNG 173 174
CS - SOICT-HUST
Total time is O(m*n)

LCS: Implement using loop LCS: Trace using recursion

0, nÕu i  0 hoÆc j  0, Làm thế nào để đưa ra được dãy con chung

lcs(i, j )  lcs(i  1, j  1)  1, nÕu i, j  0 vµ a i  bj dài nhất gồm những phần tử nào ?

max{lcs(i, j  1), lcs(i  1, j )}, nÕu i, j  0 vµ ai  bj .
0, nÕu i  -1 hoÆc j  -1,

lcs(i, j )  lcs(i  1, j  1)  1, nÕu i, j  0 vµ a i  b j

max{lcs(i, j  1), lcs(i  1, j )}, nÕu i, j  0 vµ ai  bj .

• Method 1: Trace using recursion

O(m*n)

trace(a.length()-1, b.length()-1);

Question: how to know LCS consists of which elements ? 176

44
LCS: Trace using recursion LCS: Trace using loop

• Method 1: Trace using recursion Làm thế nào để đưa ra được dãy con chung
dài nhất gồm những phần tử nào ?
0, nÕu i  -1 hoÆc j  -1,

lcs(i, j )  lcs(i  1, j  1)  1, nÕu i, j  0 vµ a i  b j

max{lcs(i, j  1), lcs(i  1, j )}, nÕu i, j  0 vµ ai  bj .

• Method 2: Trace using loop

NGUYỄN KHÁNH PHƯƠNG 177 NGUYỄN KHÁNH PHƯƠNG 178

CS - SOICT-HUST CS - SOICT-HUST

45