Lecture 3 Notes: MIT Linear Algebra (18.06) [Multiplication and Inverse Matrices]

Important Points and Concepts

– When are 2 matrices multipliable? And what would the result look like?

– What are the ways we can multiply 2 matrices?

– What is an inverse matrix? And how do we find it?

Multiplication

When are 2 matrices multipliable? And what would the result look like?

Let A be an m x n matrix and B an n x m matrix. Can we multiply A and B?

An easy way to tell if 2 matrices are multipliable is to check if the number of columns of the matrix A is equal to the number of rows of matrix B. If they are, we can multiply them. The output will have the have the same number of rows as A and the same number of columns as B.

(m x n)(n x m) = m x m

In this case, AB will result in an m x m matrix, let’s call it C.

Let’s do another quick example: A(m x  n)B(n x p) = C(???)

Matrix A is an m x n matrix and B is an n x p matrix. First, can we multiply them? And if so, what would the output look like in terms of rows and columns?

We can see that A has n rows, B has n columns, which means that we can multiply these 2 matrices. C would have the number of rows of A (m) and the number of columns in B (p). Therefore, C would be an m x p matrix.

What are the ways we can multiply 2 matrices?

Ways to multiply

\Bigg[ \hphantom{-}  \begin{matrix}  1 & 2 & 3 \\  4 & 5 & 6  \end{matrix}  \hphantom{-}\Bigg]  \Bigg[ \hphantom{-}  \begin{matrix}  7 & 8 \\  9 & 10 \\  11 & 12  \end{matrix}  \hphantom{-}\Bigg]  \hphantom{-}  =  \hphantom{-}  ???

These matrices are multipliable, the result is an 2 x 3 matrix.

Let’s call the first matrix P, the second matrix Q and the resulting matrix Z.

What are the ways we can multiply 2 matrices?

Dot product (standard way)

To find the top left number of Z, we take the first row of P [1, 2, 3] and the first column of Q [7, 9, 11]. We perform an operation called the dot product, which looks like this: (1, 2, 3) * (7, 9, 11).

The operation produces (1 * 7) + (2 * 9) + (3 * 11) and the top left number of Z results in 58.

For the top right value, we perform the same operation with the same row [1, 2, 3] but a different column. Instead we use the second column of Q [8, 10, 12] since we are trying the find the (1, 2) value of Z. Notice how change which row and column we are multiplying based on the row and column of Z.

The operation produces this: (1 * 8) + (2 * 10) + (3 * 12) and the top left number of Z is 64.

I won’t solve it all the way, but you get the idea. For the bottom left of Z (2, 1), we’d be taking the dot product of the second row of P and the first column of the Q.

Column Way (columns of Z are combinations of columns of P)

How do we multiply a matrix by a column?

Let’s find the first column of Z: P times first column of Q.

And that’s it, we repeat this process for each column of Q to produce each column of Z.

Row way (rows of  Z are combinations of rows of Q)

How do we multiply a row by a matrix?

Let’s find the first column of Z: the first row of P times Q.

Very similar to the column way. We repeat this process for each row of P.

Columns x Rows

Columns of P times a row of Q = (2 x 1) x (1 x 3). We get a 2 x 3 matrix.

A quick example:

\Bigg[ \hphantom{-}  \begin{matrix}  2 \\  3 \\  4  \end{matrix}  \hphantom{-}\Bigg]  \Bigg[ \hphantom{-}  \begin{matrix}  1 & 6  \end{matrix}  \hphantom{-}\Bigg]  \hphantom{-}  =  \hphantom{-}  \Bigg[ \hphantom{-}  \begin{matrix}  2 & 12 \\  3 & 18 \\  4 & 24  \end{matrix}  \hphantom{-}\Bigg]

The first row of the result [2 * 1, 2 * 6] is [2, 12]. The second row is [3 * 1, 3 * 6] is [3, 18] and the third row is [4, 24]. The pattern is easy to see.

Block

Let’s say we want to multiply matrices A and B, both are 20 x 20 matrices. The main concept is that we can break up matrices  into blocks. We can break up A into 4 10 x 10 matrices and B into 4 10 x 10 matrices. Simply multiply the top left blocks of A and B, and we get the top left matrix of the resulting matrix (AB).

