A post dedicated to that oh so famous, Quick sort! ^^
Wednesday, 19 May 2010
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…
Tuesday, 18 May 2010
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! :(
Subscribe to:
Posts (Atom)