23: algorithm classes and BDDs

Dynamic Programming #1 | Dynamic Programming #2 | Memoization | Greedy Algorithms

Dynamic Programming Intro: Assembly-line scheduling [1]

Assembly-line scheduling problem:
  • There are two assembly lines, normally a product goes through either one
  • Each line has n stations. Station_i on both lines has the same function
  • Station_i in different lines were created at different times and have different performance
  • Changing lines has a time cost associated with it
With rush orders, what is the fastest way through the factory using both stations?

AssemblyLine

The structure of the fastest way through the factory

We can use brute-force to calculate the fastest route using combinatorics. There are 2^n ways to choose stations so enumerating all possible ways and then finding the min time takes O(2^n) time.

But we can use dynamic programming. The optimal way to get to Station[n] is based on a subproblem: what is the optimal way to get to Station[n-1] plus the choice of switching lines or not.
  • f_total = min(f1[n], f2[n])
  • f1[n] = min(f1[n-1] + s1[n], f2[n-1] + c2[n-1] + s1[n])
  • f2[n] = min(f2[n-1] + s2[n], f1[n-1] + c1[n-1] + s2[n])
s1/s2 = time for a station to run
c1/c2 = cost of changing lines

1:  
algorithm
 
assemblyLineFastestWay(
s1, 
s2, 
c1, 
c2)

2:  
 
 
f1[
0]
 
s1[
0]
;

3:  
 
 
f2[
0]
 
s2[
0]
;

4:  
 
 
for
(
to 
n)
{

5:  
 
 
 
 
if
(
f1[
i-1]
 
s1[
i]
 
<
f2[
i-1]
 
c2[
i-1]
 
s1[
i]
)
{

6:  
 
 
 
 
 
 
f1[
i]
 
f1[
i-1]
 
s1[
i]
;

7:  
 
 
 
 
 
 
path1[
i]
 
1;

8:  
 
 
 
 
}
 
else
 
{

9:  
 
 
 
 
 
 
f1[
i]
 
f2[
i-1]
 
c2[
i-1]
 
s1[
i]
;

10: 
 
 
 
 
 
 
path1[
i]
 
2;

11: 
 
 
 
 
}

12: 
 
 
 
 
if
(
f2[
i-1]
 
s2[
i]
 
<
f1[
i-1]
 
c1[
i-1]
 
s2[
i]
)
{

13: 
 
 
 
 
 
 
f2[
i]
 
f2[
i-1]
 
s2[
i]
;

14: 
 
 
 
 
 
 
path2[
i]
 
2;

15: 
 
 
 
 
}
 
else
 
{

16: 
 
 
 
 
 
 
f2[
i]
 
f1[
i-1]
 
c1[
i-1]
 
s2[
i]
;

17: 
 
 
 
 
 
 
path2[
i]
 
1;

18: 
 
 
 
 
}

19: 
 
 
}

20: 
 
 
if
(
f1[
n-1]
 
<
 
f2[
n-1]
)
{

21: 
 
 
 
 
min_time 
f1[
n-1]
;

22: 
 
 
 
 
start_path 
path1;

23: 
 
 
}
 
else
 
{

24: 
 
 
 
 
min_time 
f2[
n-1]
;

25: 
 
 
 
 
start_path 
path2;

26: 
 
 
}

27: 

The inner part of the for loop is constant time and the loop ranges over n, so the time complexity to solve with dynamic programming is O(n).

Printing out the fastest path:
1:  
algorithm
 
assemblyLinePrintFastest(
start_path, 
path1, 
path2)

2:  
 
 
curr_line 
start_path;

3:  
 
 
for
(
to 
0)
{

4:  
 
 
 
 
int
 
line 
curr_line[
i]
;

5:  
 
 
 
 
print 
line;

6:  
 
 
 
 
if
(
line 
== 
1)
{

7:  
 
 
 
 
 
 
curr_line 
path1;

8:  
 
 
 
 
}
 
else
 
{

9:  
 
 
 
 
 
 
curr_line 
path2;

10: 
 
 
 
 
}

11: 
 
 
}


Dijkstra's algorithm for shortest paths is a similar dynamic programming example. But here note that problem specific structure can be added as long as you have optimal subproblem solutions.

Bottom's-Up Dynamic Programming: Matrix-chain Multiplication [1]