Inverses

What is an inverse matrix? And how do we find it?

Let A be a square matrix.

A^{-1} A = I  \\  AA^{-1} = I

The inverse of A times A is the identity matrix, I. And this works both ways for square matrices only.

A matrix has no inverse if

– The determinant is zero (the left diagonal numbers multiplied together minus the right diagonal multiplied together is zero)

– Both columns lie on the same line (for example if the second column in a 2 x 2 matrix is a multiple of the first)

– you can find a vector x with Ax = 0, (x!=0)

Gauss – Jordan (solve 2 equations at once)

Solve for the inverse.

\Bigg[ \hphantom{-}  \begin{matrix}  1 & 3 \\  2 & 7  \end{matrix}  \hphantom{-}\Bigg]  \Bigg[ \hphantom{-}  \begin{matrix}  a & b \\  c & d  \end{matrix}  \hphantom{-}\Bigg]  \hphantom{-}  =  \hphantom{-}  \Bigg[ \hphantom{-}  \begin{matrix}  1 & 0 \\  0 & 1  \end{matrix}  \hphantom{-}\Bigg]

First, create an augmented matrix that includes the identity.

\Bigg[ \hphantom{-}  \begin{matrix}  1 & 3 & 1 & 0 \\  2 & 7 & 0 & 1  \end{matrix}  \hphantom{-}\Bigg]

Recreate the identity matrix on the left side of this matrix using elimination and the right side will become the inverse.

\Bigg[ \hphantom{-}  \begin{matrix}  1 & 3 & 1 & 0 \\  2 & 7 & 0 & 1  \end{matrix}  \hphantom{-}\Bigg]    \rightarrow    \Bigg[ \hphantom{-}  \begin{matrix}  1 & 3 & 1 & 0 \\  0 & 1 & -2 & 1  \end{matrix}  \hphantom{-}\Bigg]    \rightarrow    \Bigg[ \hphantom{-}  \begin{matrix}  1 & 0 & 7 & -3 \\  0 & 1 & -2 & 1  \end{matrix}  \hphantom{-}\Bigg]

The process is elimination the usual way, top down. Once we reach the bottom, we perform elimination bottom up to reproduce the identity matrix.

And you can see, the right side becomes the inverse of our original matrix.

EA = I \rightarrow E = A^{-1}

Advertisements

Lecture 2 Notes: MIT Linear Algebra (18.06) [Elimination with Matrices]

Elimination with Matrices

Important point: A matrix times a column is a column, a matrix times a row is a row

Given the following equations, solve for x, y, and z using elimination and back substitution:

\hphantom{3}x + 2y + z = 2  \\  3x + 8y + z = 12  \\  \hphantom{3x +} 4y + z = 2

We start by forming our matrix, leaving out the right side of the equations.

\Bigg[ \hphantom{-}  \begin{matrix}  1 && 2 && 1 \\  3 && 7 && 1 \\  0 && 4 && 1  \end{matrix}  \hphantom{-}\Bigg]

Elimination (success/failure)

Using elimination, our goal is to turn our original matrix into one that looks like this where n represents some arbitrary number:

\Bigg[ \hphantom{-}  \begin{matrix}  n && n && n \\  0 && n && n \\  0 && 0 && n  \end{matrix}  \hphantom{-}\Bigg]

To get to this destination we:
– go row by row
– keep the first row
– determine what number multiplied to the row above when subtracted
by the current row will get us closer our destination matrix

Step by step, here are what the matrices will look like

\Bigg[ \hphantom{-}  \begin{matrix}  1 && 2 && 1 \\  3 && 7 && 1 \\  0 && 4 && 1  \end{matrix}  \hphantom{-}\Bigg]    \rightarrow    \Bigg[ \hphantom{-}  \begin{matrix}  1 && 2 && 1 \\  0 && 2 && -2 \\  0 && 4 && 1  \end{matrix}  \hphantom{-}\Bigg]    \rightarrow    \Bigg[ \hphantom{-}  \begin{matrix}  1 && 2 && 1 \\  0 && 2 && -2 \\  0 && 0 && 5  \end{matrix}  \hphantom{-}\Bigg]

