Tag Archives: math

The Depth-First-Search Algorithm

I remember when I was younger I used to play the game of hide-and-seek a lot. This is a game where a group of people (at least two) separate into a group of hiders and a group of seekers. The most common version of this that I’ve seen is having one person as the seeker and everyone as hiders. Initially, the seeker(s) is given a number to count towards and close their eyes while counting. The hiders then search for places to hide from the seeker. Once the seeker is finished counting, their job is to find where everyone is hiding or admitting that they cannot find all the seekers. Any seekers not found are said to have won, and seekers that are found are said to have lost.

I played this game a number of times in my childhood, but I remember playing it with a friend named Dennis in particular. Dennis had a certain way he played as seeker. While many of us would simply go to places we deemed as “likely” hiding spots in a somewhat random order, Dennis would always begin by looking in one area of the room, making sure that he had searched through every area connected to that area before going to a new area. He continued this process until he either found everybody or concluded that he had searched every spot he could think of and gave up.

It wasn’t until years later that I was able to note the similarity between Dennis’s way of playing hide-and-seek and the Depth-First-Search algorithm. The Depth-First-Search Algorithm is a way of exploring all the nodes in a graph. Similar to hide-and-seek, one could choose to do this in a number of different ways. Depth-First-Search does this by beginning at some node, looking first at one of the neighbors of that node, then looking at one of the neighbors of this new node. If the new node does not have any new neighbors, then the algorithm goes to the previous node, looks at the next neighbor of this node and continues from there. Initially all nodes are “unmarked” and the algorithm proceeds by marking nodes as being in one of three states: visited nodes are marked as “visited”; nodes that we’ve marked to visit, but have not visited yet are marked “to-visit”; and unmarked nodes that have not been marked or visited are “unvisited”.

Consider a bedroom with the following possible hiding locations: (1) Under Bed, (2) Behind Cabinet, (3) In Closet, (4) Under Clothes, (5) Behind Curtains, (6) Behind Bookshelf, and (7) Under Desk. We can visualize how the bedroom is arranged as a graph and then use a Breadth First Search algorithm to show how Brent would search the room. Consider the following bedroom arrangement, where we have replaced the names of each item by the number corresponding to that item. Node (0) corresponds to the door, which is where Dennis stands and counts while others hide.

Bedroom Items as a Graph

Now consider how a Breadth First Search would be run on this graph.

Bedroom Items as a Graph Colored by DFS

The colors correspond to the order in which nodes are visited in Depth-First-Search.

The way we read this is that initially Dennis would start at node 0, which is colored in Blue.
While Dennis is at node 0, she notices that nodes 1, 5, and 6 (under bed, behind curtains, and behind bookshelf) are the nearby and have not been checked yet so she places them on the “to visit” list.
Next, Dennis will begin to visit each node on the “to visit” list, and when a node is visited, she labels it as visited. At each location, she also takes note of the other locations she can reach from this location. Below is the order of nodes Dennis visits and how he discovers new locations to visit.

Order Visited Node Queue Adding Distance From Node 0
1 0 6,5,1 0
2 6 5,1 7,3,2 1
3 7 3,2,5,1 2
4 3 2,5,1 2
5 2 5,1 4 2
6 4 5,1 3
7 5 1 1
8 1 1

Here is a link to my Examples page that implements the Depth-First-Search Algorithm on Arbitrary Graphs.

The Breadth-First-Search Algorithm

I remember when I was younger I used to play the game of hide-and-seek a lot. This is a game where a group of people (at least two) separate into a group of hiders and a group of seekers. The most common version of this that I’ve seen is having one person as the seeker and everyone as hiders. Initially, the seeker(s) is given a number to count towards and close their eyes while counting. The hiders then search for places to hide from the seeker. Once the seeker is finished counting, their job is to find where everyone is hiding or admitting that they cannot find all the seekers. Any seekers not found are said to have won, and seekers that are found are said to have lost.

