I just added a program that finds the strongly connected components of a graph using Tarjan’s Algorithm.
A strongly connected component of a graph is a subgraph S of G where every pair of nodes, u and v in S there is a path from u to v and a path from v to u.
To find these strongly connected components we implement Tarjan’s algorithm. The idea behind Tarjan’s algorithm is to begin by running a depth first search from an arbitrary node in the graph, labeling nodes reachable from this start node in the order they are reached. The algorithm is also interested in the “oldest” node that could be reached by a given node. This is indicated by the keeping track of the lowest label that can be reached from that node. We will call the first property label(v) and the second lowlink(v).
When the algorithm starts label(v) is the same as lowlink(v) whenever a node is discovered. As the algorithm is executed, the DFS is being run on each discovered node, which in turn updates the lowlink(v) property telling of (older) nodes that can be reached. If an older node can be reached, then we update lowlink. If we reach a node that cannot connect to any older nodes after the DFS call, i.e if label(v) is the same a lowlink(v), then this means that this node does not have a path to any node with a lower label. So this node will be the first node of a new strongly connected component.
Feel free to check it out an let me know what you think in the comments below.
]]>Note that we do not say that the elements of Z need to be a continuous block of elements. If this were true we would be defining a substring. So as an example, suppose we have as an initial string,
X = C, O, M, P, U, T, E, R.
Then the following are all subsequences:
Z1 = C, M, U, T, R
Z2 = C, O, M, P
Z3 = U, T, E, R
Z4 = O, P, T, E
I will note that Z2 and Z3 are also substrings since they contain continuous sets of characters.
The length of a substring is simply the number of characters it contains. So X has length 8, Z1 has length 5, Z2, Z3 and Z4 have length 4.
Suppose now that we had a second string, Y = P, R, O, G, R, A, M, M, E, R and are interested in the longest common subsequence between the two. We can do that by observing that there is a bit of recursion going on with this question. What I mean by that is that asking the question of “What is the longest common subsequence between X and Y” is the same as asking “What is the longest common subsequence between X and Y once we have seen 8 characters of X and 10 characters of Y”
There are three possible ways to answer this question.
If X<sub>8</sub> equals Y<sub>10</sub>, then we ask the same question about X<sub>7 and Y<sub>9</sub> and add 1 to the answer.
If X<sub>8</sub> is not equal to Y<sub>10</sub>, then the answer to this will be the same as the maximum of the pair X<sub>7</sub>, Y<sub>10</sub> and the pair X<sub>8</sub>, Y<sub>9</sub>.
If we reach a situation where we reach the beginning of either string, we are forced to answer 0 to that question.
Then the function has the following look:
LCS(X_{i}, Y_{j}) = 