Let’s start with our original matrix.

We keep the first row, so we take a look at the second row. We ask ourselves: What must I do to the first row ([1, 2, 1]) such that when subtracted by the second row ([3, 8, 1]), the first number is a zero? Our aim is to get a row that look like this ([0, n, n], again n being any arbitrary number). The answer is that we must multiply the first row by 3, which will give us [3, 6, 3]. We then subtract this by the second row to give us [0, 2, -2]. We now work with this new matrix when going to the third row.

We repeat this step for our new matrix.

We have to get a row that looks like [0, 0, n]. As we can see, we’re already halfway there since we were given the first 0 to begin with. Same process for the other 0: what must I do to the row above ([0, 2, 2]) such that when subtracted by the third row ([0, 4, 1]) the first two numbers are zero? Similar to the process above, we must multiply the second row by 2, which will give us [0, 4, -4]. We then subtract this by the third row to give us [0, 0, 5]. Now, we have our final matrix.

Pivot numbers

The diagonal line of numbers starting from the top-left (1, 2, 5) are called pivot numbers. An important note is that if any of these numbers were zero to start with, we would have to switch rows around and try again.

Right hand side

Notice we haven’t touched the right side of the equations yet, but that’s an easy step to do afterwards. This is also the way software solves systems of equations.

Let’s take our matrices we solved through and let’s augment them by including the numbers from the right hand side of the equations. These matrices are known as augmented matrices.

\Bigg[ \hphantom{-}  \begin{matrix}  1 && 2 && 1 & 2\\  3 && 7 && 1 & 12\\  0 && 4 && 1 & 2  \end{matrix}  \hphantom{-}\Bigg]    \rightarrow    \Bigg[ \hphantom{-}  \begin{matrix}  1 && 2 && 1 & 2\\  0 && 2 && -2 & 6\\  0 && 4 && 1 & 2  \end{matrix}  \hphantom{-}\Bigg]    \rightarrow    \Bigg[ \hphantom{-}  \begin{matrix}  1 && 2 && 1 & 2\\  0 && 2 && -2 & 6\\  0 && 0 && 5 & -10  \end{matrix}  \hphantom{-}\Bigg]

You get the new fourth column by following a similar process of taking the multiplier, multiply the number above the row in question and subtracting the current row number by that value.

For example, the number we multiplied the first row in the un-augmented matrices was a 3. We start in the second row and multiply the 2 in the first by 3 to make 6. Subtract the 12 in the second row by the 6 and we get 6, which is our new second row value.

Back Substitution

Our new equations are:

\hphantom{3}x + 2y + z = 2  \\  \hphantom{3x +} 2y + -2z = 6  \\  \hphantom{3x + 2y +} 5z = -10

Very simple from this point, start with the last equation and move up, solving for a variable at a time. The solutions turns out to be: z = -2, y = 1, x = 2.

Elimination Matrices

Let’s use the first and second matrices of our un-augmented matrices as an example. What matrix do I multiply the first matrix by to get the second matrix? How do I subtract 3x from row 1 from row 2?

\Bigg[ \hphantom{-}  \begin{matrix}  1 && 0 && 0\\  0 && 1 && 0\\  0 && 0 && 1  \end{matrix}  \hphantom{-}\Bigg]    \Bigg[ \hphantom{-}  \begin{matrix}  1 && 2 && 1\\  3 && 7 && 1\\  0 && 4 && 1  \end{matrix}  \hphantom{-}\Bigg]    =    \Bigg[ \hphantom{-}  \begin{matrix}  1 && 2 && 1\\  0 && 2 && -2\\  0 && 4 && 1  \end{matrix}  \hphantom{-}\Bigg]

We’ll start with the identity matrix which when multiplied by some matrix, gives you back that same matrix. We need to fix this so that we have 3 of row 1 subtracted from row 2. Here is the solution.

