Skip to content

Instantly share code, notes, and snippets.

View zahlenteufel's full-sized avatar

Gastón Bengolea Monzón zahlenteufel

6 followers · 15 following
  • London
View GitHub Profile
@zahlenteufel
zahlenteufel / KMP Drawer.md
Last active August 29, 2015 13:57
KMP Automaton Drawer with Graphviz

#KMP Drawer with Graphviz

Given a pattern string, it generates the Graphviz dot script to draw the implicit automaton that uses the KMP string matching algorithm.

To compile:

g++ -std=c++0x -Wall kmpdraw.cpp -o kmpdraw

Example:

@zahlenteufel
zahlenteufel / Transitive Reduction.md
Last active August 29, 2015 13:57
Transitive Reduction of a Graph

#Transitive Reduction

Given a DAG (directed acyclic graph), it computes the minimal subgraph that has the same transitive closure. This is the most comfortable way of visualizing for example a partial order (with is transitive).

Uses Graphviz to visualize the results:

Sample

@zahlenteufel
zahlenteufel / earley.md
Created April 9, 2014 07:38
Earley Algorithm for Non-Deterministic CFG Parsing in Python

#Earley Algorithm for Non-Deterministic CFG Parsing in Python

$ python earley.py "3+2*1+4"

Abstract Syntax Tree for 3+2*1+4

in case it can parse the input, it outputs the Abstract Syntax Tree:

\Tree [.G [.S [.S [.S [.M [.T [.3 ]]]] [.+ ] [.M [.M [.T [.2 ]]] [.* ] [.T [.1 ]]]] [.+ ] [.M [.T [.4 ]]]] [.$ ]]

@zahlenteufel
zahlenteufel / parzenWindow.m
Last active August 29, 2015 14:00
Experimenting with Parzen Window in MATLAB for Density Estimation
% Generate the points
clf
subplot(2,1,1);
axis equal
mu1 = [5 4]';
sigma1 = [2 -0.8; -0.8 1];
mu2 = [0 1]';
sigma2 = [1 -0.06;-0.06 0.5];
chol(sigma1);
chol(sigma2); % verifica definida positiva
@zahlenteufel
zahlenteufel / kwaymerge.cpp
Created June 10, 2014 23:14
K-Way Merge using C++11
template <typename T>
using minheap = priority_queue<T, vector<T>, greater>;
vector<int> kwaymerge(vector<vector<int>>& vs) {
int k = vs.size();
vector<int> readcount(k, 0);
vector<int> res;
vector<pair<int, int>> vec;
for (int i = 0; i < k; i++) {
if (vs[i].size() > 0){
@zahlenteufel
zahlenteufel / LinCod.py
Created June 4, 2015 02:53
Implementation of Fraenkel's "Error-Correcting-Code using Combinatorial Games"
# 1) for m in 0..n compute g_s(z_m) = mex{g(Z_i_1) xor ... xor g(z_i_j) : 0 <= i_1 < .. < i_j < m, j <=s}
import itertools
import operator
n = 8
s = 3 # s = d - 2
def pack(idxs, n):
return [int(i in idxs) for i in xrange(n)]
@zahlenteufel
zahlenteufel / iterative_inorder_traversal.cpp
Created July 8, 2015 12:50
Iterative inorder traversal of a Binary Tree in C++11
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
struct node {
int value;
node* left;
node* right;
@zahlenteufel
zahlenteufel / binary_tree_iterators.cpp
Created July 8, 2015 16:20
Binary Tree Iterators
#include <iostream>
#include <cassert>
using namespace std;
struct node {
int value;
node* left;
node* right;
node *parent;
@zahlenteufel
zahlenteufel / Apollonius.java
Last active October 7, 2015 06:08
Cono de Apolonio
SpecialPlane horPlane = new SpecialPlane(0,0.2, new PVector(253, 184, 19));
SpecialPlane parPlane = new SpecialPlane(1, 0.5, new PVector(246, 139, 31));
SpecialPlane obPlane = new SpecialPlane(0.5, 0.3, new PVector(241, 112, 34));
VPlane vertPlane = new VPlane(-0.4, new PVector(238, 246, 108));
boolean[] visible = {true, true, true, true, true}; // which parts of the cone are visible
float rotY = 0, rotX = 0;
PVector[][] ps = generatePoints(100);
void setup() {
@zahlenteufel
zahlenteufel / minRectangle.html
Last active July 29, 2016 23:47
Minimum Enclosing Rectangle
<canvas id="myCanvas" width="500" height="500"></canvas>