Dijkstra's Shunting Yard in Typescript

The shunting yard algorithm converts infix expressions (i.e. 1+2) into reverse Polish notation, i.e. 1 2 +, which lends itself well to execution on a stack machine. An aside: I wanted to revisit this algorithm because it was one of the first I implemented in C during self-study five years ago. In a way, reimplementing it is a way of measuring my progress since then. The internal details aren’t too complicated - it’s based on the simple pseudo-code of the Wikipedia article describing the shunting yard algorithm.

Bay Area SSC Meetup

I’m in SF for the summer, and I was thus able to attend the Slate Star Codex meetup this year in Dolores Park. Met a lot of interesting people, and got to meet Scott. While I’m in the Bay Area I hope to get a little more involved in that scene. Picture is of the park, not the meetup specifically.

Pythagorean Triple Problem in Sub-linear Time

The Pythagorean triple problem is as follows. Given an input integer \(n\), return integers \(a\), \(b\), \(c\) such that the two following conditions hold: $$ a b c = n $$ $$ a^2 + b^2 = c^2 $$ I was interested in finding a solution to this problem that was both succint and had good asymptotic complexity. The solution I found runs in O(sqrt(n)) time by deconstructing the problem into the well-known 3SUM problem.

Mathematica Steps to LaTeX [WiP]

A common problem when using Mathematica to derive expressions is similar to a big problem plaguing machine learning algorithms today: It is difficult or impossible to explain the result due to the internal complexity of the black-box which generates it. Mathematica’s internal algorithms for performing various symbolic computation are built for speed, not simplicity, and in many cases the method Mathematica uses is nothing like the manual way humans would find the solution.

Quadtree Particle Simulation

A small particle simulation was written in JS, utilizing a simplified (constant depth) quadtree structure. The model includes forces between nearby particles, so rather than invoke a O(n^2) operation to compute the net force for each particle, a quadtree is used so each particle may efficiently access its neighbors. The forces used are tuned to provide some amount of clustering, but also to provide global homogeneity to prevent too many particles appearing in one quadtree section (which would decrease cpu-time efficiency).

Double Pendulum

This is a simulation of 2 bobs, connected by massless, perfectly rigid rods to a central pivot under the force of uniform gravity. In addition to being the motivating example for chaotic systems (in addition to the Lorenz system, its fluid mechanics counterpart), the double pendulum represents some interesting challenges. Draw circle bounds Draw cherry tracer Draw connections Pause Clear cherry tracer Simulation parameters: Angle 1 Angle 2

Oriented Bounding-Box Heuristic

The 2-dimensional minimum-area oriented bounding box problem is as follows: Given a set of coplanar points, how can we efficiently find the smallest rectangle which encloses these points? Additionally, that rectangle can be oriented at any angle with respect to the coordinate system. One interesting estimate for the solution, which guarantees “pretty good” results in O(n) time is a natural extension of orthogonal linear regression. Specifically, we assume that the minimum rectangle is aligned to the orthogonal “line of best fit” of the point set.

2019 Presidential Luncheon

This last Wednesday I had the honor of attending a luncheon with ODU’s current president John R. Broderick. This event was a meetup with the local Tau Beta Pi engineering honor society chapter. The food was delicious! We were able to talk to Broderick about current events on campus, and suggestions we had (especially with regard to on-campus parking). Group photo included.

One-Dimensional Linear Regression

The simple linear regression algorithm is a closed-form solution to a least-squared distance minimization problem. Here is demonstrated the one-dimensional case of simple linear regression. $$ \min_{\alpha,\beta} \sum_{i=1}^{n} (y_i - \alpha - \beta x_i)^2 $$ Click and drag the black points to affect the regression. Double click to add or remove points. The blue point in the center represents the geometric average, through which the fit always passes through.

Quadratic Bezier Curves

Quadratic Bézier curves are explicit parametric functions of the following form: $$ x(t) = (1-t)^2 x_0 + 2t(1-t) x_1 + t^2 x_2\\ y(t) = (1-t)^2 y_0 + 2t(1-t) y_1 + t^2 y_2\\ t \in \mathbb R[0,1] $$ These curves are perhaps the simplest class of parametric curves, but useful in their own right. This is a small demo of such curves. Drag the control points around to see the curve change.