\Bigg[ \hphantom{-}  \begin{matrix}  1 && 0 && 0\\  -3 && 1 && 0\\  0 && 0 && 1  \end{matrix}  \hphantom{-}\Bigg]    \Bigg[ \hphantom{-}  \begin{matrix}  1 && 2 && 1\\  3 && 7 && 1\\  0 && 4 && 1  \end{matrix}  \hphantom{-}\Bigg]    =    \Bigg[ \hphantom{-}  \begin{matrix}  1 && 2 && 1\\  0 && 2 && -2\\  0 && 4 && 1  \end{matrix}  \hphantom{-}\Bigg]

Matrix Multiplication

Important point: Matrices are noncommutative, so order matters!

How to switch rows of a matrix

\Bigg[ \hphantom{-}  \begin{matrix}  0 & 1\\  1 & 0  \end{matrix}  \hphantom{-}\Bigg]    \Bigg[ \hphantom{-}  \begin{matrix}  a & b\\  c & d  \end{matrix}  \hphantom{-}\Bigg]    =    \Bigg[ \hphantom{-}  \begin{matrix}  c & d\\  a & b  \end{matrix}  \hphantom{-}\Bigg]

Inverses

How to undo elimination: Simply switch a sign to get back to the identity matrix

\Bigg[ \hphantom{-}  \begin{matrix}  1 && 0 && 0\\  3 && 1 && 0\\  0 && 0 && 1  \end{matrix}  \hphantom{-}\Bigg]    \Bigg[ \hphantom{-}  \begin{matrix}  1 && 0 && 0\\  -3 && 1 && 0\\  0 && 0 && 1  \end{matrix}  \hphantom{-}\Bigg]    =    \Bigg[ \hphantom{-}  \begin{matrix}  1 && 0 && 0\\  0 && 1 && 0\\  0 && 0 && 1  \end{matrix}  \hphantom{-}\Bigg]

Lecture 1 Notes: MIT Linear Algebra (18.06)

The Geometry of Linear Equations

Ax = b is a big theme.
A = matrix, x = vector of unknowns, and b = solution vector or point

Main questions:
Can I solve Ax = b for every b?
Do the linear combinations of the columns fill 3D space? (for our 3D example below, yes it does)

2 equations, 2 unknowns

Find the x and y values that satisfy both equations.

\hphantom{-}2x - y = 0  \\  -x + 2y = 3

Row Picture

The coefficients of the left side of the first equation become the first row of the first matrix. The coefficients of the the left side of the second question become the second row of the first matrix.

First equation coefficients are -2 and -1.
Second equation coefficients are -1 and 2.
Both are displayed below in their own matrix.

Next is the vector containing the 2 unknowns: x and y.

Lastly the matrix times the vector (also known as taking the dot product)
is equal to the vector containing the numbers on the right side of the given equations.

\Bigg[  \begin{matrix}  \hphantom{-}2 & -1 \\  -1 & \hphantom{-}2  \end{matrix}  \hphantom{-}\Bigg]    \Bigg[  \begin{matrix}  \hphantom{-}x   \hphantom{-}y  \end{matrix}  \hphantom{-}\Bigg]    \hphantom{-}=  \hphantom{-}\Bigg[  \begin{matrix}  \hphantom{-}0  \hphantom{-}3  \end{matrix}  \hphantom{-}\Bigg]

With the column picture, you plot the lines, see where they intersect and that is your solution: x = 1, y =2.

Column Picture

Take the first and second columns from the previous matrix and multiply them by their corresponding unknown: x and y. Add these vectors together and have them equal to the same previous vector.

x\Bigg[  \begin{matrix}  \hphantom{-}2  -1  \end{matrix}  \hphantom{-}\Bigg]    \hphantom{-}+ \hphantom{-}y\Bigg[  \begin{matrix}  -1   \hphantom{-}2  \end{matrix}  \hphantom{-}\Bigg]    \hphantom{-}=  \hphantom{-}\Bigg[  \begin{matrix}  \hphantom{-}0  \hphantom{-}3  \end{matrix}  \hphantom{-}\Bigg]

