Transcript Transform-and-conquer

ITS033 – Programming & Algorithms
Lecture 08
Transform & Conquer
Asst. Prof. Dr. Bunyarit Uyyanonvara
IT Program, Image and Vision Computing Lab.
School of Information and Computer Technology
Sirindhorn International Institute of Technology
Thammasat University
http://www.siit.tu.ac.th/bunyarit
[email protected]
02 5013505 X 2005
1
ITS033
Midterm
Topic 01 - Problems & Algorithmic Problem Solving
Topic 02 – Algorithm Representation & Efficiency Analysis
Topic 03 - State Space of a problem
Topic 04 - Brute Force Algorithm
Topic 05 - Divide and Conquer
Topic 06 - Decrease and Conquer
Topic 07 - Dynamics Programming
Topic 08 - Transform and Conquer
Topic 09 - Graph Algorithms
Topic 10 - Minimum Spanning Tree
Topic 11 - Shortest Path Problem
Topic 12 - Coping with the Limitations of Algorithms Power
http://www.siit.tu.ac.th/bunyarit/its033.php
and http://www.vcharkarn.com/vlesson/showlesson.php?lessonid=7
2
This Week Overview

Introduction

Presort

Binary Search Tree

AVL Tree

Problem reduction
3
Lecture 08.1
ITS033 – Programming & Algorithms
Transform & Conquer: Introduction
Asst. Prof. Dr. Bunyarit Uyyanonvara
IT Program, Image and Vision Computing Lab.
School of Information and Computer Technology
Sirindhorn International Institute of Technology
Thammasat University
http://www.siit.tu.ac.th/bunyarit
[email protected]
02 5013505 X 2005
4
Transform and Conquer
This group of techniques solves a problem by a
transformation

to a simpler/more convenient instance of the same
problem (instance simplification)

to a different representation of the same instance
(representation change)

to a different problem for which an algorithm is already
available (problem reduction)
5
Introduction


Transform-and-conquer
Methods work as two-stage procedures.

(1) Transformation stage: the problem’s instance is
modified to be, for one reason or another, more
amenable to solution.

(2) Conquering stage, solve it.
6
Introduction
7
Lecture 08.2
ITS033 – Programming & Algorithms
Transform & Conquer: Instance Simplification
Asst. Prof. Dr. Bunyarit Uyyanonvara
IT Program, Image and Vision Computing Lab.
School of Information and Computer Technology
Sirindhorn International Institute of Technology
Thammasat University
http://www.siit.tu.ac.th/bunyarit
[email protected]
02 5013505 X 2005
8
Instance simplification - Presorting
Solve a problem’s instance by transforming it into
another simpler/easier instance of the same problem
Presorting
Many problems involving lists are easier when list is sorted.
 searching
 computing the median (selection problem)
 checking if all elements are distinct (element uniqueness)
Also:
 Topological sorting helps solving some problems for dags.
 Presorting is used in many geometric algorithms.
9
Searching with presorting
Problem: Search for a given K in A[0..n-1]
Presorting-based algorithm:
Stage 1 Sort the array by an efficient sorting algorithm
Stage 2 Apply binary search
Efficiency: O(nlog n) + O(log n) = O(nlog n)
Good or bad?
Why do we have our dictionaries, telephone directories, etc. sorted?
10
Element Uniqueness with presorting

Presorting-based algorithm
Stage 1: sort by efficient sorting algorithm (e.g. mergesort)
Stage 2: scan array to check pairs of adjacent elements
Efficiency: O(nlog n) + O(n) = O(nlog n)

Brute force algorithm
Compare all pairs of elements
Efficiency: O(n2)
11
Example 1

Checking element uniqueness in an array
ALGORITHM PresortElementUniqueness(A[0..n - 1])
//Solves the element uniqueness problem by sorting the array first
//Input: An array A[0..n - 1] of orderable elements
//Output: Returns “true” if A has no equal elements, “false”
// otherwise
Sort the array A
for i  0 to n - 2 do
if A[i]= A[i + 1] return false
return true
12
Lecture 08.3
ITS033 – Programming & Algorithms
Transform & Conquer: Representation Change
Asst. Prof. Dr. Bunyarit Uyyanonvara
IT Program, Image and Vision Computing Lab.
School of Information and Computer Technology
Sirindhorn International Institute of Technology
Thammasat University
http://www.siit.tu.ac.th/bunyarit
[email protected]
02 5013505 X 2005
13
Searching Problem
Problem: Given a (multi)set S of keys and a search
key K, find an occurrence of K in S, if any

Searching must be considered in the context of:
 file size (internal vs.
external)
 dynamics of data (static vs. dynamic)

Dictionary operations (dynamic data):
 find (search)
 insert
 delete
