Category Archives: Blog

These are my thoughts on various topics.

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. 

Range Puzzles

Range Puzzles

I have always liked puzzles. I really enjoy discovering a new puzzle. Sometimes when I have discovered a new puzzle, I enjoy it so much that I can’t seem to do enough of them. In such cases, I quickly run out of these puzzles to do and find myself looking for either a new puzzle or a way to generate them on my own.

Such was the case when I discovered the “Range Puzzles”. The rules are simple:

Every cell is marked either blue or gray
No two gray cells can be next to one another
The grid must be a connected (i.e. there is always a path from every cell to every other cell using horizontal and vertical connections.
Some cells have a number inside. This indicates the number of cells that can be viewed (horizontally and vertically in both directions) by this cell, including the cell itself.

To try out these puzzles, visit Range Puzzles at LEARNINGlover.com

How To Take Notes in Math Class

I was recently asked by someone how they should be taking notes in math class. I could immediately relate because I once asked this very same question. In both undergrad and grad, I had to ask myself how to take notes because I often would leave class with a bunch of sentence fragments based on what the professor said, but without anything I could use as a study guide. At best, it would be a garbled thing that I could combine with somebody else’s notes and try to make some legible out of it. Generally though, I would just ignore my notes and go to the text book if it was well written, or the library if the text book was not well written.

So how did I get past this? Well, after taking the Set Theory course, I started seeing mathematics as more of a construction job, like building a house. Mathematics is based on proofs which is nothing more than logical reasoning, and logical reasoning is just a series of statements that are either assumptions, definitions, or conclusions drawn from those assumptions based on known facts. The main purpose of classes is to present these “known facts” to the students and help them become more informed mathematicians. So what is a mathematical fact?

There are two important types of facts we generally learn in mathematics. The first gives us a language we can work from – these are our definitions. These are the most important things in a mathematics class because if it is a class on “group theory”, then one of the first definitions will be of a “group,” and not knowing this definition will cause problems when you are trying to prove that something is or is not a group. Similarly, if your class is on solving quadratic equations, then it is very important to be able to define what a “quadratic equation” is. Definitions in mathematics are important because, unlike in an English class, you cannot always derive the meaning of a mathematical term from its usage. Mathematical definitions are very precise and your notes should include this precision.

As a side note, I will state (if not stress) that examples are not definitions. Examples are meant to bring the definition to life, and to help connect the definition to the student, but if you are asked what is a group and respond that “the set of integers mod 7 under the operation of addition is a group”, you’d be incorrect because you gave an example of a group without telling why this is a group. Similarly, if I were to ask you to define a quadratic equation and you said “x^2 + 2x + 1 = 0 is a quadratic equation”, you’d be giving me an example but not a definition. It is important to understand the distinction between examples and definitions because when we understand the definition we can clearly explain why (ala prove) that the given instance is in fact an example.

Some professors will briefly mention a definition and then focus most of their time on examples in an attempt to make the concepts easier to understand. As a student though, it is important to ask the question “what is the definition of _____” because the exams, or the research that follows, or the applications of this concept in real life are not likely to be that same example. If the professor does not write out the definition of whatever concept you are studying, or you are unclear of this definition you should ask questions, go to an online resource, or a text book for supplementary reference.

The second type of fact presented in mathematical classes is the theorem (aka lemma or corollary). A theorem is a statement that is provable by mathematical reasoning. In a classroom setting, theorems will generally be presented in an orderly fashion such that if Theorem 1 is presented before Theorem 2, then Theorem 1 does not require Theorem 2 in order to be proven.

Because theorems are provable statements, it may be tempting to jump directly into the proof, and particularly to only take notes on the proof. I cannot stress against this enough. Before writing the proof, you should make sure to begin the proof with a clear statement of the theorem. This should be a declarative statement that is thus provable. Do not confuse the questions a professor may ask before proving a theorem with the theorem itself. An example of a theorem from group theory is “Any group that has a prime number of elements of elements in that group is cyclic (or can be generated by a single element). Also, do not confuse the nicknames of theorems with the theorem itself. For instance Lagrange’s Theorem says that “the number of elements of any subgroup of a finite group divides the number of elements in the original group.” Remembering this as Lagrange’s Theorem is fine, but it is much more important to remember the declarative statement proved.

I’m sure there are other things people use to take notes in math classes. Feel free to leave a comment sharing some of this advice.

Learn About Descriptive Statistics

I had been meaning to write a script and blog post on descriptive statistics for some time now, but with work and winter weather and the extra work that winter weather brings, and now that the winter weather is over trying to get back into an exercise routine (running up a hill is such a challenging experience, but when I get to the top of that hill I feel like Rocky Balboa on the steps at the steps at the entrance of the Philadelphia Museum of Art), I haven’t had the time to devote to this site that I would have liked. Well, that’s not entirely true. I have still been programming in my spare time. I just haven’t been able to share it here. I went to a conference in February and in my down time, I was able to write a script on descriptive statistics that I think gives a nice introduction to the area.

Before I go into descriptive statistics though, lets talk about statistics, which is concerned with the collection, analysis, interpretation and presentation of data. Statistics can generally be broken down into two categories, descriptive statistics and infernalinferential statistics, depending on what we would like to do with that data. When we are concerned with visualizing and summarizing the given data, descriptive statistics gives methods to operate on this data set. On the other hand, if we wish to draw conclusions about a larger population from our sample, then we would use methods from inferential statistics.

In the script on descriptive statistics I’ve written, I consider three different types of summaries for descriptive statistics:

Measures of Central Tendency
Mean – the arithmetic average of a set of values
Median – the middle number in a set of values
Mode – the most used number in a set of values

Dispersion
Maximum – the largest value in the data set
Minimum – the smallest value in the data set
Standard Deviation – the amount of variation in a set of data values
Variance – how far a set of numbers is spread out

Shape
Kurtosis – how peaked or flat a data set is
Skewness – how symmetric a data set is

Plots
Histogram Plots – a bar diagram where the horizontal axis shows different categories of values, and the height of each bar is related to the number of observations in the corresponding category.
Box and Whisker Plots – A box-and-whisker plot for a list of numbers consists of a rectangle whose left edge is at the first quartile of the data and whose right edge is at the third quartile, with a left whisker sticking out to the smallest value, and a right whisker sticking out to the largest value.
Stem and Leaf Plots – A stem and leaf plot illustrates the distribution of a group of numbers by arranging the numbers in categories based on the first digit.

Slope Formula

I was watching a football game a few days ago, and to prepare for it, we decided to pick up some snacks. As the game progressed, I found myself eating a lot of chips, but at halftime, there was one snack that remained unopened, a snack I had been thinking about all night, a snack that I couldn’t seem to locate until that moment – Recee’s Pieces. We purchased a pretty large sized bag that I thought would last a while. So at the end of halftime, when the bag was almost empty, someone made sure to warn me that at the rate I’m eating these things I’d be sure to be sick the next day.

Just to give you some insight into my how my mind works, the fact that she used the term “rate” took me back to classes of Algebra 1 where we were first learning about linear equations, slopes, y-intercepts, point slope form, slope intercept form, and so on. The more I thought about it, the more I thought this would be a good script to add to this site as it would probably provide help to many students who are currently enrolled in those classes as well as a remembrance to adults who took those classes years ago and wish to recall the concepts.

So I have added a script which helps go over the slope formula. It randomly generates two points and asks users to select which of a set of choices is the slope of those two numbers. In case you forget, there is a button where you can be given the slope as well.