When we plot these vectors and use the answer x = 1, y = 2 from from before, we start by putting together 1 of the x vectors and 2 of the y vectors. The vector between the beginning point and the ending point is your solution. Again x = 1, y = 2.

The solutions from the column and row pictures are easy to see at this point, no reason to use one over the other when dealing with 2 equations and 2 unknowns. Now on the 3 equations and 3 unknowns.

3 equations, 3 unknown

\hphantom{-}2x - y \hphantom{-0z}= 0  \\  -x + 2y - z = -1  \\  \hphantom{-0x}-3y + 4z = 4

Row Picture

Same process as above. However, when it comes to plotting the 3 planes and finding the intersecting point, it gets tricky to visualize.

Column Picture

A ton easier when it comes to plotting, only 3 vectors need to be plotted. It’s a lot easier to visualize and to find the solution vector.

Learn Famo.us [part 2]: Displaying and Positioning Elements

In part 2 of my series on Famo.us, it’s day 1 of the thesis project of Hack Reactor and the Famo.us HQ is amazing! WP_20140729_006   An entire side of the building on the Penthouse Suite + Patio with a view + Free food + Showers = Can I live here? Unfortunately, I can only stay as long as late as the last employee each night…

During our first day, we took an in-depth dive to Famo.us University, it was much more detailed and nicely explained the nuances not touched in the tutorials. For this post, I decided to go really in-depth as well due to the lack of documentation and resources out there. Simply put, I want this to be the best resource for those now starting to learn Famo.us.

What is a Surface?

A Surface is a renderable. In laymen terms, a renderable is something you can to the main context (more on this later) and see on the screen. The function of a surface is to display, visually, the data you give it. Surfaces have no knowledge of its position on the screen or its opacity. Also, in terms of the render tree (will write a post on this soon, in the meantime, read this), you can think of a surface as a leaf. You cannot add anything to a leaf in a tree.

How to create a surface Creating a surface is simple. Just require the surface class and use the new keyword. I’ve also included the boilerplate code that is required with almost every Famo.us app.

define(function(require, exports, module) {

  // main requires
  var Engine  = require('famous/core/Engine');
  var Surface = require('famous/core/Surface');

  // create the main context
  var mainContext = Engine.createContext();

  // create a new surface and
  // pass in the options object
  var mySurface = new Surface({
    size: [100, 100],
    content: 'Hello Famo.us!',
    properties: {
      backgroundColor: 'red',
      color: 'white'
    }
  });

  // add our surface to the mainContext
  // so we can see it on the screen
  mainContext.add(mySurface);

});

Size. You can define the size [width, height] in pixels inside of the options object. A size of [100, 100] is 100 pixels wide and 100 pixels long. You can also pass in true, for example a size of [true, true] would be just enough space for the content. And a size of [undefined, undefined] will take up the entire screen and also resize accordingly. You can also interchange the true and undefined with specific pixel values. A size of [500, undefined] would be a surface that is 500 pixels wide but is as long as the screen. Stringified percentages (‘50%’) can also be used.

Content. of the content, you can use HTML to help with formatting. Trying passing in ‘Hello Famo.us!’ to see the effect. You can also attach an image using a div with a src to the picture url (ImageSurface would be better in this situation).

Properties. For those with more CSS experience, you can pass in CSS in the properties object. It’s a little different though with camelCase instead of dashes. For example, background-color -> backgroundColor.

Other. You can add classes to surfaces and apply CSS that way. You can use different classes that extend from surfaces such as a CanvasSurface, ContainerSurface, ImageSurface, InputSurface, TextareaSurface and VideoSurface. I won’t go into these in this post, but just know that they exist and that some might be better suited for your situation.

What is a Modifier?

A Modifier is also a renderable. It can be applied to the main context to change the position and other properties, such as opacity, of surfaces. In terms of the render tree, modifiers will affect anything below it on the same branch. And unlike surfaces, modifiers can be chained together. You can have as many modifiers affecting a surface or a group of surfaces as you want.

How to create a Modifier We’ll use the same code as above and add in a StateModifier.

