diff -r 3bf3f5bb067e -r 260e330f7466 videos/02-algo2.srt --- 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