Matrix-chain Multiplication can be done in any order:
(A1(A2(A3(A4))))
(A1((A2A3)A4))
((A1A2)(A3A4))
((A1(A2A3))A4)
(((A1A2)A3)A4)

The number of multiplications is dependent on the order, but the result is the same.

For example:
Matrix Size
A1 30x35
A2 35x15
A3 15x5
A4 5x10
A5 10x20
A6 20x25

The number of multiplications is (outer1_dim * inner_dim * outer2_dim)

(A1(A2(A3(A4)))):
prev curr cost
(30x35(35x15(15x5(5x10)))) (30x35(35x15(15x10))) 750
(30x35(35x15(15x10))) (30x35(35x10)) 750 + 5250 = 6000
(30x35(35x10)) 30x10 6000 + 10500 = 16500

((A1A2)(A3A4)):
prev curr cost
(((30x35)(35x15))((15x5)(5x10))) (30x15)(15x10) 15750 + 750 = 16500
(30x15)(15x10) 30x10 16500 + 4500 = 21000

m_matrix:
MatrixChain

s_matrix:
MatrixChain

m[2,5] = min:
  • m[2,2] + m[3,5] + p1p2p5
  • m[2,3] + m[4,5] + p1p3p5
  • m[2,4] + m[5,5] + p1p4p5

m[2,5] represents the minimum way to compute the subgroup: A2-A5

Original Formula Broken out
m[2,2] + m[3,5] + p1p2p5 min(A2)+min(A3xA4xA5) + mult_of_two_mins
m[2,3] + m[4,5] + p1p3p5 min(A2xA3)+min(A4xA5) + mult_of_two_mins
m[2,4] + m[5,5] + p1p4p5 min(A2xA3xA4)+min(A5) + mult_of_two_mins

Once we compute m and s, we start at the stop of the s table and start following the k downward.

Matrix Chain Code
1:   
// matrixChain.cpp - download here

2:   

3:   
#include
 
<
vector>

4:   
#include
 
<
set>

5:   
#include
 
<
iostream>

6:   
#include
 
<
string>

7:   

8:   
class
 
Table 
{

9:   
public
:

10:  
 
 
void
 
set(
int
 
x, 
int
 
y, 
int
 
value)
;

11:  
 
 
int
 
get(
int
 
x, 
int
 
y)
;

12:  
 
 
void
 
setInfinity(
int
 
x, 
int
 
y)
;

13:  
 
 
bool
 
getInfinity(
int
 
x, 
int
 
y)
;

14:  
 
 
void
 
print(
std:
:
string 
s)
;

15:  
private
:

16:  
 
 
void
 
expand(
int
 
x, 
int
 
y)
;

17:  
 
 
std:
:
vector<
std:
:
vector<
int
>
 
>
 
m_data;

18:  
 
 
std:
:
set<
std:
:
pair<
int, 
int
>
 
>
 
m_inf;

19:  
}
;

20:  

21:  
void
 
Table:
:
expand(
int
 
x, 
int
 
y)

22:  
{

23:  
 
 
while
(
m_data.size(
)
 
<
=
 
x)
{

24:  
 
 
 
 
m_data.push_back(
std:
:
vector<
int
>
(
)
)
;

25:  
 
 
}

26:  
 
 
std:
:
vector<
int
>
&
 
row 
=
 
m_data[
x]
;

27:  
 
 
while
(
row.size(
)
 
<
=
 
y)
{

28:  
 
 
 
 
row.push_back(
0)
;

29:  
 
 
}

30:  
}

31:  

32:  
void
 
Table:
:
set(
int
 
x, 
int
 
y, 
int
 
value)

33:  
{

34:  
 
 
expand(
x, 
y)
;

35:  
 
 
m_data[
x]
[
y]
 
=
 
value;

36:  
 
 
std:
:
set<
std:
:
pair<
int, 
int
>
 
>
:
:
iterator 
iter;

37:  
 
 
iter 
=
 
m_inf.find(
std:
:
pair<
int, 
int
>
(
x, 
y)
)
;

38:  
 
 
if
(
iter 
!=
 
m_inf.end(
)
)
{

39:  
 
 
 
 
m_inf.erase(
iter)
;

40:  
 
 
}

41:  
}

42:  

43:  
int
 
