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.

Read more of this post

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.

Read more of this post

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! ^^

Read more of this post

Sorting – Merge Sort


A post all about the Merge sort :D

Read more of this post

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.

Read more of this post

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…

Read more of this post

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.

Read more of this post

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).

Read more of this post

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! :(

Read more of this post

Follow

Get every new post delivered to your Inbox.

Join 45 other followers