Design, Analysis and
Implementation of Algorithms
Pham Quang Dung and Do Phan Thuan
Computer Science Department, SoICT,
Hanoi University of Science and Technology.
September 4, 2017
1 / 5
Introduction
Questions you may have
I
What are algorithms?
I
Why do we learn this course?
General answer
I
Algorithms: A well-defined computational procedure that takes a set
of values as input and produces a set of values as output
I
Objectives of the course
F
Skills: Design, analysis and implementation of algorithms
2 / 5
Introduction
Questions you may have
I
What are algorithms?
I
Why do we learn this course?
General answer
I
Algorithms: A well-defined computational procedure that takes a set
of values as input and produces a set of values as output
I
Objectives of the course
F
Skills: Design, analysis and implementation of algorithms
2 / 5
Introduction
Questions you may have
I
What are algorithms?
I
Why do we learn this course?
General answer
I
Algorithms: A well-defined computational procedure that takes a set
of values as input and produces a set of values as output
I
Objectives of the course
F
Skills: Design, analysis and implementation of algorithms
2 / 5
Plan
Basic
I
Chapter 1: Introduction to algorithms and data structures (weeks 1-2)
I
Chapter 2: Recursion, Backtracking, and Branch-and-Bound (weeks
3-5)
I
Chapter 3: Greedy algorithms (weeks 6)
I
Chapter 4: Divide-and-Conquer (week 7)
I
Chapter 5: Dynamic Programming (weeks 8-9)
I
Chapter 6: Graph algorithms and applications (weeks 10-11)
Advances
I
Chapter 7: Advanced data structures and applications (weeks 12-13)
I
Chapter 8: Algorithms on Strings and applications (week 14-15)
3 / 5
4 / 5
References
1
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to
Algorithms. Second Edition, MIT Press, 2001
2
Robert Lafore. Data structures and Algorithms in Java (2nd Edition)
Sams Publishing, 2002
5 / 5
Introduction to Data Structures
and Algorithms
Pham Quang Dung and Do Phan Thuan
Computer Science Department, SoICT,
Hanoi University of Science and Technology.
January 19, 2018
1 / 1
First example
Find the largest weight subsequence of a given sequence of numbers
Given a sequence s = ha
1
, . . . , a
n
i
a subsequence is s(i , j) = ha
i
, . . . , a
j
i, 1 i j n
weight w(s(i, j)) =
j
X
k=i
a
k
Problem: find the subsequence having largest weight
http://www.spoj.com/problems/MAXSUMSU/
Example
sequence: -2, 11, -4, 13, -5, 2
The largest weight subsequence is 11, -4, 13 having weight 20
2 / 1
How many subsequences?
Number of couple (i, j) where 1 i j n
n
2
+n
This give a direct algorithm
3 / 1
Direct algorithm O(n
3
)
Scan all possible subsequences
n
2
+n =
n
2
+n
2
Compute and keep the largest weight subsequence
1 public long algo1 ( int [] a ){
2 int n = a. length ;
3 long max = a [0];
4 for ( int i = 0; i < n; i ++){
5 for ( int j = i; j < n; j ++){
6 int s = 0;
7 for ( int k = i; k <= j ; k ++)
8 s = s + a[ k ];
9 max = max < s ? s : max ;
10 }
11 }
12 return max ;
13 }
4 / 1
Direct algorithm
Faster algorithm O(n
2
)
Observation:
P
j
k=i
a[k] = a[j] +
P
j1
k=i
a[k]
1 public long algo2 ( int [] a ){
2 int n = a. length ;
3 long max = a [0];
4 for ( int i = 0; i < n; i ++){
5 int s = 0;
6 for ( int j = i; j < n; j ++){
7 s = s + a [j ];
8 max = max < s ? s : max ;
9 }
10 }
11 return max ;
12 }
5 / 1
Divide And Conquer
Divide the sequence into 2 subsequences at the middle s = s
1
:: s
2
The largest subsequence might
I
be in s
1
or
I
be in s
2
or
I
start at some position of s
1
and end at some position of s
2
Java code:
1 pri vate long m axSeq ( int i, int j ){
2 if ( i == j ) return a [i ];
3 int m = (i +j ) /2;
4 long ml = maxSeq (i ,m );
5 long mr = maxSeq (m +1 ,j );
6 long maxL = max Left (i ,m );
7 long maxR = maxRig ht ( m+1 , j);
8 long maxL R = maxL + maxR ;
9 long max = ml > mr ? ml : mr ;
10 max = max > ma xLR ? max : m axLR ;
11 return max ;
12 }
13 public long algo3 ( int [] a ){
14 int n = a. length ;
15 return ma xSeq (0 , n -1);
16 }
6 / 1
Divide and Conquer O(n log n)
1 pri vate long m axLe ft ( int i , int j ){
2 long maxL = a[j ];
3 int s = 0;
4 for ( int k = j; k >= i ; k - -){
5 s += a[ k ];
6 maxL = maxL > s ? maxL : s ;
7 }
8 return maxL ;
9 }
10 pri vate long m axR ight ( int i, int j ){
11 long maxR = a[i ];
12 int s = 0;
13 for ( int k = i; k <= j ; k ++){
14 s += a[ k ];
15 maxR = maxR > s ? maxR : s ;
16 }
17 return maxR ;
18 }
7 / 1
Dynamic programming
General principle
Division: divide the initial problem into smaller similar problems
(subproblems)
Storing solutions to subproblems: store the solution to subproblems
into memory
Aggregation: establish the solution to the initial problem by
aggregating solutions to subproblems stored in the memory
8 / 1
Dynamic programming
Largest subsequence
Division:
I
Let s
i
be the weight of the largest subsequence of a
1
, . . . , a
i
ending at
a
i
Aggregation:
I
s
1
= a
1
I
s
i
= max{s
i1
+ a
i
, a
i
}, i = 2, . . . , n
I
Solution to the original problem is max{s
1
, . . . , s
n
}
Number of basic operations is n (best algorithm)
9 / 1
Dynamic programming O(n)
1 public long algo4 ( int [] a ){
2 int n = a. length ;
3 long max = a [0];
4 int [] s = new int [n ];
5 s [0] = a [0];
6 max = s [0];
7 for ( int i = 1; i < n; i ++){
8 if (s [i -1] > 0) s [i] = s [i -1] + a [i ];
9 else s [i] = a [i ];
10 max = max > s[ i ] ? max : s[i ];
11 }
12 return max ;
13 }
10 / 1
Analyzing algorithms
Resources (memory, bandwithd, CPU, etc.) required by the algorithms
Most concern is the computational time
Input size: number of items in the input
Running time: measured in term of the number of primitive
operations performed
11 / 1
Analyzing algorithms
algo1: T (n) =
n
3
6
+
n
2
2
+
n
3
algo2: T (n) =
n
2
2
+
n
2
algo3:
I
Count the number of addition (”+”) operation T (n)
T (n) =
(
0 if n = 1
T (
n
2
) + T (
n
2
) + cn if n > 1
I
By induction: T (n) = n c logn
algo4: T (n) = c n
12 / 1
Analyzing algorithms
Worst-case running time: the longest running time for any input of
size n
Best-case running time: the shortest running time for any input of
size n
Average-case running time: probabilistic analysis (make assumption of
a distribution of the input) yields expected running time
13 / 1

Preview text:

Design, Analysis and Implementation of Algorithms
Pham Quang Dung and Do Phan Thuan
Computer Science Department, SoICT,
Hanoi University of Science and Technology. September 4, 2017 1 / 5 General answer
I Algorithms: A well-defined computational procedure that takes a set
of values as input and produces a set of values as output I Objectives of the course
F Skills: Design, analysis and implementation of algorithms Introduction Questions you may have I What are algorithms? I Why do we learn this course? 2 / 5 I Objectives of the course
F Skills: Design, analysis and implementation of algorithms Introduction Questions you may have I What are algorithms? I Why do we learn this course? General answer
I Algorithms: A well-defined computational procedure that takes a set
of values as input and produces a set of values as output 2 / 5 Introduction Questions you may have I What are algorithms? I Why do we learn this course? General answer
I Algorithms: A well-defined computational procedure that takes a set
of values as input and produces a set of values as output I Objectives of the course
F Skills: Design, analysis and implementation of algorithms 2 / 5 Plan Basic
I Chapter 1: Introduction to algorithms and data structures (weeks 1-2)
I Chapter 2: Recursion, Backtracking, and Branch-and-Bound (weeks 3-5)
I Chapter 3: Greedy algorithms (weeks 6)
I Chapter 4: Divide-and-Conquer (week 7)
I Chapter 5: Dynamic Programming (weeks 8-9)
I Chapter 6: Graph algorithms and applications (weeks 10-11) Advances
I Chapter 7: Advanced data structures and applications (weeks 12-13)
I Chapter 8: Algorithms on Strings and applications (week 14-15) 3 / 5 4 / 5 References 1
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to
Algorithms. Second Edition, MIT Press, 2001 2
Robert Lafore. Data structures and Algorithms in Java (2nd Edition) Sams Publishing, 2002 5 / 5
Introduction to Data Structures and Algorithms
Pham Quang Dung and Do Phan Thuan
Computer Science Department, SoICT,
Hanoi University of Science and Technology. January 19, 2018 1 / 1 First example
Find the largest weight subsequence of a given sequence of numbers
Given a sequence s = ha1, . . . , ani
a subsequence is s(i , j ) = hai , . . . , aj i, 1 ≤ i ≤ j ≤ n weight w (s(i , j )) = j X ak k=i
Problem: find the subsequence having largest weight
http://www.spoj.com/problems/MAXSUMSU/ Example
sequence: -2, 11, -4, 13, -5, 2
The largest weight subsequence is 11, -4, 13 having weight 20 2 / 1 How many subsequences?
Number of couple (i , j ) where 1 ≤ i ≤ j ≤ n n+n 2 This give a direct algorithm 3 / 1 Direct algorithm — O(n3)
Scan all possible subsequences n +n = n2+n 2 2
Compute and keep the largest weight subsequence 1
p u b l i c l o n g a l g o 1 ( int [] a ){ 2 int n = a . l e n g t h ; 3 l o n g max = a [ 0 ] ; 4
for ( int i = 0; i < n ; i + + ) { 5
for ( int j = i ; j < n ; j + + ) { 6 int s = 0; 7
for ( int k = i ; k <= j ; k ++) 8 s = s + a [ k ]; 9 max = max < s ? s : max ; 10 } 11 } 12 r e t u r n max ; 13 } 4 / 1 Direct algorithm Faster algorithm — O(n2) Observation: Pj a[k] = a[j ] + Pj−1 a[k] k=i k=i 1
p u b l i c l o n g a l g o 2 ( int [] a ){ 2 int n = a . l e n g t h ; 3 l o n g max = a [ 0 ] ; 4
for ( int i = 0; i < n ; i + + ) { 5 int s = 0; 6
for ( int j = i ; j < n ; j + + ) { 7 s = s + a [ j ]; 8 max = max < s ? s : max ; 9 } 10 } 11 r e t u r n max ; 12 } 5 / 1 Divide And Conquer
Divide the sequence into 2 subsequences at the middle s = s1 :: s2 The largest subsequence might I be in s1 or I be in s2 or
I start at some position of s1 and end at some position of s2 Java code: 1
p r i v a t e l o n g m a x S e q ( int i , int j ){ 2
if ( i == j ) r e t u r n a [ i ]; 3 int m = ( i + j ) / 2 ; 4
l o n g ml = m a x S e q ( i , m ); 5
l o n g mr = m a x S e q ( m +1 , j ); 6
l o n g m a x L = m a x L e f t ( i , m ); 7
l o n g m a x R = m a x R i g h t ( m +1 , j ); 8
l o n g m a x L R = m a x L + m a x R ; 9
l o n g max = ml > mr ? ml : mr ; 10
max = max > m a x L R ? max : m a x L R ; 11 r e t u r n max ; 12 } 13
p u b l i c l o n g a l g o 3 ( int [] a ){ 14 int n = a . l e n g t h ; 15
r e t u r n m a x S e q (0 , n - 1 ) ; 16 } 6 / 1
Divide and Conquer — O(n log n) 1
p r i v a t e l o n g m a x L e f t ( int i , int j ){ 2 l o n g m a x L = a [ j ]; 3 int s = 0; 4
for ( int k = j ; k >= i ; k - -){ 5 s += a [ k ]; 6
m a x L = m a x L > s ? m a x L : s ; 7 } 8 r e t u r n m a x L ; 9 } 10
p r i v a t e l o n g m a x R i g h t ( int i , int j ){ 11 l o n g m a x R = a [ i ]; 12 int s = 0; 13
for ( int k = i ; k <= j ; k + + ) { 14 s += a [ k ]; 15
m a x R = m a x R > s ? m a x R : s ; 16 } 17 r e t u r n m a x R ; 18 } 7 / 1 Dynamic programming General principle
Division: divide the initial problem into smaller similar problems (subproblems)
Storing solutions to subproblems: store the solution to subproblems into memory
Aggregation: establish the solution to the initial problem by
aggregating solutions to subproblems stored in the memory 8 / 1 Dynamic programming Largest subsequence Division:
I Let si be the weight of the largest subsequence of a1, . . . , ai ending at ai Aggregation: I s1 = a1
I si = max{si−1 + ai , ai }, ∀i = 2, . . . , n
I Solution to the original problem is max{s1, . . . , sn}
Number of basic operations is n (best algorithm) 9 / 1 Dynamic programming — O(n) 1
p u b l i c l o n g a l g o 4 ( int [] a ){ 2 int n = a . l e n g t h ; 3 l o n g max = a [ 0 ] ; 4 int [] s = new int [ n ]; 5 s [0] = a [ 0 ] ; 6 max = s [ 0 ] ; 7
for ( int i = 1; i < n ; i + + ) { 8
if ( s [ i -1] > 0) s [ i ] = s [ i -1] + a [ i ]; 9 e l s e s [ i ] = a [ i ]; 10
max = max > s [ i ] ? max : s [ i ]; 11 } 12 r e t u r n max ; 13 } 10 / 1 Analyzing algorithms
Resources (memory, bandwithd, CPU, etc.) required by the algorithms
Most concern is the computational time
Input size: number of items in the input
Running time: measured in term of the number of primitive operations performed 11 / 1 Analyzing algorithms algo1: T (n) = n3 + n2 + n 6 2 3 algo2: T (n) = n2 + n 2 2 algo3:
I Count the number of addition (”+”) operation T (n) ( 0 if n = 1 T (n) = T ( n ) + T ( n ) + cn if n > 1 2 2
I By induction: T (n) = n c logn algo4: T (n) = c n 12 / 1 Analyzing algorithms
Worst-case running time: the longest running time for any input of size n
Best-case running time: the shortest running time for any input of size n
Average-case running time: probabilistic analysis (make assumption of
a distribution of the input) yields expected running time 13 / 1