algorithm page 2 - Dave's Blog

Search
My timeline on Mastodon

linkiblog | How to Build a Popularity Algorithm You can be Proud of

2009 Sep 9, 5:49PermalinkCommentstechnical statistics algorithms howto social tutorial math popular reddit digg programming

RFC 1951 - DEFLATE Compressed Data Format Specification version 1.3

2009 Sep 3, 7:17"This specification defines a lossless compressed data format that compresses data using a combination of the LZ77 algorithm and Huffman coding." Also see RFC 1950 zlib, a wrapper compression format that can use deflate, and RFC 1952 gzip, a compressed file format that can use deflate.PermalinkCommentstechnical rfc ietf compression http deflate gzip zlib

Timefire: On Reducing the Size of Compressed Javascript (by up to 20%)

2009 Sep 1, 4:39"...what effect does the large-scale structure of the JS output code have on the DEFLATE algorithm of GZIP which is used to serve up compressed script?" Another instance of using knowledge of the specific file type to get gains in compression. Is there a web proxy running all this at which I can point my phone?PermalinkCommentsvia:kris.kowal performance javascript gzip deflate compression web technical

DSpace@MIT : Parallel and Distributed Computation:Numerical Methods

2009 Jul 27, 5:27"Parallel and Distributed Computation:Numerical Methods", Bertsekas, Dimitri P.; Tsitsiklis, John N., 2003-11-21PermalinkCommentsprogramming mit pdf algorithm distributed parallel math todo technical

Content-Type Processing Model

2009 Jun 22, 3:12HTML5's mime-sniffing is getting moved to an IETF doc: "Many web servers supply incorrect Content-Type headers with their HTTP responses. In order to be compatible with these servers, user agents must consider the content of HTTP responses as well as the Content-Type header when determining the effective media type of the response. This document describes an algorithm for determining the effective media type of HTTP responses that balances security and compatibility considerations."PermalinkCommentsmime mime-sniffing ietf http w3c html5 technical

Michael(tm) Smith - WebKit destined to get its own content sniffer

2009 Jun 22, 3:09"Web/browser-security maven and coder Adam Barth has been working on implementing a content sniffer in WebKit, based on a content-sniffing algorithm that was originally specified in the HTML5 draft, but that's now specified as a separate IETF draft that Adam is editing and that's titled, Content-Type Processing Model."PermalinkCommentsmime mime-sniffing webkit http technical

Web addresses in HTML 5

2009 Mar 23, 11:06The HTML5 spec tells us how it is in the real world for URLs: "This specification defines various algorithms for dealing with Web addresses intended for use by HTML user agents. For historical reaons, in order to be compatible with existing Web content HTML user agents need to implement a number of processes not defined by the URI and IRI specifications [RFC3986], [RFC3987]."PermalinkCommentshtml html5 url uri reference w3c

The igraph library for complex network research

2008 Nov 5, 3:55A graphing library which includes variaous graph visualization algorithms. GNU licensed. "igraph is a free software package for creating and manipulating undirected and directed graphs. It includes implementations for classic graph theory problems like minimum spanning trees and network flow, and also implements algorithms for some recent network analysis methods, like community structure search."PermalinkCommentsreference free development programming visualization graph math library opensource c++ igraph graphviz via:mattb

[0810.5056] P is not equal to NP

2008 Oct 29, 10:22If this is true Charles Stross is going to have to rewrite a story or two.PermalinkCommentsvia:kris.kowal algorithm csc

Deriving a Non-Recursive Fibonacci Function Using Linear Algebra

2008 Aug 20, 10:51

In my Intro to Algorithms course in college the Fibonacci sequence was used as the example algorithm to which various types of algorithm creation methods were applied. As the course went on we made better and better performing algorithms to find the nth Fibonacci number. In another course we were told about a matrix that when multiplied successively produced Fibonacci numbers. In my linear algebra courses I realized I could diagonalize the matrix to find a non-recursive Fibonacci function. To my surprise this worked and I found a function.
The Nth Fibonacci value is (1 + sqrt(5))^N - (1 - sqrt(5))^N all over sqrt(5) * 2^N
Looking online I found that of course this same function was already well known. Mostly I was irritated that after all the algorithms we created for faster and faster Fibonacci functions we were never told about a constant time function like this.

