We’ve seen how to do the naive approach towards pattern matching. So what about other algorithms that are much more better at doing this task? This is the Knuth-Morris-Pratt (KMP) algorithm for pattern matching.

We all should all know what string searching is. We have a pattern p and some string s, and we wish to see if p exists in s. There are a number of ways to do this, and this is one of those many ways; the naive approach.

Okay, I didn’t see that James had made a video about the very same subject. Great minds think alike I guess? Sigh. Well, here it is: The Dynamic Programming method for solving a 0/1 Knapsack Problem explained, in depth, by me in under 11 minutes!

Bug 1: Ignore the “The cell with the green circle around has a capacity of” blah blah etc. because I uploaded the wrong version ._. The green circle should be around cell (3,1).
Bug 2: I circle item ‘1’ when I should circle item ‘3’ at the end when we’re going through the keep array. I fail.
Bug 3: I say ‘2’ somewhere instead of ‘3’. See if you can spot it.

What is a traversal? It’s when you visit every node of a tree or graph using the edges.

Tree traversal

Let’s talk about 3 methods of traversing trees (Note: Always start at the root)

Depth-First-Search: Visit all the descendants of a node before visiting the sibling nodes. You have to visit some nodes more than once in a DFS, this is called backtracking

Breadth-First-Search: Visit all children of a node before visiting sibling nodes

Priority Search: Nodes are given priorities, and the children of the node that haven’t been visited yet with the highest priority are visited first

Note: This is a direct follow on (or a sequel if you want) to this post, so you might want to read that first!

Representing graphs

So you’ve seen what graphs are and how they can be classified. But how do you represent them in code? For example, do we put them in an array, a vector or a linked list? There isn’t one definite answer, so let’s go through some of the methods of representing them. Read more of this post