The Turing Tapes

We can't all be graph theory geniuses like my friend Nathan Klein , but...we can learn how to make graphs in JavaScript. Source:  Wikipedia This is what mathematicians refer to as a graph.  In a graph, nodes (the circles above, numbered so we can distinguish them) are linked together by vertices (the lines).  Graphs can be used to store data and relationships, and they can also be used to simulate problems, such as in the  Traveling Salesman Problem , which asks you to find the most efficient route through a bunch of different cities. Quite often, we need to find the shortest path from one node to another (such as in the Traveling Salesman problem. It's a great problem).  What's the best way to do that? Djikstra's algorithm. Dijkstra’s algorithm  has a Big O complexity of log n, which is super efficient.  How does one do Djikstra's algorithm?  It's simple: you start at one node, and then move to the next node that has the shortest distance.  ...

One of the first thing a programmer learns is the various "types" that data can have.  Commonly-used types include things like strings, integers, and arrays.  Underneath the hood, all software data is, of course, composed of bits commonly represented by sequences of ones and zeros.  But typing gives structure to those bits, and not only allows programmers to understand and reason about the code they write (it makes more sense, for instance, to think of a string as letters or words rather than bits), but also prevents errors through creating restrictions on what certain types can and cannot do (for instance, you can add floating point numbers but you can't add arrays). There are two major axes along which typing varies: a language can be either strongly or weakly typed; and a language can be statically or dynamically typed.  You can loosely think of these, respectively, as a language's ability to prevent type errors, and when a language catches type errors. Static vs....

Welcome to the second in a series of posts about anti-patterns in Ruby ! What is a singleton?  A singleton is a single instance of a class, particularly  a single instance of a class - to be a singleton, a class must have the property of only being able to be created once (note that a singleton could not be created yet, so a singleton doesn't have the property of necessarily existing). Why use a Singleton pattern? * You have a single resource that you need to model - for instance, a log file. * You need quick access to a particular resource throughout your system and don't want to have to remake it every time. * Having more than one of a resource might be dangerous in your system - for example, if you're designing hardware related to a physical system, it may cause serious problems if you have multiple instances of an object floating around and different parts of the software are making calculations from different representations of a real-world machine part. * ...other rea...

Here's a lesson about the difference between theory and practical applications. Everyone knows about  bubble Sort  and  merge Sort  - they're probably the first two sorting algorithms you learned.  Everyone also knows that (1) bubble sort sucks and (2) this is due to the fact that its average time complexity is O(n^2), aka the worst time complexity.  It even generally performs worse than things like insertion sort and  selection sort , the "a D- is still a passing grade" of sorting algorithms. While all these things are true, there's a more important truth: always test your code. While reading  The Imposter's Handbook by Rob Conery  the other day and flipping through the comparison sort algorithms he provides, I decided, Why not actually test out this code?   And, the  speed test demon  that I am, my test involved sorting out his [23,4,42,15,16,8] array one million times with bubble sort and with merge sort, and I got this res...

When I was in middle school, I found a bunch of books at my local library that explained how to create games for the Atari console in  BASIC .  This was my first introduction to coding. BASIC is a great first language to learn to the extent that, as its name implies, it is an extremely basic programming language and is easy to understand (as you'll be able to tell after reading this post, it is not a good way to learn how to program in general, at least if your goal is to use modern programming languages). BASIC is also based off of  FORTRAN II , which is of course based off of FORTRAN, which is the language that invented the GOTO statement. The GOTO statement takes its inspiration from the most fundamental of computers, the Turing machine.  Turing machines are an abstraction in which a head reads and writes ones and zeros from an infinite tape of individual cells. The head moves back and forth along the tape based off of a finite list of instructions and what those ...

Everyone knows that computer programs are made of bits - the ones and zeros that hold all the information that keeps our modern life running. But how do you get from numbers to programs - how simple ones and zeros do  anything? The answer is logic gates (as well as a whole bunch of stuff about how electronics are built - you need to actually make these logic gates on out of circuits in order for our logic structures to be enacted; but I'm a programmer, not an electrical engineer, so let's not go there).  A logic gate is what's known as a  Boolean function , a mathematical operation that takes in bits and spits out more bits. Each logic gate takes in two bits of information (as mentioned before, generally denoted as a 1 (also sometimes represented as true ) or a zero (also sometimes represented as false )), so there are four possible inputs to a logic gate: {0, 0}, {0, 1}, {1, 0}, and {1, 1}.  For each of these inputs, a logic gate can spit out either a 1 or a 0, so t...