--- a/videos/02-algo2.srt Sun Oct 04 22:20:25 2020 +0100
+++ b/videos/02-algo2.srt Mon Oct 05 01:42:47 2020 +0100
@@ -581,11 +581,11 @@
126
00:06:32,030 --> 00:06:36,140
-So the derivative of c of one.
+So the derivative of c of 1
127
00:06:36,140 --> 00:06:38,990
-Peaches defined as 0.
+would be defined as 0.
128
00:06:38,990 --> 00:06:41,465
@@ -593,7 +593,7 @@
129
00:06:41,465 --> 00:06:44,960
-If he have any cross one,
+If he have n = 1,
130
00:06:44,960 --> 00:06:48,125
@@ -602,74 +602,73 @@
131
00:06:48,125 --> 00:06:50,120
-So there's not much as we can do.
+So there's not much else we can do.
132
00:06:50,120 --> 00:06:53,735
We would have to calculate
-the derivative of air are.
+the derivative of r.
133
00:06:53,735 --> 00:06:57,395
-Now in the n equals two case.
+Now in the n = 2 case,
134
00:06:57,395 --> 00:07:00,245
-That would mean we
-have two copies of
+that would mean we
+have two copies of r.
135
00:07:00,245 --> 00:07:03,425
-R. And they would be a sequence.
+And they would be a sequence.
136
00:07:03,425 --> 00:07:07,775
-How would be the derivative C of
+How would be the derivative c of
137
00:07:07,775 --> 00:07:10,340
-R four by R be
+r followed by r be
138
00:07:10,340 --> 00:07:13,265
-defined where we would
+defined? Well we would
look up the definition.
139
00:07:13,265 --> 00:07:15,470
And it would say that's
-the complicated case
+the complicated case,
140
00:07:15,470 --> 00:07:16,760
-d sequence or
+the sequence.
141
00:07:16,760 --> 00:07:21,875
-if null a bowl of R,
+If nullable of r,
142
00:07:21,875 --> 00:07:25,250
-Then the most complicated case.
+then the more complicated case,
143
00:07:25,250 --> 00:07:28,225
-Else, That's the easy
-case that would be
+else, that's the easy
+case, that would be
144
00:07:28,225 --> 00:07:32,660
-derivative of c of R four
+derivative of c of r, followed
145
00:07:32,660 --> 00:07:35,540
-by R. And then I
-just have to copy
+by r. And then I just have to copy
146
00:07:35,540 --> 00:07:40,775
-that derivative of C
-of four by r here.
+that derivative of c
+of r followed by r here.
147
00:07:40,775 --> 00:07:43,130
@@ -682,17 +681,17 @@
149
00:07:51,145 --> 00:07:55,030
-it looks like we can
+it looks like we can't
do much better than
150
00:07:55,030 --> 00:07:58,390
-that unless we do
+that, unless we do
151
00:07:58,390 --> 00:08:02,560
a little bit of magic and the
-magic to do with this case.
+magic has to do with this case.
152
00:08:02,560 --> 00:08:07,420
@@ -719,12 +718,12 @@
157
00:08:18,550 --> 00:08:20,680
-this sequence work
-expression R followed
+this sequence regular
+expression r followed by r.
158
00:08:20,680 --> 00:08:23,080
-by r. And the question was,
+And the question was,
159
00:08:23,080 --> 00:08:26,365
@@ -738,11 +737,11 @@
161
00:08:30,370 --> 00:08:33,020
-So features the definition.
+So if we just unfold the definition,
162
00:08:33,020 --> 00:08:36,050
-We would ask if
+we would ask if
the r is nullable,
163
@@ -756,8 +755,8 @@
165
00:08:40,640 --> 00:08:44,135
-It is just this
-record expression.
+it is just this
+regular expression.
166
00:08:44,135 --> 00:08:49,550
@@ -794,11 +793,11 @@
173
00:09:08,330 --> 00:09:10,580
We don't have to
-calculate your now,
+calculate nullable,
174
00:09:10,580 --> 00:09:13,880
-but we can just replace
+we can just replace
it by this expression.
175
@@ -809,7 +808,7 @@
176
00:09:16,670 --> 00:09:19,860
that will be definitely
-good file algorithm.
+good our algorithm.
177
00:09:20,140 --> 00:09:22,775
@@ -823,7 +822,7 @@
179
00:09:26,795 --> 00:09:31,100
And notice that this record
-expression the only be
+expression will only be
180
00:09:31,100 --> 00:09:35,780
@@ -836,7 +835,7 @@
182
00:09:38,075 --> 00:09:40,060
-I will actually not go into it
+I will actually not go into
183
00:09:40,060 --> 00:09:43,850
@@ -850,11 +849,11 @@
185
00:09:45,260 --> 00:09:47,705
we definitely know
-that R is nullable.
+that r is nullable.
186
00:09:47,705 --> 00:09:52,955
-Okay? Okay, so here's
+Okay, so here's
our regular expression.
187
@@ -881,12 +880,12 @@
192
00:10:05,945 --> 00:10:10,160
So the first thing
-actually is we multiplying
+actually is we're multiplying
193
00:10:10,160 --> 00:10:16,595
this right hand side of the
-alternative is times one.
+alternative with times 1.
194
00:10:16,595 --> 00:10:19,700
@@ -896,26 +895,26 @@
195
00:10:19,700 --> 00:10:23,090
change which strings this
-work expression can match.
+regular expression can match.
196
00:10:23,090 --> 00:10:25,685
Remember we even had it
-as a simplification row,
+as a simplification rule,
197
00:10:25,685 --> 00:10:27,425
-just in this case B,
+just in this case we
198
00:10:27,425 --> 00:10:29,705
don't apply it as a
-simplification will
+simplification rule,
199
00:10:29,705 --> 00:10:31,310
actually make this
-work expression
+regular expression
200
00:10:31,310 --> 00:10:32,720
@@ -923,12 +922,12 @@
201
00:10:32,720 --> 00:10:34,910
-But times one doesn't make
+But times 1 doesn't make
202
00:10:34,910 --> 00:10:37,820
a difference because it
-means the end of the string,
+means at the end of a string,
203
00:10:37,820 --> 00:10:40,070
@@ -951,7 +950,7 @@
207
00:10:48,410 --> 00:10:51,860
-stuff are exactly the
+r are exactly the
same as that one.
208
@@ -978,25 +977,24 @@
213
00:11:06,320 --> 00:11:09,245
-So now I have r plus one.
+So now I have r + 1.
214
00:11:09,245 --> 00:11:13,055
Usually we cannot
-simplify r plus one.
+simplify r + 1.
215
00:11:13,055 --> 00:11:15,530
-If it had been R
-plus 0, then yes,
+If it had been r + 0, then yes,
216
00:11:15,530 --> 00:11:18,665
-we could have got rid of the CRO.
+we could have got rid of the 0.
217
00:11:18,665 --> 00:11:21,590
-Plus one often
+But this + 1 often
makes a difference,
218
@@ -1006,7 +1004,7 @@
219
00:11:22,970 --> 00:11:25,940
Remember, we know that
-this R is nullable,
+this r is nullable,
220
00:11:25,940 --> 00:11:29,840
@@ -1028,23 +1026,23 @@
224
00:11:37,070 --> 00:11:40,535
-a much simpler wound
-reg expression.
+a much simpler equivalent
+regular expression.
225
00:11:40,535 --> 00:11:44,285
And this actually helps a
-lot for our if condition.
+lot for our if-condition.
226
00:11:44,285 --> 00:11:46,925
Look, this was the
-original if condition
+original if-condition
227
00:11:46,925 --> 00:11:50,270
-and this is direct expression
-h. We just simplified.
+and this is the regular expression
+we just simplified.
228
00:11:50,270 --> 00:11:53,105
@@ -1062,11 +1060,11 @@
231
00:11:59,510 --> 00:12:02,750
pointless because you
-check if it's null above,
+check if it's nullable,
232
00:12:02,750 --> 00:12:05,060
-we return this reg
+we return this regular
expression or it's
233
@@ -1103,7 +1101,7 @@
240
00:12:24,170 --> 00:12:26,915
-So we know India CEO case,
+So we know in the 0-case,
241
00:12:26,915 --> 00:12:30,920
@@ -1112,35 +1110,35 @@
242
00:12:30,920 --> 00:12:33,095
-So because we define this
+Because we define this
243
00:12:33,095 --> 00:12:36,785
-and times as one,
+n-times as one,
the derivative is 0.
244
00:12:36,785 --> 00:12:39,889
-For chest r, this will
+For just r, this will
be the derivative.
245
00:12:39,889 --> 00:12:42,170
And we can't do any
-better than that
+better than that.
246
00:12:42,170 --> 00:12:45,620
-for our followed by
-RB just found out.
+For r followed by r, as we
+just found out
247
00:12:45,620 --> 00:12:47,270
-Actually it is quite simple.
+actually it is quite simple
248
00:12:47,270 --> 00:12:51,410
-Reg expression is equivalent
+regular expression is equivalent
to the derivative.
249
@@ -1158,7 +1156,7 @@
252
00:12:58,099 --> 00:13:02,390
-of this or what should
+of this r. What should
be the derivative?
253
@@ -1185,17 +1183,17 @@
258
00:13:18,275 --> 00:13:21,290
-Because then what we have is.
+Because then what we have is this.
259
00:13:21,290 --> 00:13:25,370
We can define our
-nullable for n times
+nullable for n-times
260
00:13:25,370 --> 00:13:31,025
-s. If any cross 0 then
-true as nullable.
+as if n = 0 then
+true, else nullable r.
261
00:13:31,025 --> 00:13:33,875
@@ -1208,7 +1206,7 @@
263
00:13:37,190 --> 00:13:40,235
then we return the
-Sierra reg expression.
+0 regular expression.
264
00:13:40,235 --> 00:13:43,295
@@ -1218,7 +1216,7 @@
265
00:13:43,295 --> 00:13:50,735
it would be derivative of
-c r four by r n minus one.
+c r followed by r{n-1}.
266
00:13:50,735 --> 00:13:54,770
@@ -1226,7 +1224,7 @@
267
00:13:54,770 --> 00:13:56,330
-thing we have to make choice that
+thing we have to make csure is that
268
00:13:56,330 --> 00:13:58,175
@@ -1243,7 +1241,7 @@
271
00:14:03,735 --> 00:14:07,810
-If we have a wreck expression R
+If we have a regular expression r
272
00:14:07,810 --> 00:14:09,820
@@ -1261,7 +1259,7 @@
275
00:14:14,245 --> 00:14:16,930
-So we would ask if I is nullable,
+So we would ask if r is nullable,
276
00:14:16,930 --> 00:14:19,765
@@ -1269,8 +1267,8 @@
277
00:14:19,765 --> 00:14:23,905
-And if i is not nullable
-or we have this as branch.
+And if r is not nullable,
+we have this else branch.
278
00:14:23,905 --> 00:14:27,010
@@ -1284,7 +1282,7 @@
280
00:14:30,310 --> 00:14:34,510
the derivative of two
-Rs, one after another.
+r's, one after another.
281
00:14:34,510 --> 00:14:37,330
@@ -1317,12 +1315,12 @@
287
00:14:52,700 --> 00:14:57,380
-And I have now followed
-by R plus R. Oh,
+And I have now r followed
+by r plus r.
288
00:14:57,380 --> 00:14:59,030
-hey, man, now you probably
+But now you probably
289
00:14:59,030 --> 00:15:00,680
@@ -1358,11 +1356,11 @@
296
00:15:18,995 --> 00:15:22,700
We go in this if branch
-only if r is nullable,
+only if r is nullable.
297
00:15:22,700 --> 00:15:26,150
-so on its own can already
+So r on its own can already
match the empty string.
298
@@ -1377,12 +1375,11 @@
300
00:15:30,695 --> 00:15:33,140
And so I now just have
-to rearrange the parent,
+to rearrange the parentheses
301
00:15:33,140 --> 00:15:35,450
-the thesis which we
-said we can also do.
+which we said we can also do.
302
00:15:35,450 --> 00:15:37,595
@@ -1395,7 +1392,7 @@
304
00:15:39,740 --> 00:15:41,975
-we have a if condition
+we have an if condition
305
00:15:41,975 --> 00:15:43,310
@@ -1422,17 +1419,17 @@
310
00:15:51,920 --> 00:15:55,310
-work for all the n times
+work for all the n-times
regular expressions.
311
00:15:55,310 --> 00:15:57,860
-And leave that to
+And I leave
the calculation for
312
00:15:57,860 --> 00:16:02,570
-maybe R to the four to you.
+maybe r to the four to you.
313
00:16:02,570 --> 00:16:04,490
@@ -1460,17 +1457,17 @@
318
00:16:16,250 --> 00:16:20,660
-In this Reto, said We have
-this explicit constructor now
+In this re2.sc, we said we have
+this explicit constructor
319
00:16:20,660 --> 00:16:25,535
-for n times b can now fill
+for n-times. We can now fill
in the cases for nullable.
320
00:16:25,535 --> 00:16:27,635
-So if we have R in times,
+So if we have r n-times,
321
00:16:27,635 --> 00:16:30,995
@@ -1480,11 +1477,11 @@
322
00:16:30,995 --> 00:16:34,190
Otherwise we have to test
-whether eyes nullable.
+whether r is nullable.
323
00:16:34,190 --> 00:16:37,565
-And in the derivative case, oi,
+And in the derivative case,
324
00:16:37,565 --> 00:16:40,339
@@ -1493,7 +1490,7 @@
325
00:16:40,339 --> 00:16:43,564
the return this 0
-wreck expression.
+regular expression.
326
00:16:43,564 --> 00:16:46,700
@@ -1502,11 +1499,11 @@
327
00:16:46,700 --> 00:16:50,270
-of psi of r four by n times of r,
+of c of r followed by n times of r,
328
00:16:50,270 --> 00:16:54,545
-but n minus one times and
+but n minus one times, and
everything else stays the same.
329
@@ -1519,8 +1516,8 @@
331
00:16:58,430 --> 00:17:01,595
-In the main mantra
-function as all the same.
+In the main matcher
+function is all the same.
332
00:17:01,595 --> 00:17:04,820
@@ -1533,17 +1530,17 @@
334
00:17:06,050 --> 00:17:08,090
-the optional record
+the optional regular
expression yet.
335
00:17:08,090 --> 00:17:10,670
-And we have now at this
+And we have now this
336
00:17:10,670 --> 00:17:13,250
-either warm and evil
-2-break expression.
+EVIL1 and EVIL2
+regular expression.
337
00:17:13,250 --> 00:17:15,290
@@ -1552,11 +1549,11 @@
338
00:17:15,290 --> 00:17:17,000
a bit more ambitious.
-Be testing it.
+We're testing it with
339
00:17:17,000 --> 00:17:20,315
-The strings between 01000
+strings between 0 and 1000
340
00:17:20,315 --> 00:17:22,580
@@ -1565,7 +1562,7 @@
341
00:17:22,580 --> 00:17:26,210
I'm testing this again
-inside the ammonite rebel.
+inside the Ammonite REPL.
342
00:17:26,210 --> 00:17:30,180
@@ -1580,22 +1577,22 @@
344
00:17:34,640 --> 00:17:40,490
700 needs two seconds,
-three seconds, 4800.
+three seconds for 800.
345
00:17:40,490 --> 00:17:43,940
-Let's see about it
-needs 4 thousand.
+Let's see what it
+needs for one thousand?
346
00:17:43,940 --> 00:17:47,435
But you have to remember
-Ruby and Python.
+Ruby and Python
347
00:17:47,435 --> 00:17:51,530
-They needed half a
-minute to just 43 TAs.
+needed half a
+minute for just 30 a's.
348
00:17:51,530 --> 00:17:54,485
@@ -1608,17 +1605,17 @@
350
00:17:57,110 --> 00:18:00,575
-1000 days so that success.
+1000 a's. So that success.
351
00:18:00,575 --> 00:18:04,775
-So this speed is also explained
+This speed is also explained
if you look at the sizes.
352
00:18:04,775 --> 00:18:08,975
Since we now have this explicit
-and times constructor,
+n-times constructor,
353
00:18:08,975 --> 00:18:11,930
@@ -1627,12 +1624,12 @@
354
00:18:11,930 --> 00:18:14,540
-This evil one reg
+This EVIL1 regular
expression will always be
355
00:18:14,540 --> 00:18:17,195
-of this size seven,
+of this size seven, at
the beginning.
356
@@ -1651,12 +1648,12 @@
359
00:18:24,740 --> 00:18:28,100
And let's try out this
-example, this 20 a.
+example with 20 a's.
360
00:18:28,100 --> 00:18:31,685
So we build the derivative
-according to 20 character A's.
+according to 20 character a's.
361
00:18:31,685 --> 00:18:33,890
@@ -1664,8 +1661,8 @@
362
00:18:33,890 --> 00:18:35,780
-we ended up this a
-wreck expression which
+we ended up with a
+regular expression that
363
00:18:35,780 --> 00:18:37,895
@@ -1677,7 +1674,7 @@
365
00:18:39,830 --> 00:18:43,205
-then we just have a wreck
+then we just have a regular
expression with 211 nodes.
366
@@ -1691,16 +1688,16 @@
368
00:18:47,165 --> 00:18:49,550
-So yeah, there's
+So yeah, the Brzozowski
369
00:18:49,550 --> 00:18:52,205
-this push off CKY algorithm
-and this improvement.
+algorithm
+and with this improvement,
370
00:18:52,205 --> 00:18:54,890
-We're now running
+we're now running
circles around Ruby and
371
@@ -1720,11 +1717,11 @@
374
00:19:02,975 --> 00:19:05,930
We now can do something
-like thousand a's.
+like thousand a's
375
00:19:05,930 --> 00:19:07,580
-And in reasonable time.
+in a reasonable time.
376
00:19:07,580 --> 00:19:09,740
@@ -1742,11 +1739,11 @@
379
00:19:14,210 --> 00:19:16,670
-six seconds here, it says 15.
+six seconds. Here it says 15.
380
00:19:16,670 --> 00:19:18,080
-So you always have to take
+You always have to take
381
00:19:18,080 --> 00:19:20,885
@@ -1764,7 +1761,7 @@
384
00:19:25,100 --> 00:19:27,065
-So we have worked a lot,
+We have worked a lot,
385
00:19:27,065 --> 00:19:30,720