Lights Out

Two months ago, I got to use D3 to help visualize the steps for getting something approved and interact with these steps. I affectionally call my code Roadmap.

roadmap-screenshot
An everyday example.

I had a great time because (1) the way we draw things in D3 reminded me of Matlab, whom I will always love; (2) I got to re-learn graph theory (fun fact: all digraphs have a topological sort—being able to sort is always nice and being able to in linear time even more so); and (3) I got to play with Post-it notes to make up an algorithm for drawing graphs on desktop and mobile.

roadmap-planning.jpg
Office supplies to the rescue.

I also had a hard time finding out how to use D3 in Ember. Because Ember is rather a rare species, there was only 1 tutorial that helped me understand what I needed to do. Thanks to that tutorial, I was able to create a prototype of Roadmap over a weekend, use Ember’s mixin feature effectively, and write extensive tests to show that Roadmap really works. In case you want to learn Ember and D3, let me show you what I learned.

We will create a game from the 90s called Lights Out. The game consists of a 5 x 5 grid of lights, which you can press like buttons. When the game starts, some of the lights are on. When you press a light, that light and its adjacent ones—top, right, bottom, and left, if they exist—are switched from on to off, or off to on. The goal of the game is for you to turn off all lights, preferably in as few moves as possible.

Continue reading “Lights Out”

Advertisements

Mai Retrospective

Mai is an app that I created with Jason, Brian, David, and John at our coding bootcamp. With Mai, you can post photos and share stories, much like Facebook and Instagram. Mai takes one step further by writing the stories for you.

Continue reading “Mai Retrospective”

Metric and Probability-Based Recommendations

How many of you like to eat, play, and most importantly, drink? (Hopefully, everyone!)

I helped create an app called LocALL. It gives 50,000 recommendations for short trips to eat, play, and drink and support local businesses in Austin. We can extend our app to cover ~400 metropolitan cities in the US and create 20 million recommendations. (Big data and machine learning!)

At the heart of our solution is math. We used spherical geometry and probability to create simple, fast recommendations.

Continue reading “Metric and Probability-Based Recommendations”

Iterative Methods: Part 3

Let’s look at one more way to solve the equation A\vec{x} = \vec{b}. We assume that A \in \mathbb{R}^{n \times n} is nonsingular, and define the k-th Krylov subspace as follows:

\mathscr{K}_{k} \,:=\, \mbox{span}\{\vec{b},\,A\vec{b},\,\cdots,\,A^{k - 1}\vec{b}\}.

Krylov subspace methods are efficient and popular iterative methods for solving large, sparse linear systems. When A is symmetric, positive definite (SPD), i.e.

\left\{\begin{array}{l} A^{T} = A \\[12pt] \vec{x}^{T}A\vec{x} > 0,\,\,\,\forall\,\vec{x} \neq \vec{0}, \end{array}\right.

we can use a Krylov subspace method called Conjugate Gradient (CG).

Today, let’s find out how CG works and use it to solve 2D Poisson’s equation.

Continue reading “Iterative Methods: Part 3”

Iterative Methods: Part 2

Last time, we looked at 2D Poisson’s equation and discussed how to arrive at a matrix equation using the finite difference method. The matrix, which represents the discrete Laplace operator, is sparse, so we can use an iterative method to solve the equation efficiently.

Today, we will look at Jacobi, Gauss-Seidel, Successive Over-Relaxation (SOR), and Symmetric SOR (SSOR), and a couple of related techniques—red-black ordering and Chebyshev acceleration. In addition, we will analyze the convergence of each method for the Poisson’s equation, both analytically and numerically.

Continue reading “Iterative Methods: Part 2”