I recently found my paper depicting this and thought it would be a good thing to use to try out MathML, a markup language for displaying math. I went to the MathML implementations page and installed a plugin for IE to display MathML and then began writing up my paper in MathML. I wrote the MathML by hand and must say that's not how its intended to be created. The language is very verbose and it took me a long time to get the page of equations transcribed.

MathML has presentation elements and content elements that can be used separately or together. I stuck to content elements and while it looked great in IE with my extension when I tried it in FireFox which has builtin MathML support it didn't render. As it turns out FireFox doesn't support MathML content elements. I had already finished creating this page by hand and wasn't about to switch to content elements. Also, in order to get IE to render a MathML document, the document needs directives at the top for specific IE extensions which is a pain. Thankfully, the W3C has a MathML cross platform stylesheet. You just include this XSL at the top of your XHTML page and it turns content elements into appropriate presentation elements, and inserts all the known IE extension goo required for you. So now my page can look lovely and all the ickiness to get it to render is contained in the W3C's XSL.

PermalinkCommentstechnical mathml fibonacci math

A complete break of the KeeLoq access control system

2008 Apr 4, 9:48I wonder if my car uses KeeLoq: "Hence, using the methods described by us, an attacker can clone a remote control from a distance and gain access to a target that is protected by the claimed to be "highly secure" KeeLoq algorithm."PermalinkCommentscryptography rfid security keeloq via:schneier car

Algorithmic Complexity Attacks

2008 Mar 28, 10:35Scott A Crosby and Dan S Wallach "present a new class of low-bandwidth denial of service attacks that exploit algorithmic deficiencies in many common applications' data structures." DoS via worst case behavior in hash tables and exponential time RegExp'sPermalinkCommentsscott-crosby dan-wallach dos programming regex research security hash

CASCADES project: Cost-effective Outbreak Detection in Networks

2007 Nov 7, 9:41Algorithm to tell you which blogs to read to be the most up to date. Graphs which blogs aggregate from other blogs.PermalinkCommentsinformation graph network news blog

Universal Turing Machine in XSLT

2007 May 1, 6:04A turing machine implemented as an XSLT. A great way to show that XSLT is turing complete.PermalinkCommentsxslt turing turing-machine turing-complete algorithm xml programming

WordNet - Princeton University Cognitive Science Laboratory

2007 Apr 19, 3:41"WordNet is a large lexical database of English... Nouns, verbs, adjectives and adverbs are grouped into sets of cognitive synonyms (synsets), each expressing a distinct concept...The resulting network of meaningfully related words and concepts can be navPermalinkCommentsalgorithm collections etymology dictionary visualization xml language ontology tool free

Good Math, Bad Math : Prime Number Pathology: Fractran

2007 Apr 12, 2:04A programming language expressed and evaluated with prime numbers.PermalinkCommentsmath prime programming language algorithm turing

Articles / Classic Texts in Computer Science

2007 Feb 25, 2:46Classic articles and texts on Computer Science.PermalinkCommentsbooks article algorithm documentation csc

FolkRank: A Ranking Algorithm for Folksonomies

2007 Feb 20, 1:07Abstract: "We present a formal model and a new search algorithm for folksonomies, called FolkRank, that exploits the structure of the folksonomy. The proposed algorithm is also applied to find communities within the folksonomy and is used to structure sePermalinkCommentsfolksonomy folkrank algorithm article rank sort social tag tagging

GRDDL Primer

2006 Nov 28, 3:24GRDDL is a mechanism for Gleaning Resource Descriptions from Dialects of Languages. It is a technique for obtaining RDF data from XML documents and in particular XHTML pages. Authors may explicitly associate documents with transformation algorithms, typicPermalinkCommentsreference w3c web xml rdf metadata grddl semanticweb

John Resig - Javascript Diff Algorithm

2006 Nov 6, 4:50A Javascript lib that does diff for you. Could be useful in implementing cool AJAX-y clientside things. Also has link to ACM paper describing the diff algorithm used.PermalinkCommentsacm ajax algorithm article blog code development diff javascript library programming reference
Older EntriesNewer Entries Creative Commons License Some rights reserved.