I played this game a number of times in my childhood, but I remember playing it with a friend named Brenda in particular. Brenda had a certain way she played as seeker. While many of us would simply go to places we deemed as “likely” hiding spots in a somewhat random order, Brenda would always take a survey of the room, and no matter where she began searching, she would always make note of the locations close to her starting point and make sure she was able to give them all a look before she looked at locations that were close to the points she deemed close to the starting point. She continued this process until she either found everybody or concluded that she had searched every spot she could think of and gave up.

It wasn’t until years later that I was able to note the similarity between Brenda’s way of playing hide-and-seek and the Breadth-First-Search algorithm. The Breadth-First-Search algorithm is a way of exploring all the nodes in a graph. Similarly to hide-and-seek, one could choose to do this in a number of different ways. Breadth-First-Search does this by beginning at some node, looking first at each of the neighbors of the starting node, then looking at each of the neighbors of the neighbors of the starting node, continuing this process until there are no remaining nodes to visit. Initially all nodes are “unmarked” and the algorithm proceeds by marking nodes as being in one of three stages: visited nodes are marked as “visited”; nodes that we’ve marked to visit, but have not visited yet are marked “to-visit”; and unmakred nodes that have not been marked are “unvisited”.

Consider a bedroom with the following possible hiding locations: (1) Under Bed, (2) Behind Cabinet, (3) In Closet, (4) Under Clothes, (5) Behind Curtains, (6) Behind Bookshelf, and (7) Under Desk. We can visualize how the bedroom is arranged as a graph and then use a Breadth First Search algorithm to show how Brenda would search the room. Consider the following bedroom arrangement, where we have replaced the names of each item by the number corresponding to that item. Node (0) corresponds to the door, which is where Brenda stands and counts while others hide.

Bedroom Items as a Graph

Now consider how a Breadth First Search would be run on this graph.

Bedroom Items as a Graph

The colors correspond to the order in which nodes are visited in Breadth-First-Search.

The way we read this is that initially Brenda would start at node 0, which is colored in Blue.
While Brenda is at node 0, she notices that nodes 1, 5, and 6 (under bed, behind curtains, and behind bookshelf) are the nearby and have not been checked yet so she places them on the “to visit” list.
Next, Brenda will begin to visit each node on the “to visit” list, and when a node is visited, she labels it as visited. At each location, she also takes note of the other locations she can reach from this location. Below is the order of nodes Brenda visits and how she discovers new locations to visit.

Order Visited Node Queue Adding Distance From Node 0
1 0 1, 5, 6 0
2 1 5, 6 2, 4 1
3 5 6, 2, 4 1
4 6 2, 4 3, 7 1
5 2 4, 3, 7 2
6 4 3, 7 2
7 3 7 2
8 7 2

Here is a link to my Examples page that implements the Breadth-First-Search Algorithm on Arbitrary Graphs.

ID3 Algorithm Decision Trees

ID3 Algorithm Page Image

As I grow LEARNINGlover.com, I’m always thinking of different ways to expose my own personality through the site. This is partially because it is easier for me to talk about subjects where I am already knowledgeable, but it is more-so being done to help make some of these algorithms and concepts I encode more understandable, and sometimes relating foreign concepts to everyday life makes them easier to understand.

Today, I’d like to write about decision trees, and the ID3 algorithm for generating decision trees in particular. This is a machine learning algorithm that builds a model from a training data set consisting of a feature vector and an outcome. Because our data set consists of an outcome element, this falls into the category of supervised machine learning.

The model that the ID3 algorithm builds is called a decision tree. It builds a tree based on the features, or columns of the data set with a possible decision corresponding to each value that the feature can have. The algorithm selects the next feature by asking “which feature tells me the most about our data set?” This question can be answered first by asking how much “information” is in the data set, and then comparing that result with the amount of information in each individual feature.

In order to execute this algorithm we need a way to measure both the amount the information in outcomes of the overall data set as well as how much each feature tells us about the data set. For the first, we will use entropy, which comes from the field of information theory and encoding. Entropy is based on the question of how many bits are necessary to encode the information in a set. The more information, the higher the entropy, and the more bits required to encode that information. Although we are not encoding, the correlation between high information and high entropy suits our purposes.

