Tag Archives: learninglover

Binary Puzzles

As you can probably tell, I’m a big fan of puzzles. On one hand you can say that a good puzzle is nothing but particular instance of a complex problem that we’re being asked to solve. What exactly makes a problem complex though?

To a large extent that depends on the person playing the puzzles. Different puzzles are based on different concepts and meant to highlight different concepts. Some puzzles really focus on dynamic programming like the Triangle Sum Puzzles or the Unidirectional TSP Puzzles.

Other puzzles are based on more complicated problems, in many cases instances of NP-complete problems. Unlike the puzzles mentioned above, there is generally no known optimal strategy for solving these puzzles quickly. Some basic examples of these are ones like Independent Set Puzzles, which just give a random (small) instance of the problem and ask users to solve it. Most approaches involve simply using logical deduction to reduce the number of possible choices until a “guess” must be made and then implementing some form of backtracking solution (which is not guessing since you can form a logical conclusion that if the guess you made were true, you reach either (a) a violation of the rules or (b) a completed puzzle).

One day a few months back i was driving home from work and traffic was so bad that i decided to stop at the store. While browsing the books, I noticed a puzzle collection. Among the puzzles I found in that book were the Range Puzzles I posted about earlier. However I also found binary puzzles.

Filled Binary puzzles are based on three simple rules
1. No the adjacent cells in any row or column can contain the same value (so no 000 or 111 in any row or column).
2. Every row must have the same number of zeros and ones.
3. Each row and column must be unique.

There is a paper from 2013 stating that Binary Puzzles are NP Complete. There is another paper that discusses strategies involved in Solving a Binary Puzzle

Once I finished the puzzles in that book the question quickly became (as it always does) where can I get more. I began writing a generator for these puzzles and finished it earlier this year. Now i want to share it with you. You can visit the examples section to play those games at Binary Puzzles.

Below I will go over a sample puzzle and how I go about solving it. First lets look at a 6 by 6 puzzle with some hints given:

 01   
0 10  
11 0  
 1  0 
   0  
1  1 0

We look at this table and can first look for locations where we have a “forced move”. An obvious choice for these moves wold be three adjacent cells in the same row or column where two have the same value. A second choice is that when we see that a row or column has the correct number of zeros or ones, the remaining cells in that row or column must have the opposite value.

So in the above puzzle, we can see that the value in cells (2, 2) and (2, 5) must also be a 0 because cells (2, 3) and (2, 4) are both 1. Now we see that column 2 has 5 of its 6 necessary values, and three 0’s. So the last value in this column (2, 6) must be a 1 in order for there to be an equal number of 0s and 1s.

For some easier puzzles these first two move types will get you far enough to completely fill in all the cells. For more advanced puzzles though, this may require a little more thorough analysis. 

As always, check it out and let me know what you think. 

The PageRank Algorithm

I think one of the best recent examples of the importance of mathematics is the rise of the search engine Google. I remember the world of search engines before Google and it was dominated by names like AltaVista, Yahoo, WebCrawler, Excite, and the likes. The standard way these search engines ranked the order that pages would be listed on a search query was basically to count the number of times that query appeared on pages in their database. The pages with the most listings were considered the most important, the second most listings were second most important and so on and so forth.

This sounds like a feasible way of doing things but let me show you an example of how this can be tricked. Suppose I wrote my first web page and it looked like the following:

That’s a basic web page that may not garner much attention, and it wouldn’t rank highly in most search engines as no work appears more than once. Suppose that, this being a math web page, I wanted it to rank higher on the query “math”. Then I could just edit the source code of the page to be as follows:

This second page says not much more than the first, but the fact that the word math appears 9 additional times would increase the ranking of this page among math pages. This is a very simple example, but it shows how these search engine rankings did not have a useful metric for determining the important sites on the web.

Enter Google.

The way Google solved this problem of determining the importance of a web page is basically by counting the number of links into a web page – the theory being that the more important a web page is, the more people will be talking about it and thus linking to it. Also, the more important the people talking about (linking to) a web site, the more important that site is. This can be expressed mathematically by the following formula:

In the above formula, the variable d is called the damping factor, which helps to capture some of the random nature of the internet by saying that every site should have at least some minimal worth because of the idea that a random surfer could still get to these sites.

I have written a script to implement the algorithm here.

Other Blogs that have covered this topic
Blue Onion

Learn Duality in Linear Programming

I have just completed a script to help learn about duality in linear programming.

Many real world problems can be formulated as Linear Programming problems. There are often many different ways to formulate a single problem. Some of these alternative formulations can easily be proven to be equal via simple algebra and arithmetic. For example, one person may see a problem as maximizing profit while another may see the same problem as minimizing losses. The relationship between the two alternative formulations can then be shown to be that one simply has the negative objective function value of the other.

Sometimes, though, this relationship between alternative formulations is not as easy to detect. Two alternative formulations that arise regularly in linear programming problems are a primal problem and a dual problem. The dual of a linear programming problem is the problem of finding the best bound on the objective function in terms of the constraints. This dual is formulated so that every feasible solution to the dual is a bound on the primal objective function. The Weak Duality Theorem for Linear Programming says that the optimal solution for a minimization problem is always an upper bound for its dual (which is a corresponding maximization problem). Correspondingly, the optimal solution for a maximization problem is always a lower bound for its dual. This leads to the Strong Duality Theorem for Linear Programming which says that if we can find feasible solutions to the primal and dual problems with matching objective function values, then both of these solutions must be optimal for their respective problems.