Below is a table showing how we would solve the problem mentioned.
The strategy used to devise this concept is called dynamic programming. It is useful we can solve larger problems by solving overlapping subproblems, as was the case here. In this situation we generally can store the data in a table form and avoid resolving subproblems for which many larger problems will be dependent.
You can see this algorithm in action at LEARNINGlover.com: Longest Common Subsequece. Let me know what you think.
]]>Today, I would like to present a puzzle I created to play with the Independent Set problem. This is the problem where we are given a graph G = (V, E) and are asked to find a maximum set of vertices S such that there is no edge in the graph G between any two vertices in S. The decision version (the problem asking whether there is an independent set of size k) of this problem is NPComplete, so the known algorithms for problem either have a slow running time, or do not solve it exactly.
This problem is very related to another puzzle I posted last year called the clique problem. In fact, Karp originally proved that Clique was NPComplete by showing that if Clique could be solved efficiently, then Independent Set could be solved efficiently. He did this by constructing a second graph [G bar], called the compliment of G (containing the same vertices in G, along with the edges that are not present in G. Any edge present in G will not be present in ). Then he showed that the nodes representing a maximum clique in G would represent a maximum independent set in . He had already shown that Independent Set was NPComplete, which meant that both Independent Set and Clique were among the most difficult problems within the class known as NP.
The puzzle begins with an undirected graph and asks users to find a maximum independent set. Users should click on the numbers in the table below the graph indicating the nodes they wish to select in their independent set (purple indicates that the node is selected, gray indicates that it is not). Once a user 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 independent set, they can press the “Solve” button. And to generate a new problem, users can press the “New Problem” button.As a result of this relationship between the Clique problem and the Independent Set problem, the BronKerbosch algorithm that was used to find maximum cliques previously can also be used here.
]]>One of the more common things about this generation is the constant desire to write up (type) their thoughts. So many of the conversations from my high school days were long lasting, but quickly forgotten. Today’s generation is much more likely to blog, tweet, write status updates or simply open up a notepad file and write up their thoughts after such a conversation.
When we feel that our thoughts are not ready for public eyes (maybe you want to run your idea by the Patent and Trademark Office before speaking about it) we may seek some form of security to ensure that they stay private. An old fashioned way of doing this was to write in a diary and enclosed it within a lock and key. The mathematical field of encryption also tries to grant privacy by encoding messages so that only people with the necessary information can read them.
The type of encryption I want to speak about today is called XOR encryption. It is based on the logical operation called “exclusive or” (hence the name XOR). The exclusive or operation is true between two logical statements if exactly one of the two statements is true, but not both statement. This can be represented with the following truth table
Input 1  Input2  XOR Result 
T  T  F 
T  F  T 
F  T  T 
F  F  F 
XOR Encryption is particularly useful in this day and age because we every character we type is understood by the computer as a sequence of zeros and ones. The current standard encoding that is used is Unicode (also known as UTF8). Under this encoding the letter ‘a’ is represented as the binary string ‘01100001’. Similarly every letter, number and special character can be represented as its own binary string. These binary strings are just an assignment of numbers to these characters so that we can to help represent them in the computer. The numbers can the be thought of in base 10, which is how we generally think about numbers, or in base 2 which is how computers generally work with numbers (or a number of other ways). The way we would use these binary strings in encoding is first by translating a text from humanreadable text to machine readable text via its binary string. For example, the word “Invincible”, we would get the following binary strings:
Letter  Unicode in base 10  Unicode in base 2 
I  73  01001001 
n  110  01101110 
v  118  01110110 
i  105  01101001 
n  110  01101110 
c  99  01100011 
i  105  01101001 
b  98  01100010 
l  108  01101100 
e  101  01100101 
To encrypt the message we need a key to encode the message and will simply perform an XOR operation on the key and every character in the string. Similarly, do decrypt the message we perform XOR operation on the key and every character in the encoded message. This means that the key (much like a normal key to a diary) must be kept private and only those whom the message is to be shared between have access to it.
Here is a link to the script where you can check out XOR Encrpytio. Try it out and let me know what you think.
]]>Much of how we interact with life could be described as transitions between states. These states could be weather conditions (whether we are in a state of “sunny” or “rainy”), the places we may visit (maybe “school”, “the mall”, “the park” and “home”), our moods (“happy”, “angry”, “sad”). There are a number of other ways to model states and even the possibility of infinitely many states.
Markov Chains are based on the principle that the future is only dependent on the immediate past. so for example, if I wished to predict tomorrow’s weather using a Markov Chain, I would need to only look at the weather for today, and can ignore all previous data. I would then compare the state of weather for today with historically how weather has changed in between states to determine the most likely next state (i.e what the weather will be like tomorrow). This greatly simplifies the construction of models.
To use Markov Chains to predict the future, we first need to compute a transition matrix which shows the probability (or frequency) that we will travel from one state to another based on how often we have done so historically. This transition matrix can be calculated by looking at each element of the history as an instance of a discrete state, counting the number of times each transition occurs and dividing each result by the number of times the origin state occurs. I’ll next give an example and then I’ll focus on explaining the Finite Discrete State Markov Chain tool I built using javascript.
Next, I want to consider an example of using Markov Chains to predict the weather for tomorrow. Suppose that we have observed the weather for the last two weeks. We could then use that data to build a model to predict tomorrow’s weather. To do this, lets first consider some states of weather. Suppose that a day can be classified in one of four different ways: {Sunny, Cloudy, Windy, Rainy}. Further, suppose that over the last two weeks we have seen the following pattern.
Day 1  Sunny 
Day 2  Sunny 
Day 3  Cloudy 
Day 4  Rain 
Day 5  Sunny 
Day 6  Windy 
Day 7  Rain 
Day 8  Windy 
Day 9  Rain 
Day 10  Cloudy 
Day 11  Windy 
Day 12  Windy 
Day 13  Windy 
Day 14  Cloudy 
We can look at this data and calculate the probability that we will transition from each state to each other state, which we see below:
Rain  Cloudy  Windy  Sunny  
Rain  0  1/3  1/3  1/3 
Cloudy  1/2  0  1/2  0 
Windy  2/5  1/5  2/5  0 
Sunny  0  1/3  1/3  1/3 
Given that the weather for today is cloudy, we can look at the transition matrix and see that historically the days that followed a cloudy day have been Rainy and Windy days each with probability of 1/5. We can see this more mathematically by multiplying the current state vector (cloudy) [0, 1, 0, 0] by the above matrix, where we obtain the result [1/2, 0, 1/2, 0].
In similar fashion, we could use this transition matrix (lets call it T) to predict the weather a number of days in the future by looking at T^{n}. For example, if we wanted to predict the weather two days in the future, we could begin with the state vector [1/2, 0, 1/2, 0] and multiply it by the matrix T to obtain [1/5, 4/15, 11/30, 1/6].
We can also obtain this by looknig at the original state vector [0, 1, 0, 0] and multiplying it by T^{2}.
T^{2}  = 
1