Entropy Formula

To understand how much each feature tells us about the outcomes of the data set we will build on the concept of entropy to define the information gain of a feature. Each feature has multiple options, so the dataset can be partitioned based on each possible value of this feature. Once we have this partition, we can calculate the entropy of each subset of the rows of data. We define the information gain of a feature as the sum over all possible outcomes of that feature can have of the entropy of that outcome multiplied by the probability of that outcome.

Information Gain Formula

To illustrate this algorithm, I decided to relate it to the question of whether we think of a character in a novel as a hero or villain. This is interesting because I try to read at least one book a month and as I’m reading, I often find myself asking this question about characters based on the traits of the characters as well as characters I’ve read about. In order to build an interactive script for this problem, I considered 25 possible character traits that could be present. A subset of these 25 character traits will be selected and a row will be generated grading a fictional character on a scale of 0 to 3 (0 meaning that they do not possess the trait at all, 3 meaning that the trait is very strong in their personality), and users will be asked whether they think a character with the given character traits should be listed as a hero or a villain. Then there is a button at the bottom of the script with the text “Build Tree” that executes the ID3 Algorithm and shows a decision tree that could be used to reach the set of decisions given by the user.

The possible features are:
Abstract, Adaptable, Aggressive, Ambition, Anxiety, Artistic, Cautious, Decisive, Honesty, Dutiful, Fitness, Intellect, Independent, Introverted, Lively, Open-minded, Orderly, Paranoid, Perfectionist, Romantic, Sensitive, Stable, Tension, Warmth and Wealthy

Once users select the option to build the tree, there will be several links outlining each step in the process to build this tree. These links will allow for users to expand the information relating to that step and minimize that information when done. Hopefully this will help users to understand each step more. I must say that as much fun as it has been writing this program, there were several questions when trying to explain it to others. Hopefully users get as much fun from using this tool as I had in creating it. As always feel free to contact me with any comments and or questions.

Ok, so here’s a link to the ID3 Algorithm Page. Please check it out and let me know what you think.

Clique Problem Puzzles

I still remember how I felt when I was first introduced to NP-Complete problems. Unlike the material I had learned up to that point, there seemed to be such mystery and intrigue and opportunity surrounding these problems. To use the example from Garey and Johnson’s book “Computers and Intractability: A Guide to the Theory of NP Completeness”, these were problems that not just one researcher found difficult, but that a number of researchers had been unable to find efficient algorithms to solve them. So what they did was show that the problems all had a special relationship with one another, and thus through this relationship if someone were to discover an algorithm to efficiently solve any one of these problems they would be able to efficiently solve all the problems in this class. This immediately got my mind working into a world where I, as a college student, would discover such an algorithm and be mentioned with the heavyweights of computer science like Lovelace, Babbage, Church, Turing, Cook, Karp and Dean.

Unfortunately I was a student so I did not have as much time to devote to this task as I would have liked. In my spare time though I would try to look at problems and see what kind of structure I found. One of my favorite problems was, The Clique Problem. This is a problem where we are given an undirected graph and seek to find a maximum subset of nodes in this graph that all have edges between them, i.e. a clique (Actually the NP-Complete version of this problem takes as input an undirected graph G and an integer k and asks if there is a clique in G of size k).

Although I now am more of the mindset that there do not exist efficient algorithms to solve NP-Complete problems, I thought it would be a nice project to see if I could re-create this feeling – both in myself and others. So I decided to write a program that generates a random undirected graph and asks users to try to find a maximum clique. To test users answers, I coded up an algorithm that works pretty well on smaller graphs, the Bron-Kerbosch Algorithm. This algorithm uses backtracking to find all maximal cliques, which then allows us to sort them by size and determine the largest.

