siddMahen

// Useful when performing linear cryptanalysis of block ciphers w/ S-Boxes
// Example S-Boxes used in the GHOST algorithm
var sb1 = [ 4, 10, 9, 2, 13, 8, 0, 14, 6, 11, 1, 12, 7, 15, 5, 3 ],
    sb2 = [ 14, 11, 4, 12, 6, 13, 15, 10, 2, 3, 8, 1, 0, 7, 5, 9 ],
    sb3 = [ 5, 8, 1, 13, 10, 3, 4, 2, 14, 15, 12, 7, 6, 0, 9, 11 ],
    sb4 = [ 7, 13, 10, 1, 0, 8, 9, 15, 14, 4, 6, 12, 11, 2, 5, 3 ],
    sb5 = [ 6, 12, 7, 1, 5, 15, 13, 8, 4, 10, 9, 14, 0, 2, 11, 2 ],
    sb6 = [ 4, 11, 10, 0, 7, 2, 1, 13, 3, 6, 8, 5, 9, 12, 15, 14 ],
    sb7 = [ 13, 11, 4, 1, 3, 15, 5, 9, 0, 10, 14, 7, 6, 8, 2, 12 ],
    sb8 = [ 1, 15, 13, 0, 5, 7, 10, 4, 9, 2, 3, 14, 6, 11, 8, 12 ];

siddMahen

var freq = require("freq"),
    fs = require("fs"),
    eng = {
         'e': 13.11,
         't': 10.47,
         'a': 8.15,
         'o': 8.00,
         'n': 7.10,
         'r': 6.83,
         'i': 6.35,

siddMahen

set nocompatible
set backupdir=~/.vim/backups
set undofile
set undodir=~/.vim/undo     " remember undos across sessions
set noswapfile

" ----------------------------------------------------------------------------
"  Text Formatting
" ----------------------------------------------------------------------------

siddMahen

Algorithms: Design and Analysis Part 1 - Notes

These are my personal notes about the course of the same name on Coursera. Feel free to fork these and make your own notes. I'm open to suggestions.

The sub-titles of these notes correspond roughly to a various group of lectures for each week, however, I do occasionally stray for the sake of clarity.

siddMahen

Machine Learning Notes

Arthur Samuel (1959): Field of study that gives computers the ability to learn without being explicitly programmed.

• Checkers playing computer

Well-posed Learning problem: A computer program is said to learn from experience E with respect to some task T and some performance measure P, if its performance T, as measured by P, improves with experience E.

Intro

siddMahen

Applications of Matroid Theory

Creating NP-hard Problems

Solving interesting Problems

Using matroids to solve subset sum.

The (Decision) Subset Sum Problem:

siddMahen

// make everything legible

var MSG_PACK_POS_FIXNUM = 0x00,
    MSG_PACK_MAP_FIX    = 0x80,
    MSG_PACK_ARRAY_FIX  = 0x90,
    MSG_PACK_RAW_FIX    = 0xa0,
    MSG_PACK_NIL        = 0xc0,
    MSG_PACK_FALSE      = 0xc2,
    MSG_PACK_TRUE       = 0xc3,
    MSG_PACK_FLOAT      = 0xca, /* Not supported */

siddMahen

var msgpack = require("../"),
    pack = msgpack.pack.pure,
    unpack = msgpack.unpack.pure,
    assert = require("assert");

function genObj(type, size){
    var obj;

    switch(type){
        case "raw":

siddMahen

Polytopes

A polytope is the convex hull of a set of points. Can see immeadately how it would be useful to know if a set of points in Rd form a polytope, linear programming!

How can we formalize this definition?

If we're only thinking about convex polytopes, we could construct a set based on the intersection of the product spaces of the multiplication of each plane through three points and the plane orthogonal to this plane.

P = \cap_{a,b,c \in S} (ab x ac) x (the normal of that plane through a or b or c)

siddMahen

/*
 * Keeps a portion of the array sorted at all time,
 * called the invariant.
 *
 * Every time you try to sort a new element, you cmpare
 * against all the elems in the invariant, and put it in
 * its right place.
 *
 * Keep doing this until the size invariant array = size orginal
 * array.