forked from gcallah/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 1
/
DivideConquerI.html
532 lines (492 loc) · 19.6 KB
/
DivideConquerI.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
<html>
<head>
<link href="style.css" rel="stylesheet" type="text/css"/>
<title>
Design and Analysis of Algorithms: Divide and Conquer
</title>
</head>
<body>
<h1>
Design and Analysis of Algorithms: Divide and Conquer
</h1>
<div style="text-align:center">
<p>
<img
src="https://upload.wikimedia.org/wikipedia/commons/thumb/4/45/Sierpinski_triangle.svg/250px-Sierpinski_triangle.svg.png">
</p>
</div>
<h2>
Topics
</h2>
<h3>
Introduction
</h3>
<p>
What is this?
<ul>
<li><b>Divide</b> the problem into a number of sub problems that are
smaller instances of the same problem.
<li><b>Conquer</b> the sub problems by solving them recursively. If
the subproblem sizes are small enough, however, just solve
the subproblems in a straightforward manner.
<li><b>Combine</b> the solutions for the sub problems into the
solution for the original problem.
</ul>
</p>
<h4>
Recurrences
</h4>
<p>
Merge sort recurrence:
<br>
<br>
<img src="graphics/RecEq1.gif">
<br>
<br>
We "solve" these by finding a closed-form equation that
describes the recurrence but without recursion.
<br>
<b>Solution</b>: T(n) = Θ(n lg n)
<br>
<br>
<b>Methods</b>:
<br>
</p>
<ul>
<li><b>Substitution method</b>: Guess a solution and then use
induction to prove it.
<li><b>Recursive-tree method</b>: Convert the recurrence into a
tree whose nodes represent costs incurred at each level.
<li><b>Master method</b>:
<br>
Solves recurrences of the form:
<br>
T(n) = aT(n / b) + f(n)
<br>
where a ≥ 1, b > 1.
</ul>
<p>
<br>
<b>Technicalities</b>
<br>
We often omit floors, ceilings, and boundary conditions. For
instance, if n is odd, we may say n / 2 anyway.
</p>
<h3>
The maximum-subarray problem
</h3>
<p>
<img
src="https://upload.wikimedia.org/wikipedia/commons/thumb/2/25/Maximum_Subarray_Visualization.svg/220px-Maximum_Subarray_Visualization.svg.png">
<br>
<br>
Only makes since in an array with both negative and positive
values: otherwise the answer is either the whole array of the
maximum member.
<br>
<br>
</p>
<h4>
Brute-force solution
</h4>
<p>
Try every combination of two elements!
<br>
A n choose 2 problem, so order of Ω(n<sup>2</sup>).
<br>
n choose 2 will be about 1/2 n<sup>2</sup>, since it equals
n(n - 1) / 2. So we can establish a lower bound by setting c =
1/3, for instance, and n choose 2 will always be bounded from
below by c*n<sup>2</sup>.
</p>
<h4>
A transformation
</h4>
<p>
We loon at the problem differently: let's find the nonempty,
contiguous subarray of our array whose values have the largest sum.
We call this the <b>maximum subarray</b>.
</p>
<h4>
A solution using divide-and-conquer
</h4>
<p>
To solve this problem, we divide an array A into three subarrays,
and ask what is the maximum subarray in each:
</p>
<ol>
<li>From A[low] to A[midpoint - 1].
<li>Crossing the mid-point.
<li>From A[midpoint + 1] to A[high]
</ol>
<p>
Problems 1 and 3 are simply this same problem on a smaller array!
Problem 2 can be solved by finding the maximum subarrays in
low-to-mid and in mid+1-to-high.
<br>
<br>
The recurrence is the same as for merge sort.
</p>
<h3>
Strassen's algorithm for matrix multiplication
</h3>
<h4>
Recursive Square-Matrix Multiply
</h4>
<p>
We divide each of our initial matrices into four
sub-matrices, and multiply them. Which we do by dividing
each of them into four...
<br>
<br>
In the base case when each matrix has only one member, we
just multiply them and return the result.
<br>
<br>
So what is our recurrence? Each step except the base case
multiplies eight matrices of size n / 2. So they
contribute 8T(n / 2) to running time. There are also four
matrix additions of matrices containing n<sup>2</sup> / 4
entries -- squared because n specifies an n x n matrix. So
this contributes Θ(n<sup>2</sup>) time.
<br>
<br>
So our recurrence is:
<br>
<br>
<img src="graphics/RecEq6.gif">
<br>
<br>
The master method will show us that the solution to this
recurrence is:
<br>
T(n) = Θ(n<sup>3</sup>)
</p>
<h4>
Strassen's Algorithm
</h4>
<p>
<img
src="https://upload.wikimedia.org/wikipedia/commons/thumb/2/2e/Strassen_algorithm.svg/800px-Strassen_algorithm.svg.png">
<br>
<br>
By adding ten additions, we can cut the divide portion of
our algorithm down to seven multiplications instead of
eight.
<br>
<br>
Let's try one!
<br>
<br>
Here is the method:
<br>
<br>
For two matrices:
<br>
<br>
<img src="graphics/RecEq8.gif">
<br>
<br>
Define:
<br>
<br>
P<sub>1</sub> = A(F - H)
<br>
P<sub>2</sub> = H(A + B)
<br>
P<sub>3</sub> = E(C + D)
<br>
P<sub>4</sub> = D(G - E)
<br>
P<sub>5</sub> = (A + D) * (E + H)
<br>
P<sub>6</sub> = (B - D) * (G + H)
<br>
P<sub>7</sub> = (A - C) * (E + F)
<br>
<br>
Then:
<br>
<br>
<img src="graphics/RecEq9.gif">
<br>
<br>
So let's try this example:
<br>
<br>
<img src="graphics/RecEq7.gif">
<br>
<br>
<b>Important Lesson</b>
<br>
<br>
There are often serious trade-offs between set-up time and
aymptotic run-time. One must carefully consider how large
one's inputs are likely to be before opting for a complex
algorithm like Strassen's. On modern hardware optimized for
matrix multiplication, matrix sizes often need to be in the
thousands before Strassen's algorithm yields significant
gains.
</p>
<h3>
The substitution method for solving recurrences
</h3>
<h4 id="Towers">
Towers of Hanoi
</h4>
<p>
<br>
<img
src="https://upload.wikimedia.org/wikipedia/commons/thumb/0/07/Tower_of_Hanoi.jpeg/300px-Tower_of_Hanoi.jpeg">
<br>
The monks in a temple have the job of moving all of the
disks on one peg to another, constrained by these rules:
<br>
1) Only one disk can be moved at a time.
<br>
2) Each move consists of taking the upper disk from
one of the stacks and placing it on top of another stack
i.e. a disk can only be moved if it is the
uppermost disk on a stack.
<br>
3) No disk may be placed on top of a smaller disk.
<br>
(
<a href="https://en.wikipedia.org/wiki/Tower_of_Hanoi">
Source
</a>
)
<br>
<br>
<img
src="https://upload.wikimedia.org/wikipedia/commons/thumb/8/8d/Iterative_algorithm_solving_a_6_disks_Tower_of_Hanoi.gif/220px-Iterative_algorithm_solving_a_6_disks_Tower_of_Hanoi.gif">
<br>
<br>
Recurrence:
<br>
<img src="graphics/RecEq2.gif">
<br>
<img
src="https://upload.wikimedia.org/wikipedia/commons/thumb/2/20/Tower_of_Hanoi_recursion_SMIL.svg/220px-Tower_of_Hanoi_recursion_SMIL.svg.png">
<br>
<br>
Why is this the recurrence? Well, to move disk <em>n</em>,
we first move disks 1 to <em>n</em> - 1 to the spare peg,
then move <em>n</em> to the target peg, then move disks 1
to <em>n</em> - 1 to the target peg.
<br>
<br>
So we guess the closed-form solution is something like
2<sup>n</sup>. Why? Well, we multiply by a factor of 2 each
recursion!
<br>
Now, let's try writing out a few elements of the sequence:
<br>
T(0) = 0
<br>
T(1) = 2*0 + 1 = 1
<br>
T(2) = 2*1 + 1 = 3
<br>
T(3) = 2*3 + 1 = 7
<br>
T(4) = 2*7 + 1 = 15
<br>
T(5) = 2*15 + 1 = 31
<br>
So is the answer 2<sup>n</sup> - 1?
<br>
Base case: T(0) = 0 = 2<sup>0</sup> - 1.
<br>
Yes!
<br>
Now induction: we want to show that, <em>if</em> T(n - 1) =
2<sup>(n - 1)</sup> - 1, <em>then</em> T(n) will equal
2<sup>n</sup> - 1.
<br>
How proof by induction works: we have proved our base case.
Now we try to prove that for any n, if for n - 1 our
hypothesis is true, then it is true for n as well. And since we
have already proved that for n = 0 it is true, that will
mean it will be true for all n whatsoever.
<br>
So we substitute in for n - 1:
<br>
T(n) = 2(2<sup>(n - 1)</sup> - 1) + 1
<br>
= 2 * 2<sup>(n - 1)</sup> - 2 + 1
<br>
= 2<sup>n</sup> - 1
<br>
And we are done!
</p>
<h3>
The recursion-tree method for solving recurrences
</h3>
<p>
There are two ways to use this method:
</p>
<ol>
<li>As a way to generate a guess for the substitution
method.
<li>As a way to generate a rigorous answer by itself.
</ol>
<p>
Analyze the tree:
<br>
<br>
<img
src="graphics/NSquaredTree1.png">
<br>
<br>
Calculate the work at each level:
<br>
<br>
<img
src="graphics/NSquaredTree2.png">
<br>
<br>
This produces the geometric series:
<br>
<br>
<img src="graphics/RecEq4.gif">
<br>
<br>
If we set a = n<sup>2</sup> and r = 1/2, then we have the
general sum of a converging geometric series:
<br>
<br>
<img src="graphics/RecEq5.gif">
<br>
<br>
So the solution here is O(n<sup>2</sup>). The amount of work at
each level is reduced by a power of two, and so is
just a constant factor times the root.
<br>
<br>
<b>Another example</b>:
<br>
<br>
In our textbook, we have the recurrence:
<br>
T(n) = 3T(n / 4) + cn<sup>2</sup>, c > 0
<br>
<br>
<img src="graphics/ThreeTree.png" height="440" width="700">
<br>
<br>
a<sup>log<sub>b</sub>c</sup> = c<sup>log<sub>b</sub>a</sup>
</p>
<h3>
The master method for solving recurrences
</h3>
<p>
<b>Form</b>: T(n) = aT(n / b) + f(n).
<br>
Where a ≥ 1 and b > 1 and f(n) asymptotically positive.
<br>
<br>
<b>Three cases</b>
<br>
Compare n<sup>log<sub>b</sub>a</sup> and f(n):
</p>
<ol>
<li>f(n) = O(n<sup>log<sub>b</sub>a-ε</sup>),
ε > 0
<br><b>Solution</b>: T(n) =
Θ(n<sup>log<sub>b</sub>a</sup>)
<li>f(n) = Θ(n<sup>log<sub>b</sub>a</sup>)
<br><b>Solution</b>: T(n) =
Θ(n<sup>log<sub>b</sub>a</sup> lg n)
<li>f(n) = Ω(n<sup>log<sub>b</sub>a+ε</sup>),
ε > 0
<br><b>Solution</b>: T(n) = Θ(f(n))
</ol>
<p>
<br>
<b>Sample problems:</b>
</p>
<ol>
<li>T(n) = 2T(n / 4) + n<sup>2</sup>
<li>T(n) = 4T(n / 2) + n<sup>2</sup>
<li>T(n) = 20T(n / 4) + n
<li>T(n) = 3<sup>n</sup>(n / 3) + n<sup>3</sup>
<li>T(n) = 8T(n / 2) + 2<sup>n</sup>
</ol>
<h2>
Source Code
</h2>
<p>
<a
href="https://github.com/gcallah/algorithms/blob/master/python/div_and_conquer.py">
Python
</a>
<br>
<a
href="https://github.com/gcallah/algorithms/blob/master/ruby/div_and_conquer.rb">
Ruby
</a>
<br>
<a
href="https://github.com/gcallah/algorithms/blob/master/javascript/divideAndConquer.js">
JavaScript
</a>
<br>
<a
href="https://github.com/gcallah/algorithms/blob/master/Java/matrixMult.java">
Java
</a>
</p>
<h2>
External Links
</h2>
<ul>
<li>
<a href="https://en.wikipedia.org/wiki/Master_theorem">
The Master Theorem
</a>
<li>
<a
href="https://en.wikipedia.org/wiki/Maximum_subarray_problem">
Maximum Subarray Problem
</a>
<li>
<a
href="https://www.khanacademy.org/computing/computer-science/algorithms/towers-of-hanoi/a/towers-of-hanoi">
The Towers of Hanoi
</a>
<li>
<a href="https://en.wikipedia.org/wiki/Strassen_algorithm">
Strassen's Algorithm
</a>
</ul>
<h2>
Homework
</h2>
<ol>
<li>Implement the Towers of Hanoi in a programming language of
your choice. Put in test code to count the number of moves.
Print out the number of moves after you have solved the
puzzle. Run the code and show that we have solved
the recurrence correctly. What you hand in should be
your source code plus several runs showing your results.
<li>Implement Strassen's method in a programming language of
your choice.
<li>A well-known recurrence is the Fibonacci sequence. Please
find the closed form for it, <em>showing how you found
it</em>. (You can easily look up the form online, but
please try to solve this yourself.)
<li>Find tight asymptotic bounds for the following recurrence:
<br>
<img src="graphics/RecEq3.gif">
<br>
</ol>
<h2>
Credits
</h2>
<ul>
<li>Recursion-tree diagrams:
http://www.cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-master/lec20.html
</ul>
</body>
</html>