String Searching – The Knuth-Morris-Pratt Algorithm

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.

String Searching – The Naive Approach

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.

Algorithms – The 0/1 Knapsack Problem – Dynamic Programming method

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.

Sorting – Quick Sort

A post dedicated to that oh so famous, Quick sort! ^^

Sorting – Merge Sort

A post all about the Merge sort :D

Shortest Path – Dijkstra’s Algorithm

We’ve all used those horrible SATNAV’s to get from one place to another. But how do they calculate the path we must follow in order to minimize the time needed.

This is a shortest distance problem, which shall be covered in this post via Dijkstra’s Algorithm.

Algorithms – Quick Graph Terminology

This post will be brief. It just contains a load of terminology for parts of graphs, such as:

• Spanning Trees
• Back Edges
• etc…

Dynamic Programming - Solving The Knapsack Problem

How do we fit the most valuable items from a selection of items into a knapsack? This... ladies and gentlemen, is the Knapsack problem.

Algorithms – Depth/Breadth First Search

We have seen some of the key concepts to Graphs; What a node is, an edge – as well as definitions for Digraphs and Undirected Graphs – and other bits ‘n’ bobs :) .

But one question stills looms; How do we traverse a Graph?

Here we shall look at two of the key traversing algorithms for Graphs:

• Depth First Search (DFS), and
• Breadth First Search (BFS).

Algorithms – Adjacency Lists and Matrices

Nodes can be connected to other nodes – otherwise it would be a bleeding useless graph! :D

But how do we know which node is connected to which nodes? Welcome to the wonderful world of Adjacency Lists and Matrices!

Also, i apologise for the long pause in posts! :(

Algorithms - Traversals

Traversals

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

So let's try these on a tree. Here's one I made earlier:

Algorithms - More graphs

More Graphs (yay)

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.

Algorithms - Intro to Graphs

Intro to Graphs

What are graphs?

So while you might think that graphs are things like these:



..you're right! That is a graph. But when computer scientists talk about graphs, they actually mean these:

Algorithms - Analysis of Algorithms

Analysis of Algorithms

There are 2 ways of doing this:

• Inspecting pseudo code.  This is the analytical approach


• Implement the algorithm and time it. This is the experimental approach

The analytical approach is usually preferred because:

Algorithms - Complexity

Complexity

Note: You really need to read the algorithms text book chapters 1 to 3 as well as reading these notes!

Second note: This will probably be quite short as I'm cutting out all the exposition from the notes and just including the important information.

Algorithms – Trees

So what exactly is a Tree in programming?

Well, it is not a tree that you see every day when you walk through a park :P

Algorithms – Complexity and the Big-Oh

A friend once told me that you can only truly grasp the idea of complexity if you make friends with the Big-Oh; And that's exactly what i intend to help you all with here today! :)