14
Tree Characteristics
§- trees

hierarchical structures that place elements in nodes along
branches that originate from a root.

Nodes in a tree are subdivided into levels in which the topmost
level holds the root node.

Any node in a tree may have multiple successors at the next level.
Hence a tree is a non-linear structure.
15
Tree Structures
President-CEO
Production
Manager
Personnel
Manager
Purchasing
Supervisor
Warehouse
Supervisor
Sales
Manager
Shipping
Supervisor
HIERARCHICAL TREE STRUCTURE
16
Binary Tree: Formal Definition
A binary tree T is a finite set of nodes with one of the following
properties:
a.) T is a tree if the set of nodes is empty.
(An empty tree is a tree.)
b.) The set consists of a root, R, and exactly two distinct binary
trees, the left subtree, TL and the right subtree, TR.
c.) The nodes in T consist of node R and all the nodes in TL and
TR.
17
Binary Tree: example
18
Binary Tree
19
Binary Tree: Depth
20
Selected Samples of Binary Trees
A
A
B
B
C
C
D
E
F
G
D
H
I
Tree A
Size 9 Depth 3
E
Tree B
Size 5 Depth 4
21
Binary Search Trees

Binary Search Tree (BSTs) is a binary tree which
has following properties:
 Element to
the left of the parent is always
smaller than its parents.
 Element to
the right of the parent is always
greater than its parent.
22
Binary Search Tree
Arrange keys in a binary tree with the binary search tree
property:
K
<K
>K
Example: 5, 3, 1, 10, 12, 7, 9
23
Operations of BSTs: Insert

Adds an element x to the tree so that the binary search tree
property continues to hold

The basic algorithm





set the Index to Root
Check if the data where index is pointing is NULL, if so
Insert x in place of NULL, and finish the process.
If the data is not NULL then compare the data with inserting
item
If the inserting item is equal or bigger then traverse to the
right else traverse to the left.
Continue with 2nd step again until
24
Insert Operations: 1st of 3 steps
1)- The function begins at the root node and compares
item 32 with the root value 25. Since 32 > 25, we
traverse the right subtree and look at node 35.
parent
25
20
12
t
35
40
(a)
Step 1: Compare 32 and 25.
Traverse the right subtree.
25
Insert Operations: 2nd of 3 steps
2)- Considering 35 to be the root of its own subtree, we
compare item 32 with 35 and traverse the left subtree of
35.
25
12
parent
35
20
t
40
(b)
Step 2: Compare 32 and 35.
Traverse the left subtree.
26
Insert Operations: 3rd of 3 steps
3)- Create a leaf node with data value 32.
Insert the new node as the left child of node
35.
25
newNode = new Node;
parent->left = newNode;
20
12
parent
35
32
40
(c)
Step 3: Insert 32 as left child
of parent 35
27
Insert in BST
Insert
Key 52.
Start at root.
52 > 51
Go right.
51
14
72
06
33
13
25
53
43
97
64
84
99
28
Insert in BST
Insert
Key 52.
52 > 51
Go right.
51
14
72
06
33
13
25
53
43
97
64
84
99
29
Insert in BST
Insert
Key 52.
51
14
06
33
13
72
52 < 72
Go left.
25
53
43
97
64
84
99
30
Insert in BST
Insert
Key 52.
51
14
06
33
13
72
52 < 72
Go left.
25
53
43
97
64
84
99
31
Insert in BST
Insert
Key 52.
51
14
72
06
33
13
25
52 < 53
Go left.
43
53
97
64
84
99
32
Insert in BST
Insert
Key 52.
51
14
06
33
13
72
No more tree here.
INSERT HERE
25
53
52 < 53
Go left.
43
52
97
64
84
99
33
Operations of BSTs: Search

looks for an element x within the tree

The basic algorithm

Set the index to root
 Compare the searching item with the data at index

If (the searching item is smaller) then traverse to the left else
traverse to the right.