Table:
:
get(
int
 
x, 
int
 
y)

44:  
{

45:  
 
 
expand(
x, 
y)
;

46:  
 
 
return
 
m_data[
x]
[
y]
;

47:  
}

48:  

49:  
void
 
Table:
:
setInfinity(
int
 
x, 
int
 
y)

50:  
{

51:  
 
 
m_inf.insert(
std:
:
pair<
int, 
int
>
(
x, 
y)
)
;

52:  
}

53:  

54:  
bool
 
Table:
:
getInfinity(
int
 
x, 
int
 
y)

55:  
{

56:  
 
 
if
(
m_inf.find(
std:
:
pair<
int, 
int
>
(
x, 
y)
)
 
=
=
 
m_inf.end(
)
)
{

57:  
 
 
 
 
return
 
false;

58:  
 
 
}

59:  
 
 
return
 
true;

60:  
}

61:  

62:  
void
 
Table:
:
print(
std:
:
string 
label)

63:  
{

64:  
 
 
std:
:
cout 
<
<
 
label 
<
<
 
std:
:
endl;

65:  
 
 
for
(
size_t
 
=
 
0;
 
<
 
m_data.size(
)
;
 
++i)
{

66:  
 
 
 
 
std:
:
vector<
int
>
 
inner 
=
 
m_data[
i]
;

67:  
 
 
 
 
for
(
size_t
 
=
 
1;
 
<
 
inner.size(
)
;
 
++j)
{

68:  
 
 
 
 
 
 
std:
:
cout 
<
<
 
inner[
j]
 
<
<
 
" "
;

69:  
 
 
 
 
}

70:  
 
 
 
 
if
(
inner.size(
)
 
!=
 
0)
{

71:  
 
 
 
 
 
 
std:
:
cout 
<
<
 
std:
:
endl;

72:  
 
 
 
 
}

73:  
 
 
}

74:  
}

75:  

76:  
int
 
getMults(
std:
:
vector<
int
>
&
 
p, 
int
 
index1, 
int
 
index2, 
int
 
index3)

77:  
{

78:  
 
 
int
 
ret 
=
 
1;

79:  
 
 
ret 
*=
 
p[
index1]
;

80:  
 
 
ret 
*=
 
p[
index2]
;

81:  
 
 
ret 
*=
 
p[
index3]
;

82:  
 
 
return
 
ret;

83:  
}

84:  

85:  
void
 
matrixChainOrder(
std:
:
vector<
int
>
&
 
p, 
Table&
 
m, 
Table&
 
s)