Users should click on the numbers in the table below the canvas indicating the nodes they wish to select in their clique (purple indicates that the node is selected, gray indicates that it is not). Once they have a potential solution, they can press the “Check” button to see if their solution is optimal. If a user is having trouble and simply wishes to see the maximum clique, they can press the “Solve” button. And to generate a new problem, users can press the “New Problem” button.

So I hope users have fun with the clique problem puzzles, and who knows maybe someone will discover an algorithm that efficiently solves this problem and become world famous.

Unidirectional TSP Puzzles

As we’ve entered the late spring into early summer season, I’ve found myself wanting to go out more to sit and enjoy the weather. One of these days recently I sat in the park with a good book. On this occurrence, I decided not to go with a novel as I had just finished “Incarceron“, “The Archer’s Tale“, and “14 Stones” – all of which were good reads, but I felt like taking a break from the novels.

Just as a side note, 14 Stones is a free book available on smashwords.com and I’ve now read about 6 books from smashwords.com and haven’t been disappointed yet. My favorite is still probably “The Hero’s Chamber” because of the imagery of the book, but there are some well written ebooks available there by some good up and coming writers for a reasonable price, with some being free.

 

So with the desire to read, but not being in the mood for novels I decided to pick up one of my non-text but still educational books that make me think. This day it was “Programming Challenges“. I browsed through the book until I found one that I could lay back, look at the water, and think about how to solve it.

 

The programming puzzle the peaked my interest was called “Unidirectional TSP”. We are given a grid with m rows and n columns, with each cell showing the cost of using that cell. The user is allowed to begin in any cell in the first column and is asked to reach any cell in the last column using some minimum cost path. There is an additional constraint that once a cell is selected in a column, a cell in the next column can only be chosen from the row directly above, the same row, or the row directly below. There is a javascript version of this puzzle available here.

Fundamentally, the problem is asking for a path of shortest length. Many shortest length problems have a greedy structure, but this one gained my interest because the greedy solution is not always optimal in this case. So I took a moment to figure out the strategy behind these problems. Once I had that solution, I decided that it would be a good program to write up as a puzzle.

 

In this puzzle version, users will click the cells they wish to travel in each column in which case they will turn green (clicking again will turn them white again). Once the user clicks on a cell in the last column, they will be notified of whether or not they have chosen the minimum path. Or if users are unable to solve a puzzle, the “Solution” button can be pressed to show the optimal path and its cost. 

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.

Triangle Sum Puzzle

This is probably a consequence of being a mathematician, but I have always enjoyed number puzzles. I think that there is a general simplicity and universality in numbers that are not present in things like word puzzles, where the ability to reach a solution can be limited to the vocabulary of the user.

The fact that these are puzzles and not simply homework exercises also helps because we often find people sharing difficulties and successes stories over the water cooler or at the lunch table. The fact that many of these math puzzles can teach some of the same concepts as homework problems (in a more fun and inclusive way) is generally lost on the user as their primary interest is generally on solving the puzzle in front of them, or sometimes solving the more general form of the puzzle.

Today’s post is about a puzzle that was originally shared with me over a lunch table by a friend who thought it was an interesting problem and asked what I thought about it. I didn’t give the puzzle much further thought (he had correctly solved the puzzle) until I saw it again in “Algorithmic Puzzles” by Anany Levitin and Maria Levitin. It was then that I thought about the more general form of the puzzle, derived a solution for the problem, and decided to code it up as a script for my site.

Below is a link to the puzzle:

We have a set of random numbers arranged in a triangle and the question is to find the path of maximum sum from the root node (the top node) to the base (one of the nodes on the bottom row) with the rules that
(1) Exactly one number must be selected from each row
(2) A number can only be selected from a row if (a) it is the root node or (b) one of the two nodes above it has been selected.

For the sample
So for the sample problem in the picture, the maximal path would go through nodes 57, 99, 34, 95, and 27.

For more of these puzzles check out the script I write here and be sure to let me know what you think.

The Bridge Crossing Problem