define(function(require, exports, module) {

  // main requires
  var Engine     = require('famous/core/Engine');
  var Surface    = require('famous/core/Surface');
  var Modifier   = require('famous/modifiers/StateModifier');
  var Transform  = require('famous/core/Transform');

  // create the main context
  var mainContext = Engine.createContext();

  // create a new surface and
  // pass in the options object
  var mySurface = new Surface({
    size: [100, 100],
    content: 'Hello Famo.us!',
    properties: {
      backgroundColor: 'red',
      color: 'white'
    }
  });

  // now let's create a modifier
  // and pass in some options
  var myModifier = new Modifier({
    origin: [0.5, 0.5],
    align: [0.5, 0.5],
    transform: Transform.rotateZ(10)
  });

  // add our surface (and now our modifier as well!)
  // to the mainContext so we can see it on the screen
  mainContext.add(myModifier).add(mySurface);

});

The modifier we applied will simply set the origin and align to [0.5, 0.5] effectively centering the red surface on the screen. It also resizes according to the screen size, maintaining its center position.

Kyle’s analogy. Say you have a cork board (the brown board you stick push pins in) on the wall. We’ll let this represent the main context. Now let an index card represent a surface. You want to add the index card in the bottom left of the cork board. How would you do this in Famo.us?

Origin vs Align. By understanding the difference between the two, you can position surfaces effectively on the screen. In the above example, you can control where you stick the push-pin through the index card with origin. And you can control where you place the index card (currently with the push-pin through it) on the cork board using align. In more technical terms: origin controls the child anchor and the align controls the parent anchor. Be sure to always include an align if you set the origin since the align, by default, is set to the origin.

Transform. You can also rotate and translate using Transform.rotate and Transform.translate. You can rotate in a single dimension by doing Transform.rotateX(), Transform.rotateY(), Transform.rotateZ() or rotate all at once by doing Transform.rotate(x, y, z). Transform.translate(x, y, z) works in a similar fashion. I recommend playing around with the rotations and translations to get a better feel for using Transform. An interesting distinction is that translate is in pixels and rotation ranges from 0 to 2π.

Chaining. You can apply as many modifiers as you want to the context. The way it works is that any surface below modifiers on the render tree will be affected by those modifiers. This covers the basics on surfaces and modifiers.

In my future posts, I will explain the render tree with visuals and  show more practical code examples. Also, I am working on compiling every last bit of information and learning resource there is on Famo.us into a post. Subscribe if you’d like access.

Learn Famo.us [part 1]: What is Famo.us?

 

What is Famo.us?

famo.us_pic

Famo.us is an open source (soon to be open development) JS framework capable of rendering to HTML, Canvas, and WebGL. It’s been in the works for a couple of years and was released a few months ago (April 9th).

Located in San Francisco, it was founded by Steve Newcomb (sold Bing to Microsoft) and Mark Lu (Berkeley graduate). They have $30MM in funding.

Steve and Mark’s goal for founding Famo.us

To build the ultimate JavaScript development platform
– free & open source
– fixes the performance problems of HTML5
– enables rendering to DOM, Canvas and WebGL
– multi-view capable
– controls animation with a physics engine
– enables designers with new tools for animation
– enables junior engineers to use widgets
– enable senior engineers to build their own primitives
– can build apps and games
– works on phones, tablets, computers and televisions
– one code base, deploy everywhere [1]

Famo.us core
1) a 3D rendering engine
2) a 3D physics engine
3) a gesture engine for touch, mouse, keyboard, and Leap Motion
4) a multi-view engine

With Famo.us, you can create near-native (60 FPS) experiences in web + mobile apps by writing very little code.

Famo.us enables application developers to build beautiful native speed based apps and games in HTML5 that take advantage of famo.us’ 3D rendering, 3D physics, multi-screen and gesture engines. Designers can access the motion via the physics engine without coding, application developers can build quickly using app templates and widgets without worrying about performance and platform engineers can build their own primitives from scratch with direct source code access to the full power of the famo.us engines. [1]

Much more to come on Famo.us, expect code walkthroughs, tutorials, and extensive documentation of Famo.us’ Github examples.

Sources
[1] – angellist

Frequently Asked Question
– The basics
The tough questions