86:  
{

87:  
 
 
int
 
=
 
p.size(
)
 
1;

88:  
 
 
for
(
size_t
 
=
 
1;
 
<
=
 
n;
 
++i)
{

89:  
 
 
 
 
m.set(
i, 
i, 
0)
;

90:  
 
 
}

91:  
 
 
for
(
int
 
=
 
2;
 
<
=
 
n;
 
++l)
{

92:  
 
 
 
 
for
(
int
 
=
 
1;
 
<
=
 
1;
 
++i)
{

93:  
 
 
 
 
 
 
int
 
=
 
1;

94:  
 
 
 
 
 
 
m.setInfinity(
i, 
j)
;

95:  
 
 
 
 
 
 
for
(
int
 
=
 
i;
 
<
=
 
1;
 
++k)
{

96:  
 
 
 
 
 
 
 
 
std:
:
cout 
<
<
 
"i: "
 
<
<
 
<
<
 
" j: "
 
<
<
 
<
<
 
" k: "
 
<
<
 
<
<
 
" l: "
 
<
<
 
l;

97:  
 
 
 
 
 
 
 
 
bool
 
q_is_inf 
=
 
false;

98:  
 
 
 
 
 
 
 
 
if
(
m.getInfinity(
i, 
k)
 
|| 
m.getInfinity(
k+1, 
j)
)
{

99:  
 
 
 
 
 
 
 
 
 
 
q_is_inf 
=
 
true;

100: 
 
 
 
 
 
 
 
 
}

101: 
 
 
 
 
 
 
 
 
if
(
q_is_inf)
{

102: 
 
 
 
 
 
 
 
 
 
 
std:
:
cout 
<
<
 
std:
:
endl;

103: 
 
 
 
 
 
 
 
 
 
 
continue;

104: 
 
 
 
 
 
 
 
 
}

105: 
 
 
 
 
 
 
 
 
int
 
=
 
m.get(
i, 
k)
 
m.get(
k+1, 
j)
 
getMults(
p, 
i-1, 
k, 
j)
;

106: 
 
 
 
 
 
 
 
 
std:
:
cout 
<
<
 
" m[i="
 
<
<
 
<
<
 
",k="
 
<
<
 
<
<
 
"]="
;

107: 
 
 
 
 
 
 
 
 
std:
:
cout 
<
<
 
m.get(
i,k)
 
<
<
 
" m[k+1="
 
<
<
 
k+1 
<
<
 
",j="
;

108: 
 
 
 
 
 
 
 
 
std:
:
cout 
<
<
 
<
<
 
"]="
 
<
<
 
m.get(
k+1,j)
;

109: 
 
 
 
 
 
 
 
 
std:
:
cout 
<
<
 
" mults("
 
<
<
 
i-1 
<
<
 
","
 
<
<
 
<
<
 
","
 
<
<
 
j;

110: 
 
 
 
 
 
 
 
 
std:
:
cout 
<
<
 
")="
 
<
<
 
getMults(
p, 
i-1, 
k, 
j)
;

111: 
 
 
 
 
 
 
 
 
if
(
m.getInfinity(
i, 
j)
 
|| 
<
 
m.get(
i, 
j)
)
{

112: 
 
 
 
 
 
 
 
 
 
 
m.set(
i, 
j, 
q)
;

113: 
 
 
 
 
 
 
 
 
 
 
s.set(
i, 
j, 
k)
;

114: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

115: 
 
 
 
 
 
 
 
 
 
 
std:
:
cout 
<
<
 
" q: "
 
<
<
 
<
<
 
" is less than m[i,j]"
 
<
<
 
std:
:
endl;

116: 
 
 
 
 
 
 
 
 
}
 
else
 
{

117: 
 
 
 
 
 
 
 
 
 
 
std:
:
cout 
<
<
 
std:
:
endl;

118: 
 
 
 
 
 
 
 
 
}

119: 
 
 
 
 
 
 
}

120: 
 
 
 
 
}

121: 
 
 
}

122: 
}

123: 

124: 
void
 
printOptimalParens(
Table&
 
s, 
int
 
i, 
int
 
j)

125: 
{

126: 
 
 
if
(
=
=
 
j)
{

127: 
 
 
 
 
std:
:
cout 
<
<
 
"A"
 
<
<
 
i;

128: 
 
 
}
 
else
 
{

129: 
 
 
 
 
std:
:
cout 
<
<
 
"("
;

130: 
 
 
 
 
printOptimalParens(
s, 
i, 
s.get(
i, 
j)
)
;

131: 
 
 
 
 
printOptimalParens(
s, 
s.get(
i, 
j)
 
1, 
j)
;

132: 
 
 
 
 
std:
:
cout 
<
<
 
")"
;

133: 
 
 
}

134: 
}

135: 

136: 
int
 
main(
int
 
argc, 
char
 
argv[
]
)
{

137: 

138: 
 
 
std:
:
vector<
int
>
 
p;

139: 
 
 

140: 
 
 
p.push_back(
30)
;

141: 
 
 
p.push_back(
35)
;

142: 
 
 
p.push_back(
15)
;

143: 
 
 
p.push_back(
5)
;

144: 
 
 
p.push_back(
10)
;

145: 
 
 
p.push_back(
20)
;
 

146: 
 
 
p.push_back(
25)
;

147: 

148: 
 
 
Table 
m;

149: 
 
 
Table 
s;

150: 
 

151: 
 
 
matrixChainOrder(
p, 
m, 
s)
;
 
 

152: 
 
 
m.print(
"m"
)
;

153: 
 
 
s.print(
"s"
)
;

154: 
 
 
printOptimalParens(
s, 
1, 
p.size(
)
 
1)
;

155: 
 
 
std:
:
cout 
<
<
 
std:
:
endl 
<
<
 
std:
:
endl;

156: 
 
 
return
 
0;

157: 
}


Matrix Chain Output
1:  
i:
 
j:
 
k:
 
l:
 
q:
 
15750 
is 
less 
than 
m[
i,j]

2:  
i:
 
j:
 