Most puzzles are fun in their own right. Some puzzles are so fun that they have the added benefit that they are likely to come up in unexpected places, like maybe in a job interview. I was recently reading a paper by Günter Rote entitled “Crossing the Bridge at Night” where Rote analyzes such a puzzle. Upon finishing the paper, I decided to write a script so that users could see the general form of this puzzle.

The problem can be stated as follows: There is a set of people, lets make the set finite by saying that there are exactly n people, who wish to cross a bridge at night. There are a few restrictions that make crossing this bridge somewhat complicated.

  • Each person has a travel time across the bridge.
  • No more than two people can cross the bridge at one time.
  • If two people are on the bridge together, they must travel at the pace of the slower person.
  • There is only one flashlight and no party (of one or two people) can travel across the bridge without the flashlight.
  • The flashlight cannot be thrown across the bridge, and nobody can go to the store to purchase another flashlight

The image above shows the optimal solution when the 4 people have travel times of 1, 2, 5, and 10. The script I have written allows users to work with different numbers of people with random travel times. Give it a try and see if you can spot the patterns in the solution.

Magical Squares Game

Whether introduced as children in elementary school, as adults in the workplace, or somewhere in between, the concept of magic squares has fascinated people for centuries; The Wikipedia article has discoveries of magic squares dating back to 650 B.C. in China.

Magic Squares of size n (for n >= 3) are n by n grids where the numbers 1, 2, …, n2 are specially arranged such that the sum of each row, column, and diagonal all sum to the same number. Below are two examples of magic squares of size 3 and 4.

8 3 4
1 5 9
6 2 7
4 1 16 13
15 11 2 6
10 14 7 3
5 8 9 12

Notice first, that in the first square all the numbers 1, 2, 3, .., 9 are used in the square. Likewise, the numbers 1, 2, …, 15, 16 are used in the second square. Second notice that each row, column and diagonal sums to 15 in the first square and 34 in the second square.

I have recently published a puzzle that is based on the concept of magic squares. There are some slight differences though.
– First, instead of using the numbers 1, 2, …, n2 a random set of numbers are generated.
– Second, the rows and columns each have a desired sum that we would like the numbers in the row/column to sum to.

These two changes allow for a puzzle concept to be formulated based on the magic square concept. Users take turns swapping elements until the numbers in each row and column sum to the number in their goal cell, which is located in the last column or row of the grid. Above is an image of a solved puzzle.

Users can determine their progress the numbers in the next-to-last column, which tells the current sum of the numbers in that respective row or column.

To swap two numbers, first click on a cell with one of the two numbers in it. The cell should then turn red. Then click on the cell with the other number in it and the numbers should swap. If you click on the same cell twice no action should take place (except for the cell to turn red and then blank again).

Take a moment to check out the puzzles and let me know what you think.

QR Decomposition

Suppose we have a problem that can be modeled by the system of equations Ax = b with a matrix A and a vector b. We have already shown how to use Gaussian Elimination to solve these methods, but I would like to introduce you to another method – QR decomposition. In addition to solving the general system of equations, this method can also be used in a number of other algorithms including the linear regression analysis to solve the least squares problem and to find the eigenvalues of a matrix.

Generally, when we see a system of equations, the best way to proceed in solving it is Gaussian elimination, or LU decomposition. However, there are some very special matrices where this method can lead to rounding errors. In such cases, we need a better, or more stable algorithm, which is when the QR decomposition method becomes important.

Any matrix A, of dimensions m by n with m >= n, can be represented as the product of two matrices, an m by m orthogonal matrix Q, i.e. QTQ = I, and an m by n upper triangular matrix R with the form [R 0]T. We perform this decomposition by will first converting the columns of the matrix A into vectors. Then, for each vector ak, we will calculate the vectors uk and ek given by

uk = i = 1 to k-1projej ak
and
ek = uk / ||uk||
Then Q = [e1, …, en] and

R =
<e1, a1> <e1, a2> <e1, a3>
0 <e2, a2> <e2, a3>
0 0 <e3, a3>

Here is a link to the JavaScript program I wrote to show how QR Decomposition works.