scribeGriff Studios

Books • Algorithms • Dart • HTML5 • CSS3

To content | To menu | To search

Strongly Connected Components and the 2-SAT Problem in Dart

We develop an algorithm to compute the strongly connected components of a directed graph on large graph sizes using the...

Continue reading

Exploring the Partial Sums of Fourier Series with Dart

I've always been rather fascinated by the concept that just about any signal can be decomposed into a weighted...

Continue reading

A Linear Time, Randomized Selection Algorithm in Dart

While developing a signal processing library for Dart, we realized we had a need for an efficient and flexible way of...

Continue reading

Having Fun with Dart, AJAX, and JSON

Getting distracted building a tabbed panel feed reader in Dart using AJAX, JSON and CORS was a lot of fun. The RSS feed...

Continue reading

Strongly Connected Components and the 2-SAT Problem in Dart

We develop an algorithm to compute the strongly connected components of a directed graph on large graph sizes using the iterative version of our Kosaraju class. We then make use of this algorithm to solve, in linear time, a special case of the boolean satisfiability problem, known as the 2-SAT problem. Computational times of this algorithm are reported for directed graphs in excess of 5 million edges and 2-SAT data structures with up to a 1 million clauses and an equal number of variables.

Continue reading

Algorithms in Dart: Kosaraju's Algorithm

Let's apply our DirectedGraph class to one of the most well known of graph algorithms - Kosaraju's algorithm for finding strongly connected components of a directed graph. The algorithm performs two passes of a depth first search (DFS) - the first on a directed graph will all arcs reversed and the second on the original graph. The second DFS discovers the strongly connected components by traversing the nodes in the original graph in the reverse order of their finishing times returned by the first DFS on the transformed graph.

Continue reading

Collections in Dart: The Directed Graph

A directed graph, or digraph, can be considered as a set of objects with pairwise connections with a defined orientation. For example, a one way street on a map, outbound or inbound links between web pages, and dependencies in software modules. Real world digraphs tend to be sparse and, as a result, the proper representation of the digraph involves a tradeoff between the efficient use of memory and the ease of graph manipulation.

Continue reading

Exploring the Partial Sums of Fourier Series with Dart

I've always been rather fascinated by the concept that just about any signal can be decomposed into a weighted collection of elementary basis functions. My undergraduate linear systems professor would refer to these basis functions as CCFSs (cleverly chosen fundamental signals). But what makes a basis function cleverly chosen?

Continue reading

A Linear Time, Randomized Selection Algorithm in Dart

While developing a signal processing library for Dart, we realized we had a need for an efficient and flexible way of retrieving the kth element of an unsorted array, commonly referred to as the kth order statistic. In this article, we discuss the well known randomized selection algorithm which achieves an average running time for selection of O(n).

Continue reading

Having Fun with Dart, AJAX, and JSON

Getting distracted building a tabbed panel feed reader in Dart using AJAX, JSON and CORS was a lot of fun. The RSS feed from this blog is accessed using an HttpRequest and then CORS is used for displaying which projects on Github I'm watching. The two feeds are then packaged into a small tabbed panel widget and compiled to JavaScript. This allows it to be embedded into a web page and viewed with any modern browser.

Continue reading

Using the HTML5 <input> range Attribute with the Timer Class in Dart

HTML5 adds a number of useful type attributes for the <input> tag, including fields for validating email addresses, entering dates, and providing a color picker. Although browser adoption has so far been somewhat inconsistent as of this writing, one attribute that has been of particular interest is the range attribute, more commonly referred to as the slider.

Continue reading

Keeping Time with Dart - The Stopwatch, DateTime and Timer Classes

The ability to determine time of day, the date, or to calculate elapsed time is just one of several fundamental capabilities to be found in just about every modern programming language. We frequently need to answer the question "when did this event happen?" or "how long has it been since this other event happened?". Dart's time keeping methodology is divided among the Stopwatch, DateTime and Timer classes.

Continue reading

Using Optional Parameters in a Subclass - AS3 versus Dart

Dart and AS3 both allow child classes to have their own constructor methods. Recall that constructor methods act to initialize an instance by executing the methods necessary to perform various setup tasks. Constructor methods are also responsible for initializing variables. When a constructor method resides in a subclass, it calls the constructor method of its parent by using the keyword super.

Continue reading

The Dart Programming Language for Non-Programmers - Errors and Warnings

An exception is an event, which occurs during the execution of a program, that disrupts the normal flow of the program's instructions. When an error occurs during the execution of a program, an error object, called an exception object, is created. The creation of this object is known as throwing an exception.

Continue reading