k:
 
l:
 
q:
 
2625 
is 
less 
than 
m[
i,j]

3:  
i:
 
j:
 
k:
 
l:
 
q:
 
750 
is 
less 
than 
m[
i,j]

4:  
i:
 
j:
 
k:
 
l:
 
q:
 
1000 
is 
less 
than 
m[
i,j]

5:  
i:
 
j:
 
k:
 
l:
 
q:
 
5000 
is 
less 
than 
m[
i,j]

6:  
i:
 
j:
 
k:
 
l:
 
q:
 
7875 
is 
less 
than 
m[
i,j]

7:  
i:
 
j:
 
k:
 
l:
 
3

8:  
i:
 
j:
 
k:
 
l:
 
q:
 
6000 
is 
less 
than 
m[
i,j]

9:  
i:
 
j:
 
k:
 
l:
 
q:
 
4375 
is 
less 
than 
m[
i,j]

10: 
i:
 
j:
 
k:
 
l:
 
q:
 
2500 
is 
less 
than 
m[
i,j]

11: 
i:
 
j:
 
k:
 
l:
 
3

12: 
i:
 
j:
 
k:
 
l:
 
q:
 
6250 
is 
less 
than 
m[
i,j]

13: 
i:
 
j:
 
k:
 
l:
 
q:
 
3500 
is 
less 
than 
m[
i,j]

14: 
i:
 
j:
 
k:
 
l:
 
q:
 
14875 
is 
less 
than 
m[
i,j]

15: 
i:
 
j:
 
k:
 
l:
 
4

16: 
i:
 
j:
 
k:
 
l:
 
q:
 
9375 
is 
less 
than 
m[
i,j]

17: 
i:
 
j:
 
k:
 
l:
 
q:
 
13000 
is 
less 
than 
m[
i,j]

18: 
i:
 
j:
 
k:
 
l:
 
q:
 
7125 
is 
less 
than 
m[
i,j]

19: 
i:
 
j:
 
k:
 
l:
 
4

20: 
i:
 
j:
 
k:
 
l:
 
q:
 
5375 
is 
less 
than 
m[
i,j]

21: 
i:
 
j:
 
k:
 
l:
 
4

22: 
i:
 
j:
 
k:
 
l:
 
4

23: 
i:
 
j:
 
k:
 
l:
 
q:
 
28125 
is 
less 
than 
m[
i,j]

24: 
i:
 
j:
 
k:
 
l:
 
q:
 
27250 
is 
less 
than 
m[
i,j]

25: 
i:
 
j:
 
k:
 
l:
 
q:
 
11875 
is 
less 
than 
m[
i,j]

26: 
i:
 
j:
 
k:
 
l:
 
5

27: 
i:
 
j:
 
k:
 
l:
 
q:
 
18500 
is 
less 
than 
m[
i,j]

28: 
i:
 
j:
 
k:
 
l:
 
q:
 
10500 
is 
less 
than 
m[
i,j]

29: 
i:
 
j:
 
k:
 
l:
 
5

30: 
i:
 
j:
 
k:
 
l:
 
5

31: 
i:
 
j:
 
k:
 
l:
 
q:
 
36750 
is 
less 
than 
m[
i,j]

32: 
i:
 
j:
 
k:
 
l:
 
q:
 
32375 
is 
less 
than 
m[
i,j]

33: 
i:
 
j:
 
k:
 
l:
 
q:
 
15125 
is 
less 
than 
m[
i,j]

34: 
i:
 
j:
 
k:
 
l:
 
6

35: 
i:
 
j:
 
k:
 
l:
 
6

36: 
m

37: 
15750 
7875 
9375 
11875 
15125 

38: 
2625 
4375 
7125 
10500 

39: 
750 
2500 
5375 

40: 
1000 
3500 

41: 
5000 

42: 

43: 
s

44: 

45: 

46: 

47: 

48: 

49: 
(
(
A1(
A2A3)
)
(
(
A4A5)
A6)
)

50: 

  • A dynamic programming problem chooses the optimal choices of subproblems.

Memoization of Recursive Matrix Chain Algorithm [1]

Here we use a top-down recursive programming style to solve the matrix-chain example.

1:  
algorithm
 
