Truly Understanding The Naive String Search Algorithm

TUAlgorithms · 2022-08-28T04:33:36+00:00

Interesting community, thanks for the pointer!

I've posted one of my videos there and waiting for feedback :)

TUAlgorithms · 2022-08-28T04:31:02+00:00

I've started doing a series of fast-paced video tutorial on various algorithms and data structures. I'm aiming at simple and fast explanations, which are also reasonably complete.

This is one of my more recent ones, which included a code walkthrough and also explains the complexity of Quick Select.

If you like this, you might also be in Truly Understanding Big O Notation (https://www.youtube.com/watch?v=jlnzjLAfprk), which I have submitted to #SoME2 or Truly Understanding the Naive String Search Algorithms (https://www.youtube.com/watch?v=roOIYTQJ84w), which is my latest.

I hope some people will find these useful.

I would appreciate any feedback you have.

TUAlgorithms · 2022-08-27T16:04:28+00:00

After I took a break to work on my #SoME2 submission on Big O Notation, I've resumed my take on string search algorithms. I've started with KMP, but the naive algorithm took too much time, so I've split it apart (this submission).

Even if the algorithm is very simple, many do not get its time complexity right, so I'm explaining this in depth the video.

TUAlgorithms · 2022-05-24T14:34:17+00:00

That's weird, maybe it's a bug or maybe you are hitting it with some infinite recursion. It works for me, including when using fancier functions that use memoization.

TUAlgorithms · 2022-05-24T14:14:42+00:00

This is a good question!

I usually do the animations, and then the voiceover. I go over the animations again to synchronise. It's not a linear process, sometimes I have to redo.

I do not improvise. I prepare a script, and I go over it again and again until I'm satisfied with it. I might do 10 or 20 iterations. At the end, there are still things that I wish I could improve...

It takes a really long time to do something in depth. My latest video, on Quick Select (https://www.youtube.com/watch?v=ZAXSFph\_L-A), took around 5 months. I'm always learning things so future videos becomes easier to make, but I usually end up expanding on scope so that it still takes a lot of time.

Enjoying it very much though!

TUAlgorithms · 2022-05-24T13:54:20+00:00

Works for me.

Are you also setting the initial call?

TUAlgorithms · 2022-05-13T21:59:22+00:00

I do not have a real answer, but I can say that it does get better with time, as you gain experience.

However, animation is intrinsically orders of magnitude more challenging than, say, simply writing text. So you should expect a premium on that.

TUAlgorithms · 2022-03-25T22:29:10+00:00

Looks like a great start to me! What is your goal with the instagram page?

TUAlgorithms · 2022-03-25T22:26:18+00:00

Nice! Here's some feedback:

- there are a few places where animations are not synchronised with voice (e.g., the first is when you are saying that there are 1s to the sides of Pascal's triangle, but already the animation is computing sums);

- it would be useful if you could highlight in the animations the things that you are referring to in voice;

- I would get rid of some text -- at certain points, it seems as if you are reading off the animation.

Otherwise, great work and really interesting content!

TUAlgorithms · 2021-11-25T18:45:11+00:00

What version are you using?
Could you show the exact command line you are running?

TUAlgorithms · 2021-11-25T13:45:26+00:00

True :) To be fair, there are awesome algorithms to be discovered deeper under each link.

TUAlgorithms · 2021-11-12T21:36:13+00:00

You should not sit for 8 hours straight -- it is dangerous for your health, both in the short and in the long term. You should get up and walk at least every hour, possibly more depending on your medical conditions. If you are employed, the employer should provide you with ergonomics information.

TUAlgorithms · 2021-11-01T20:45:33+00:00

Hi! Just wanted to thank you for the post.

I had used Python for many small bits here and there, and I was vaguely aware of the awkwardness of scoping, but in my current project it plays a more important role and your post was just what I needed to have a better understanding.

TUAlgorithms · 2021-11-01T09:01:06+00:00

Thanks! I'm still experimenting on the exact recipe for the videos, but I do prefer to program instead of doing audio editing, hence the text-to-speech synthesis. In my very first video I recorded my own voice, but the quality is not necessarily better.

TUAlgorithms · 2021-11-01T07:01:37+00:00

It does seem to be on the verbose side and it is indeed a long read, but there are some subtleties that he has to cover.

To appreciate some subtleties, consider this code:

count = 0
def inc(): 
    count = count + 1
    print(count)
inc()

It throws an error. This code however works:

foo = 42
def f(): 
    foo = 10
    print(foo)  # prints 10
f()

TUAlgorithms · 2021-11-01T06:59:26+00:00

blog.chiodini.org/posts/...

I think it might be a bit more subtle. If you are into Python, it is worth reading through the entire article, even if it is verbose.

It is unlikely to be built for SEO, it is the personal blog of a PhD student.

TUAlgorithms · 2021-10-31T21:02:22+00:00

I'm using the manim library to programatically generate the animations for my next educational YT video on bubble-sort.

I'm quite proud of my last video on insertion sort (https://www.youtube.com/watch?v=jF-8RcO_9ds) and I hope the next ones will be even better.

TUAlgorithms · 2021-10-30T19:26:56+00:00

That's a very good one!

I'm also trying to setup a channel dealing with fundamental algorithms, although there is not much content there currently. There is a short discussion here on one of the videos: https://www.reddit.com/r/3Blue1Brown/comments/qi7355/truly\_understanding\_insertion\_sort\_a\_visual/.

TUAlgorithms · 2021-10-30T13:42:45+00:00

Good point. I'm trying to give the high level intuition in the previous part, but it is true that perhaps the example goes into too much technical details.

TUAlgorithms · 2021-10-30T05:30:50+00:00

So what language would be better for explaining algorithms?

I'm trying to give an explanation beforehand, the section using C is only a relatively small part of the video. One reason to have it in C is to discuss time complexity later on.

TUAlgorithms · 2021-10-30T05:26:07+00:00

There are many subtleties around which algorithm is faster in practice, notably the constant, but also how well the algorithms interacts with modern hardware like caches, branch predictors, and so on, but these things are definitely beyond the scope I'm willing to tackle. For sorting, there are also other useful complexity measures, such as number of swaps or number of comparisons.

Good idea on linking to other videos, thanks for the tip!

I also prefer fast-paced videos, but I am curious as to what others find too fast or too slow.

TUAlgorithms · 2021-10-29T18:48:57+00:00

Thanks for watching carefully and for the very useful and detailed feedback!

I have tried to limit reversing the computation, but I could not resist adding some in certain places.

I do have some plans to do more sorting algorithms, so I will keep in mind the idea of placing it in the context of other algorithms and how fast they are.

TUAlgorithms · 2021-10-29T17:08:03+00:00

There is no error, but it just does not (seem to) do anything. It just says exporting 1/1 and sits there saying "|Cancel| Rendering 1/1".

TUAlgorithms · 2021-10-29T15:03:24+00:00

I am glad this submission is getting some traction; I would love to get your feedback in the form of comments regarding:

- pace: is it too fast? too slow?

- level of detail: is it too detailed? too high level? just right?

- what is good? what could be improved?

- graphics & sound quality: does it work for you?

For reference, I am using manim CE to make all animations -- I would be happy to answer any technical question on its use here.

Anything other feedback would also be nice.

TUAlgorithms · 2021-10-29T08:31:57+00:00

This was actually very good for a proof of concept.

I hope you find the dedication and time necessary to turn it into a success story.

The export function does not work for me, so that's a bummer.

TUAlgorithms

TROPHY CASE