When we multiply the original state vector by T^{2} we arrive at this same answer [1/5, 4/15, 11/30, 1/6]. This matrix T^{2} has an important property in that every state can reach every other state.
In general, if we have a transition matrix where for every cell in row i and column j, there is some power of the transition matrix such that the cell (i, j) in that matrx is nonzero, then we say that every state is reachable from every other state and we call the Markov Chain regular.
Regular Markov Chains are important because they converge to what’s called a steady state. These are state vectrs x = [x_{0}, …, x_{n}] such that xT^{n} = x for very large values of n. The steady state tells us how the Markov Chain will perform over long periods of time. We can use algebra and systems of linear equations to solve for this steady state vector.
For the Javascript program I’ve written, I have generated a set of painting samples for a fictional artist. The states are the different colors and the transitions are the colors that the artist will use after other colors. as well as the starting and ending colors. Given this input, we can form a Markov Chain to understand the artist’s behavior. This Markov Chain can then be used to solve for the steady state vector or to generate random paintings according to the artist’s profile. Be sure to check it out and let me know what you think.
]]>Lets say that I was interested in organizing this information into a new course. The order I present these topics is very important. Knowing which topics depend on one another allows me to use the topological sorting algorithm to determine an ordering for the topics that respects the preliminary work.
The input for the topoligical sorting algorithm is a Directed Acyclic Graph (DAG). This is a set of relationships between pairs of topics, where if topic 1 must be understood before topic 2, we would add the relationship (topic 1, topic 2) to the graph. DAGs can be visualized by a set of nodes (points) representing the topics. Relationships like the one above (topic 1, topic 2) can then represented by a directed arc originating at topic 1 and flowing in the direction of topic 2. We say that the graph is “Acyclic” because there cannot be a cycle in the topic preliminaries. This amounts to us saying that a topic cannot be a prerequisite for itself. An example of a DAG is shown in the image above.
With the topics represented as a DAG, the topologial ordering algorithm works by searching the set of nodes for the one with no arcs coming into it. This node (or these nodes is multiple are present) represents the topic that can be covered next without losing understanding of the material. Such a node is guaranteed to exist by the acyclic property of the DAG. Once the node is selected, we can remove this node as well as all arcs that originate at this node from the DAG. The algorithm then repeats the procedure of searching for a nod with no arcs coming into it. This process repeats until there are no remaining nodes from which to choose.
Now lets see how the topological sort algorithm works on the graph above. We will first need to count the indegree (the number of arcs coming into) each node.
Node  Indegree
—————
0  2
1  2
2  0
3  2
4  2
5  2
6  0
7  2
8  3
Node to be removed (i.e. node with the minimum indegree): Node 2.
Arcs connected to node 2: (2, 5), (2, 3)
Resulting Indegree Count:
Node  Indegree
—————
0  2
1  2
3  1
4  2
5  1
6  0
7  2
8  3
Node to be removed: Node 6:
Arcs connected to node 6: (6, 1), (6, 3), (6, 4), (6, 5), (6, 7), (6, 8)
Resulting Indegree Count:
Node  Indegree
—————
0  2
1  1
3  0
4  1
5  0
7  1
8  2
Node to be removed: Node 3
Arcs connected to node 3: (3, 0), (3, 8)
Resulting Indegree Count:
Node  Indegree
—————
0  1
1  1
4  1
5  0
7  1
8  1
Node to be removed: Node 5
Arcs connected to node 5: (5, 0), (5, 8)
Resulting Indegree Count:
Node  Indegree
—————
0  0
1  1
4  1
7  1
8  0
Node to be removed: Node 0:
Arcs connected to node 0: (0, 1), (0, 4)
Resulting Indegree Count:
Node  Indegree
—————
1  0
4  0
7  1
8  0
Node to be removed: Node 1
Arcs connected to node 1: none
Resulting Indegree Count:
Node  Indegree
—————
4  0
7  1
8  0
Node to be removed: Node 4
Arcs connected to node 4: none
Resulting Indegree Count:
Node  Indegree
—————
7  1
8  0
Node to be removed: Node 8
Arcs connected to node 8: (8, 7)
Resulting Indegree Count:
Node  Indegree
—————
7  0
Node to be removed: Node 7
Arcs connected to node 7: none
Resulting Indegree Count:
Node  Indegree
—————
Since there are no nodes remaining, we have arrived at a topological ordering. Going through this iteration, we can see that we arrived at the ordering (2, 6, 3, 5, 0, 1, 4, 8, 7). There were several occasions where there were multiple nodes with indegree of 0 and we could have selected an alternative node. This would have given us a different topological ordering of the nodes, but it would still be valid.
There are more learning opportunities and an interactive demonstration of the algorithm at Topological Sort Examples at LEARNINGlover.
]]>I can remember back when I was in school, still deciding whether I wanted to study pure or applied mathematics. One of the common questions I would receive from those in applied mathematical realms would sound like “What’s the point of doing mathematics with no real world applications?”. Generally my response to these questions was about the intrinsic beauty of mathematics, no different from an artist painting not for some desire to be a millionaire, but because of an burning desire to paint. Whether their paintings would one day be on the walls of a Smithsonian museum or sit on their mother’s refrigerator is generally outside of the thought process of the artist. So too, would I argue about the thought process of a pure mathematician.
When I was an undergrad and learned about the RSA algorithm (named for Ron Rivest, Adi Shamir, and Leonard Adleman who discovered the algorithm) it helped me explain this concept a lot better. The algorithm is based on prime numbers and the problem of finding the divisors of a given number. Many mathematicians throughout the ages have written papers on the beauty of prime numbers (see Euclid, Eratosthenes, Fermat, Goldbach, etc). For a large period in time one of the beautiful things about prime numbers was that they were so interesting in themselves. There were questions about how to check if a number is prime, question of patterns in primes, famous conjectures like the Goldbach conjecture and the twin prime conjecture, quick ways of finding prime numbers or numbers that are almost always prime, etc. In short, this was an active area of research that much of the applied world was not using. This all changed in 1977 when Rivest, Shamir and Adleman published the RSA algorithm.
The algorithm is in the area called public key cryptography. These algorithms differ from many of the previous cryptography algorithms, namely symmetric key cryptography. Whereas symmetric key cryptography depends uses the same device (key) to encode as to decode, public key cryptography creates two keys – one for encoding that is generally shared with others, and another for decoding which is kept private. These two keys in generally relate to a mathematical problem that is very difficult to solve.
In my example script for the RSA Algorithm, I show two people who want to communicate, Alice and Bob. Bob wants people to be able to send him messages securely so he decides to use the RSA algorithm. To do this, he first needs to think of two prime numbers, p_{1} and p_{2}.
From these, he computes the following:
n = p_{1} * p_{2}
Next, he computes Euler’s function on this n which can be calculated as
(n) = (p_{1} – 1) * (p_{2} – 1)
Then Bob looks for a number e that is relatively prime to . This is what he will use as the encryption key.
One he has e, he can calculate d, which is the multiplicative inverse of e in _{(n)}.
This means that e * d = 1 (mod (n)).
The public key that will be used for encryption will be the pair (e, n). This is what he posts publicly via his web page for others to communicate with him securely. Bob also has a private key pair (d, n) that he will use to decrypt messages.
Alice sees Bob’s public key and would like to communicate with him. So she uses it to encode a message. The formula she uses to encrypt her message is c = m^{e} mod n, where c is the encrypted message. Once Alice encrypts her message, she sends it to Bob.
Bob receives this encoded message and uses the private key (d, n) to decode the message from Alice. The formula to decrypt is m = c^{d} mod n.
For a more illustrative idea of how this algorithm works as well as examples, be sure to visit Script for the RSA Algorithm.
]]>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.
]]>I remember when I was younger I used to play the game of hideandseek 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 hideandseek and the DepthFirstSearch algorithm. The DepthFirstSearch Algorithm is a way of exploring all the nodes in a graph. Similar to hideandseek, one could choose to do this in a number of different ways. DepthFirstSearch 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 “tovisit”; 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.
Now consider how a Breadth First Search would be run on this graph.
The colors correspond to the order in which nodes are visited in DepthFirstSearch.
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 DepthFirstSearch Algorithm on Arbitrary Graphs.
]]>I remember when I was younger I used to play the game of hideandseek 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 hideandseek and the BreadthFirstSearch algorithm. The BreadthFirstSearch algorithm is a way of exploring all the nodes in a graph. Similarly to hideandseek, one could choose to do this in a number of different ways. BreadthFirstSearch 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 “tovisit”; 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.
Now consider how a Breadth First Search would be run on this graph.
The colors correspond to the order in which nodes are visited in BreadthFirstSearch.
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 BreadthFirstSearch Algorithm on Arbitrary Graphs.
]]>