memoizedMatrixChain(
p)
{

2:  
 
 
length[
p]
 
1;

3:  
 
 
for
(
to 
n)
{

4:  
 
 
 
 
for
(
to 
n)
{

5:  
 
 
 
 
 
 
m[
i.j]
 
inf;

6:  
 
 
 
 
}

7:  
 
 
}

8:  
 
 
return
 
lookupChain(
p, 
1, 
n)
;

9:  
}

10: 

11: 
algorithm
 
lookupChain(
p, 
i, 
j)
{

12: 
 
 
if
(
m[
i,j]
 
<
 
inf)
{

13: 
 
 
 
 
return
 
m[
i,j]
;

14: 
 
 
}

15: 
 
 
if
(
== 
j)
{

16: 
 
 
 
 
m[
i,j]
 
0;

17: 
 
 
}
 
else
 
{

18: 
 
 
 
 
for
(
to 
j-1)
{

19: 
 
 
 
 
 
 
lookupChain(
p, 
i, 
k)
 
lookupChain(
p, 
k+1, 
j)
 
p[
i-1]
*p[
k]
*p[
j]
;

20: 
 
 
 
 
 
 
if
(
<
 
m[
i,j]
)
{

21: 
 
 
 
 
 
 
 
 
m[
i,j]
 
q;

22: 
 
 
 
 
 
 
}

23: 
 
 
 
 
}

24: 
 
 
}

25: 
 
 
return
 
m[
i,j]
;

26: 
}

Greedy Algorithms: Activity-Selection Problem [1]

Activity-Selection Problem: Select the maximum-sized subset of mutually compatible activities.

i 1 2 3 4 5 6 7 8 9 10 11
start_time 1 3 0 5 3 5 6 8 8 2 12
end_time 4 5 6 7 8 9 10 11 12 13 14

Recursive Solution We can find the maximum subset by recursively splitting the problem into two parts and finding the optimal solution there:

  • A_ij = A_ik union {ak} union A_kj
We do not know the value of k. We could use a bottoms up method of finding all the possibilies and putting them in a table.

Theorem 16.1 [1]:
Consider any non-empty subproblem S_ij, and let a_m be the activity in S_ij with the earliest finish time.

Then:
  1. Activity a_m is used in some maximum-size subset of mutually compatible activities of S_ij.
  2. The subproblem S_im is empty
Proof: If S_im is not empty, then a_m cannot be in S_mj

This theorem implies that we only need to take one possible sub-problem. Therefore we don't need to use bottom's up dynamic programming.

Top-down recursive greedy algorithm
1:  
algorithm
 
recursiveActivitySelector(
s, 
f, 
i, 
n)
{

2:  
 
 
1;

3:  
 
 
while
(
<
and 
s[
m]
 
<
 
f[
i]
)
{

4:  
 
 
 
 
++m;

5:  
 
 
}

6:  
 
 
if
(
<
n)
{

7:  
 
 
 
 
return
 
{
a_m}
 
union 
recursiveActivitySelector(
s, 
f, 
m, 
n)
;

8:  
 
 
}
 
else
 
{

9:  
 
 
 
 
return
 
0;

10: 
 
 
}

11: 
}

Example:

Active Activities Proposed Active
A_1 A_2. start_2 is before finish_1
A_1 A_3. start_3 is before finish_1
A_1 A_4. start_4 after finish_1
A_1, A_4 A_5. start_5 is before finish_4
A_1, A_4 A_6. start_6 is before finish_4
A_1, A_4 A_7. start_7 is before finish_4
A_1, A_4 A_8. start_8 is after finish_4
A_1, A_4, A_8 A_9. start_9 is before finish_8
A_1, A_4, A_8 A_10. start_10 is before finish_8
A_1, A_4, A_8 A_11. start_11 is after finish_8
A_1, A_4, A_8, A_11

Dynamic Programming vs. Greedy Algorithms [1]

Dynamic programming
  • Optimal substructure:
    • For a given problem, you are given a choice that leads to the optimal solution. You do not know how to obtain this best choice yet
  • Overlapping subproblems:
    • A recursive program will solve the same sub-problems over and over

Greedy strategy
  • Greedy choice:
    • Prove that at any stage of the recursion, one of the optimal choices is the greedy choice
    • Show that all but one of the subproblems made by having the greedy choice are emtpy

References

  1. Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms", Second Edition. Chapters 15 and 16