Skip to content

Instantly share code, notes, and snippets.

View TheRayTracer's full-sized avatar

Simon Flannery TheRayTracer

5 followers · 0 following
  • Melbourne, Australia
View GitHub Profile
@TheRayTracer
TheRayTracer / main.cpp
Created March 17, 2012 10:53
Comparing brute force and divide and conquer methods to find the number of inversions in a large list. This implementation uses C++ and the STL. Comments have been removed before posting.
#include <iostream>
#include <fstream>
#include <vector>
#include <cassert>
#include <limits>
#define WIN32_LEAN_AND_MEAN
#include <windows.h>
namespace std { };
@TheRayTracer
TheRayTracer / QuickSort.txt
Created March 21, 2012 07:23
A sample proof-of-concept quick sort implementation to compare the importance of selecting a quality pivot. This implementation uses C++ and the STL. Comments have been removed before posting.
2148
9058
7742
3153
6324
609
7628
5469
7017
504
@TheRayTracer
TheRayTracer / main.cpp
Last active October 2, 2015 06:37
This example in C++ demonstrates two techniques to detect a loop in a linked list. This example determines if a linked list has a cycle. Note that the cycle can occur anywhere - not just the tail node linking back to the head. For example, if the list bec
#include <iostream>
#include <map>
#include <cassert>
#include <climits>
namespace std { };
using namespace std;
struct node
{
@TheRayTracer
TheRayTracer / main.cpp
Created March 28, 2012 08:58
The following is a C++ implementation of Karger's Random Contraction Algorithm to compute the minimum cut of a connected graph. The steps are: 1. Randomly pick an edge. 2. Merge both vertices. 3. Remove self vertex loops. Loop until only 2 vertices remain
#include <iostream>
#include <fstream>
#include <vector>
#include <time.h>
#include <math.h>
#include <cassert>
namespace std { };
using namespace std;
@TheRayTracer
TheRayTracer / Selection.txt
Created March 29, 2012 10:58
The following listing contains 3 examples implementations in C++ of the common Selection Algorithm. The first Selection Algorithm requires additional storage requirements and uses recursion. The next Selection Algorithm uses recursion, but no additional s
2148
9058
7742
3153
6324
609
7628
5469
7017
504
@TheRayTracer
TheRayTracer / main.cpp
Created April 6, 2012 12:02
The following is a C++ implementation demonstrating Kosaraju's Two-Pass Algorithm to find strongly connected components within a directed graph. An input file containing vertex edges is used to build a directed graph (and the reverse graph).
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <algorithm>
#include <cassert>
namespace std { };
using namespace std;
@TheRayTracer
TheRayTracer / main.cpp
Created April 7, 2012 09:42
This is a small C++ implementation demonstrating Topological sorting of a directed graph. An input file containing vertex edges is used to build a directed graph.
#include <iostream>
#include <fstream>
#include <vector>
#include <cassert>
namespace std { };
using namespace std;
istream& operator>>(istream& is, vector<vector<size_t> >& graph)
{
@TheRayTracer
TheRayTracer / QuickSort.txt
Created April 9, 2012 09:47
This is a Python proof-of-concept quick sort implementation to compare the importance of selecting a quality pivot.
2148
9058
7742
3153
6324
609
7628
5469
7017
504
@TheRayTracer
TheRayTracer / main.cpp
Created April 21, 2012 12:58
The following is a naive implementation of the Rabin-Karp algorithm to search for sub strings within larger strings using a rolling hash. The standard strstr() function will outperform this proof-of-concept implementation, but this implementation is in th
#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <iostream>
#include <cstring>
#include <cassert>
#include <sys/stat.h>
#define WIN32_LEAN_AND_MEAN
@TheRayTracer
TheRayTracer / main.py
Last active October 3, 2015 13:58
Examples of handy functions including Factorial, Fibonacci and palindrome finding functions using both recursion and loops.
def get_factorial_recursively(i):
f = 1
if i > 1:
f = f * i * get_factorial_recursively(i - 1)
return f
def get_factorial_iteratively(i):
f = 1
for j in range(2, i + 1):
f = f * j