Tuesday, 19 August 2014

VisuAlgo



Visualising data structures and algorithms through animation

Set the animation speed at the bottom-left corner of the page.

It has animations for sorting, linked lists, stacks, queues, binary search trees, heaps, graphs and graph traversals, MSP.....

Tuesday, 13 May 2014

Graph Algorithms

This video explains these algorithms really well, but the machine voice is soooo annoying! :-/
It'll just have to do for now.
(I only watched the first one though. I'm only assuming that the rest will be useful too)


Floyd's Algorithm



Kruskal's Algorithm



Drijkstra Dijkstra's Algorithm

(hehe they made a spelling error / typo in the title)


Prim's Algorithm



DFS



BFS




Link to this channel






*if any of these don't coincide with what you were taught in class, please let me know so I can fix it

Radix Sort

Friday, 9 May 2014

DFS & BFS

Depth-First Search




procedure dfs(vertex v)
{
   mark v as visited
   for each w adjacent to v
      if w unvisited
         dfs(w)
}


Breadth-First Search

procedure BFS(vertex s)
{
   create a queue Q
   enqueue s onto Q
   mark s as visited
   while Q is not empty
   {
      dequeue a vertex from Q into v
      for each w adjacent to v
      {
         if w unvisited 
         {
            mark w as visited
            enqueue w onto Q
         }
      }
   }
}


DFS
BFS

Wednesday, 7 May 2014

WFIalgorithm

Warshall / Floyd / Ingerman Algorithm (for finding shortest paths)

The graph can include negative weights.
This algorithm also allows us to detect cycles if the diagonal is initialized to inf and not to zero. If any of the diagonal values are changed, then the graph contains a cycle. Basically, if the cost / distance from node A to node A is not inf, it contains a cycle.

http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

B-Trees

Play around with this to get the feel for b-trees:

http://slady.net/java/bt/view.php

(Blogger won't let me embed it :( )

Sunday, 27 April 2014

Saturday, 26 April 2014

Topological Stuff

Here's a quick and simple algorithm for topological ordering:
(examples to follow)

  • Find a node with NO incoming edges, and order it first.
  • Delete that node from the graph.
  • Repeat.

Source:

Friday, 25 April 2014

Insertion Sort

Selection Sort

"Red is current min.
Yellow is sorted list.
Blue is current item."
~Wikipedia




So blue iterates through the list, comparing values as it goes along. The current minimum value is stored in red. By the time the end of the list is reached (with blue), the value that is red at that time, will be the smallest value in the "active part" of the list.
It is moved to the end of the "passive section", marked in yellow. Once it is yellow, it doesn't need to search it again, as it's already where it should be.

Please note: The algorithm doesn't really use colours. They are just for visualisation.

"Selection sort" because it selects the smallest value and works with that.



wikipedia link

Bubble Sort

Tuesday, 1 April 2014

General Sorting Stuff

Best case Average Case Worst Case
Quick Sort O(n log(n)) O(n log(n)) O(n²)
Merge Sort O(n log(n)) O(n log(n)) O(n log(n))
Insertion Sort O(n) O(n²) O(n²)
Selection Sort O(n²) O(n²) O(n²)
Bubble Sort O(n) O(n²) O(n²)



Quick 'n easy bits o' code  <- Quick explanation of some sorting algorithms