Installing PostGreSQL database on Microsoft Azure Virtual Machine

azure_logo

Login to Microsoft Azure.

Create a new virtual machine

  1. Click on the ‘+ New’ in the lower left corner
  2. Select Compute -> Virtual Machine -> From Gallery
  3. Tab 1: Use an Ubuntu 12.04 LTS image
  4. Tab 2: Keep default settings, type in ‘Virtual Machine Name’ and a password (I didn’t use the SSH certificate)
  5. Tab 3: Keep default settings, change region, choose a DNS name and create a TCP endpoint called ‘postgres’ (port #’s don’t matter)
  6. Tab 4: Nothing to change here, click the checkmark and wait a few minutes for azure to do its magic (grab some tea from Punjab Kebab!)

SSH into the virtual machine

  1. Open up terminal
  2. type in:
     ssh azureuser@[DNS-Name].cloudapp.net 

    and enter your password

You are now inside your virtual machine!

Now we need to install PostGreSQL on your virtual machine

Type in a few commands:

sudo apt-get install postgresql
sudo apt-get install postgresql-9.1-postgis
sudo apt-get install postgresql-contrib

To get  into your database type

 sudo -u postgres psql postgres 

And that’s it, now you can write psql commands to create tables for your database!

N-Queens Implementation in Javascript

Week 2, Day 4 of Hack Reactor:

Having already passed the data structures sprint where we implemented 4 different instantiation patterns in JavaScript. Our next two-day sprint focused on algorithms and working on an implementation of the classic N-Queens problem.

The problem is simple: How many ways are there to arrange n queens on an n by n chessboard such that no queens are in a direct line of attack.

Our first implementation was very, very slow, taking ~15 minutes for N=8.

How we stored the chessboard: 2D-array


[ [0,1,0],

  [1,0,0],

  [0,0,1] ]

Having (barely) passed the core requirements, we then set our eyes on the extra-credit section. There was a lot of room for improvement in the time complexity. Since the nature of the problem requires a brute-force technique along with a collision detect on every queen being placed. I discovered that the large majority of our code’s time was being spent checking for collisions. Since our algorithm spent most of its time checking collisions, that was the first place to improve. At a glance, our implementation of collision detection had a time complexity of O(n^2) on each row for a total time complexity of O(n^3)…(after n^2, it pretty much goes downhill from there).

My initial thought for improving efficiency was a different way of representing the chessboard that was more efficient than the 2D-array we were currently using.

From a 2D-array to a 1D-array:


[1, 0, 2]

Since we know that every solution will have a queen in every row, we don’t care about the spaces where there aren’t queens. We only care about the locations of each queen in the row. With this implementation, each index of the array represents the row, and the value represents the location of the queen in that row.

For example, row 0 has a queen in position 1, row 1 has a queen in position 0, and row 2 has a queen in position 2. By using this representation, the time complexity for checking collisions is O(N) since we are only traversing one array.

But  how we can do better? I’ll give you a hint: hash tables.

From a 2D-array to an object:


{0: 1, 1: 0, 2: 2}

Using the same logic as rows, the keys represent the rows and the values represent the location of the queen in that row. However, since objects are implemented as hash tables in javascript, we can take advantage of the constant time lookup, O(1).

We had less than a day at this point to refactor our original N-Queens implementation. We felt the other two implementations, although more efficient, would not give us much of a challenge. We instead went with a bitwise implementation because who doesn’t love a good bitwise from time to time.

Following this very old code, here is our bitwise javascript implementation of N-Queens:


var countNQueens = function(n){
  var all = Math.pow(2,n) - 1;
  var solutionCount = 0;

  var findSolutions = function(cols,ld,rd){

    var pos = ~(cols | ld | rd) & all;

    while(pos>0){
      var bit = -pos & pos;
      pos = pos ^ bit;

      findSolutions((cols | bit), (ld | bit) << 1, (rd | bit) >> 1);

    }
    if (cols === all) {
      solutionCount++;
    }
  };
  findSolutions(0, 0, 0);
  console.log(solutionCount);
  return solutionCount;
};