Repeat the process untill the index is point to NULL or found
the item.
34
Search in BST
Search
for Key 43.
51
14
72
06
33
13
25
53
43
97
64
84
99
35
Search in BST
Search
for Key 43.
Start at root.
43 < 51
Go left.
51
14
72
06
33
13
25
53
43
97
64
84
99
36
Search in BST
Search
for Key 43.
43 < 51
Go left.
51
14
72
06
33
13
25
53
43
97
64
84
99
37
Search in BST
Search
for Key 43.
51
14
72
43 > 14
Go right.
06
33
13
25
53
43
97
64
84
99
38
Search in BST
Search
for Key 43.
51
14
72
43 > 14
Go right.
06
33
13
25
53
43
97
64
84
99
39
Search in BST
Search
for Key 43.
51
14
72
06
33
13
25
43 > 33
Go right.
43
53
97
64
84
99
40
Search in BST
Search
for Key 43.
51
14
72
06
33
13
25
43 > 33
Go right.
43
53
97
64
84
99
41
Search in BST
Search
for Key 43.
51
14
72
06
33
13
25
53
43
43 = 43
FOUND
97
64
84
99
42
Search in BST
Search
for Key 52.
Start at root.
52 > 51
Go right.
51
14
72
06
33
13
25
53
43
97
64
84
99
43
Search in BST
Search
for Key 52.
52 > 51
Go right.
51
14
72
06
33
13
25
53
43
97
64
84
99
44
Search in BST
Search
for Key 52.
51
14
06
33
13
72
52 < 72
Go left.
25
53
43
97
64
84
99
45
Search in BST
Search
for Key 52.
51
14
06
33
13
72
52 < 72
Go left.
25
53
43
97
64
84
99
46
Search in BST
Search
for Key 52.
51
14
72
06
33
13
25
52 < 53
Go left.
43
53
97
64
84
99
47
Search in BST
Search
for Key 52.
51
14
72
06
33
13
25
52 < 53
Go left.
53
43
No more tree here.
NOT FOUND
97
64
84
99
48
Tree Walk

Tree walk is a series of steps used to traverse a given tree.

inorder tree walk – is a tree walk with following steps
+ left sub-tree
+ middle node
+ right sub-tree
49
Binary Tree: example
50
Tree Structures
+
*
a
/
e
-
b
c
BINARY EXPRES S ION TREE FOR
d
"a*b + (c-d) / e "
51
In-order Tree Walk

What does the following code do?
TreeWalk(x)
TreeWalk(left[x]);
print(x);
TreeWalk(right[x]);

A: prints elements in sorted (increasing) order
This is called an inorder tree walk
 Preorder tree walk: print root, then left, then right
 Postorder tree walk: print left, then right, then root

52
Lecture 08.4
ITS033 – Programming & Algorithms
Transform & Conquer: problem reduction
Asst. Prof. Dr. Bunyarit Uyyanonvara
IT Program, Image and Vision Computing Lab.
School of Information and Computer Technology
Sirindhorn International Institute of Technology
Thammasat University
http://www.siit.tu.ac.th/bunyarit
[email protected]
02 5013505 X 2005
53
Problem Reduction
This variation of transform-and-conquer solves a problem
by a transforming it into different problem for which an
algorithm is already available.
To be of practical value, the combined time of the
transformation and solving the other problem should be
smaller than solving the problem as given by another
method.
54
Problem Reduction

Problem reduction: If you need to solve a problem, reduce it to
another problem that you know how to solve
55
Reduction to Graph Problems

Vertices of a graph typically represent possible states of the problem
in question while edges indicate permitted transitions among such
states.

One of the graph’s vertices represents an initial state, while another
represents a goal state of the problem. Such a graph is called a
state-space graph.

Thus, the transformation just described reduces the problem to the
question about a path from the initial-state vertex to a goal-state
vertex.
56
Example

A peasant finds himself on a river bank with a wolf, a goat, and a
head of cabbage. He needs to transport all three to the other side of
the river in his boat. However, the boat has room only for the
peasant himself and one other item (either the wolf, the goat, or the
cabbage). In his absence, the wolf would eat the goat, and the goat
would eat the cabbage. Find a way for the peasant to solve his
problem or prove that it has no solution.
57
Example




P, w, g, c stand for the peasant, the wolf,
the goat, and the cabbage, respectively;
the two bars | | denote the river;
there exist two distinct simple paths from
the initial state vertex to the final state
vertex.
Hence, this puzzle has two solutions, each
of which requires seven river crossings.
58
Homework
S = {1, 5, 3, 4, 8, 6, 7, 8, 4, 2, 1, 9, 11, 12,15, 14}
1. Construct a Binary Search Tree from the given set S
2. Construct a AVL Tree from the given set S
59
ITS033
Midterm
Topic 01 - Problems & Algorithmic Problem Solving
Topic 02 – Algorithm Representation & Efficiency Analysis
Topic 03 - State Space of a problem
Topic 04 - Brute Force Algorithm
Topic 05 - Divide and Conquer
Topic 06 - Decrease and Conquer
Topic 07 - Dynamics Programming
Topic 08 - Transform and Conquer
Topic 09 - Graph Algorithms
Topic 10 - Minimum Spanning Tree
Topic 11 - Shortest Path Problem
Topic 12 - Coping with the Limitations of Algorithms Power
http://www.siit.tu.ac.th/bunyarit/its033.php
and http://www.vcharkarn.com/vlesson/showlesson.php?lessonid=7
60
End of Chapter 8
Thank you!
61