Ho Chi Minh City University of Technology

Faculty of Computer Science and Engineering

Online Instructions for

Algorithms Analysis and Design

Instructor: Dr. Vo Thi Ngoc Chau

Semester 2 – 2019-2020
 Course Outline
 Chapter 1. Fundamentals
 Chapter 2. Divide-and-Conquer Strategy
 Chapter 3. Decrease-and-Conquer Strategy
 Chapter 4. Transform-and-Conquer Strategy
 Chapter 5. Dynamic Programming and Greedy
Strategies
 Chapter 6. Backtracking and Branch-and-Bound
 Chapter 7. NP-completeness
 Chapter 8. Approximation Algorithms
2
 Ho Chi Minh City University of Technology
Faculty of Computer Science and Engineering

Online Instructions for

PART 3

Semester 2 – 2019-2020
 Chapter 2.
Divide-and-Conquer Strategy

 2.1. Divide-and-conquer strategy

 2.2. Quicksort

 2.3. Mergesort

 2.4. External sorting

 2.5. Binary search tree

4
 2.5. Binary search tree
 A binary search tree is a binary tree whose
nodes contain elements of a set of
orderable items, one element per node.
K K

5 5

X≤K 4 10 K<X X<K 4 10 K≤X

1 30 1 30

22 31 22 30

15 15

22 20

5
 2.5. Binary search tree
 When we need to search for an element of
a given value v in a binary search tree, we
do it recursively in the following manner.
 If the tree is empty, the search ends in failure.
If the tree is not empty, we compare v with the
tree's root K(r). If they match, a desired
element is found and the search can be stopped.
 Otherwise, we continue with the search in the
left subtree of the root if v < K(r) and in the
right subtree if K(r) < v.

6
 2.5. Binary search tree

 v = 15, is it in the following tree?

4 10

1 30

22 31

15

22

7
 2.5. Binary search tree

 v = 15, is it in the following tree?

X≤K 4 10 K<X

1 30

22 31

15

22

8
 2.5. Binary search tree

 v = 15, is it in the following tree?

4 10

1 30

22 31

15

22

9
 2.5. Binary search tree

 v = 15, is it in the following tree?

5 5=15 ?
4 10

1 30

22 31

15

22

10
 2.5. Binary search tree

 v = 15, is it in the following tree?

5
5<15
4 10

1 30

22 31

15

22

11
 2.5. Binary search tree

 v = 15, is it in the following tree?

4 10 10=15 ?

1 30

22 31

15

22

12
 2.5. Binary search tree

 v = 15, is it in the following tree?

4 10
10<15
1 30

22 31

15

22

13
 2.5. Binary search tree

 v = 15, is it in the following tree?

4 10

1 30 30=15 ?
22 31

15

22

14
 2.5. Binary search tree

 v = 15, is it in the following tree?

4 10

1 30
15<30
22 31

15

22

15
 2.5. Binary search tree

 v = 15, is it in the following tree?

4 10

1 30

22 31 22=15 ?

15

22

16
 2.5. Binary search tree

 v = 15, is it in the following tree?

4 10

1 30

22 31
15<22
15

22

17
 2.5. Binary search tree

 v = 15, is it in the following tree?

4 10

1 30

22 31

15 15=15 ? FOUND
22

18
 2.5. Binary search tree
 Time complexity for searching the tree of
n keys for a given query key
 Abstract operation: comparison
 Best case:
Cn = 1 = O(1)
 Average case:
Cn = 2lnn = 1.38log2n = O(log2n)
 Worst case:
Cn = n = O(n)
19
 Algorithms Analysis and Design
(CO3031)

 Chapter 2. Divide-and-conquer
 2.1. Divide-and-conquer strategy

 2.2. Quicksort

 2.3. Mergesort

 2.4. External sorting

 2.5. Binary search tree

20