This shows an importance of duality. What my script provides is a means of formulating the dual of a given problem to help understand the concept.

The rules for constructing a dual linear program are as follows:

Primal:Dual:
The ith constraint is [<=]Variable yi is [>=] 0
The ith constraint is [>=]Variable yi is is [<=] 0
The ith constraint is =Variable yi is unbounded
Variable xj is [>=] 0The jth constraint is [>=]
Variable xj is [<=] 0The jth constraint is [<=]
Variable xj is unboundedThe jth constraint is =

Other Blogs that have covered this topic:
A Narrow Margin
Optimization and data mining

How Could You Possibly Love/Hate Math?

Growing up, I never really liked math. I saw it as one of those necessary evils of school. People always told me that if I wanted to do well and get into college, I needed to do well in math. So I took the courses required of a high school student, but I remember feeling utter confusion from being in those classes. My key problem was my inquisitive nature. I really didn’t like being “told” that certain things were true in math (I felt this way in most classes). I hated just memorizing stuff, or memorizing it incorrectly, and getting poor grades because I couldn’t regurgitate information precise enough. If this stuff was in fact “true”, I wanted to understand why. It seemed like so much was told to us without any explanation, that its hard to expect anybody to just buy into it. But that’s what teachers expected. And I was sent to the principal’s office a number of times for what they called “disturbing class”, but I’d just call it asking questions.

At the same time, I was taking a debate class. This class was quite the opposite of my math classes, or really any other class I’d ever had. We were introduced to philosophers like Immanuel Kant, John Stuart Mill, Thomas Hobbes, John Rawls, etc. The list goes on and on. We discussed theories, and spoke of how these concepts could be used to support or reject various propositions. Although these philosophies were quite complex, what I loved was the inquiries we were allowed to make into understanding the various positions. Several classmates and I would sit and point out apparent paradoxes in the theories. We’d ask about them and sometimes find that others (more famous than us) had pointed out the same paradoxes and other things that seemed like paradoxes could be resolved with a deeper understanding of the philosophy.

Hate is a strong word, but I remember feeling that mathematicians were inferior to computer programmers because “all math could be programmed”. This was based on the number of formulas I had learned through high school and I remember having a similar feeling through my early years of college. But things changed when I took a course called Set Theory. Last year, I wrote a piece that somewhat describes this change:

They Do Exist!

Let me tell you a story about when I was a kid
See, I was confused and here's what I did.
I said "irrational number, what’s that supposed to mean?
Infinite decimal, no pattern? Nah, can't be what it seems."
So I dismissed them and called the teacher wrong.
Said they can't exist, so let’s move along.
The sad thing is that nobody seemed to mind.
Or maybe they thought showing me was a waste of time.

Then one teacher said "I can prove they exist to you.
Let me tell you about my friend, the square root of two."
I figured it'd be the same ol' same ol', so I said,
"Trying to show me infinity is like making gold from lead"
So he replies, "Suppose you're right, what would that imply?"
And immediately I thought of calling all my teachers lies.
"What if it can be written in lowest terms, say p over q.
Then if we square both sides we get a fraction for two."

He did a little math and showed that p must be even.
Then he asked, "if q is even, will you start believing?"
I stood, amazed by what he was about to do.
But I responded, "but we don't know anything about q"
He says, "but we do know that p squared is a factor of 4.
And that is equal to 2 q squared, like we said before."
Then he divided by two and suddenly we knew something about q.
He had just shown that q must be even too.

Knowing now that the fraction couldn't be in lowest terms
a rational expression for this number cannot be confirmed.
So I shook his hand and called him a good man.
Because for once I yould finally understand
a concept that I had denied all my life,
a concept that had caused me such strife.
And as I walked away from the teacher's midst,
Excited, I called him an alchemist and exhaled "THEY DO EXIST!"

Aside from its lack of poetic content, I think that many mathematicians can relate to this poem, particularly the ones who go into the field for its theoretic principles. For many of us, Set Theory is somewhat of a “back to the basics” course where we learn what math is really about. The focus is no longer on how well you can memorize a formula. Instead, its more of a philosophy course on mathematics – like an introduction to the theory of mathematics, hence the name Set Theory.

The poem above focuses on a particular frustration of mine, irrational numbers. Early on, we’re asked to believe that these numbers exist, but we’re not given any answers as to why they should exist. The same could be said for a number of similar concepts though – basically, whenever a new concept is introduced, there is a reasonable question of how do we know this is true. This is not just a matter of practicality, but a necessity of mathematics. I mean I could say “lets now consider the set of all numbers for which X + 1 = X + 2”, but if this is true for any X, then it means that 1 equals 2, which we know is not true. So the set I’d be referring to is the empty set. We can still talk about it, but that’s the set I’d be talking about.

So why is this concept of answering the why’s of mathematics ignored, sometimes until a student’s college years? This gives students a false impression of what math really is, which leads to people making statements like “I hate math”, not really knowing what math is about.

Examples Page

Sometimes, the most effective way to understand a new concept is to actually see it in action. On My Examples Page, I have implemented a variety of scripts to help teach many different concepts.This is the page that is the easiest for me to update, so you will regularly see changes to this page along with an accompanying blog entry at My Blog Page.

This page is focused on teaching individual concepts and/or algorithms. In particular, with the HTML5 Canvas element, I’ve been able to visualize many of these concepts. Generally I try to provide a script that executes the given algorithm (or concept) and allows for users to view these concepts on random instances. When possible, I provide a button labeled “New Problem” (or something similar) which will allow the user to view a different instance of the algorithm.