LEARNINGlover

Blog

  • So You Want to Program? Lets Get Started!

    I can still remember when I first tool Algebra II. This was a class where it seemed like every week we were learning a new formula or law or procedure, and it was so easy to confuse the law of sines with the law of cosines or forget a step in a procedure and leave yourself at the mercy of the teacher as to how much credit you will receive. I remember making so many mistakes on the homework assignments and being frustrated with the whole process. At the same time, I had just convinced my mother to buy me a TI-81 calculator like all the other kids in my class. THe big thing then was using calculators to play games, but when I learned that I could make the calculator do these complicated procedures for me, it changed my life.

    Maybe your motivations for wanting to program are different from mine. Maybe you’ve realized the extra dimension that a programming language will give to an accountant’s resume or a lawyer’s resume. Maybe you have an idea that you think is too good to share so you’d rather work on it yourself. Or maybe you just want to keep busy at work instead of looking at youtube and facebook all day at work. Whatever your reason, hopefully this writeup can help.

    One of the first questions you need to answer is what language you want to learn. Different languages have different properties, so you want to know what you’re getting into. For example, if you plan to write programs to be part of a web page, C++ is probably not a good option because its programs are executable files which cannot be put into a web page. If you were to ask my opinion on a first language to learn in this day and age, I’d recommend JavaScript for a few reasons:

    • Its a simple language (when compared to C++ or Java for example), but it can still do some powerful things.
    • Its syntax (the rules of the language) is very similar to Java and C++, so those languages can become next steps after gaining an understanding of JavaScript. It also connects to other languages like Ajax and PHP, which can also become next steps.
    • It is can be interpreted by almost any browser. One of the biggest drawbacks to people learning programming or a programming language is the first step of finding the compiler/interpreter. With JavaScript all you need is the browser you’re currently using.

    Other languages have their own benefits, so don’t get too caught up if you’d rather start with a language other than JavaScript. I don’t mean to discourage any options. 

    My plan over the next few weeks is to go over a few concepts of programming in some popular languages.

    The first program one generally writes in a new language is called the “Hello, world!” program. If you think of this programming language as a new part of you, then the “Hello, world!” program is introducing this new part of you to the world. From a programmers prospective, we use it to understand the basic structure of a program in this new language – ala it introduces the programming language to us.

    There are certain things to try to take notice of in a “Hello, world!” program:

    • The case of the alphabetic characters. One of the biggest programming errors for beginners is understanding case sensitivity – i.e. that ‘int’ and ‘Int’ can be interpreted totally differently.
    • The location of non-alphanumeric characters. Many languages use parenthesis, semicolons, brackets, etc., and gaining an understanding of how to use these symbols is important.
    • How to output text. By definition, this program outputs “Hello, world!”, so understanding how this is done is important.
    • What does each line do? These programs are generally pretty short, so we should gain some understanding of the important parts of a program in this new language.

    Having stated that, lets introduce a few “Hello, world!” programs in different languages.

    JavaScript

    <html> 
    <body> 
    <script type="text/javascript">
     document.write("<p>Hello, world!</p>"); 
    </script> 
    </body> 
    </html> 

    JavaScript programs are embedded inside an HTML web page. This is why the first two lines of the JavaScript look like an HTML file – because thats exactly what it is. The third line tells the browser to expect JavaScript code for the next few lines (until the ‘</script>’ tag). The function document.write() writes text to the web page. In this case, that text is “Hello, world!”. Notice that the fourth line ends in a ‘;’. Just like we use a period to end sentences in English, we need a way to end statements in JavaScript. The ‘;’ character does this. We then close the script with ‘</script>’ tag. Then we use the html again to reach the end of the file. 

    I encourage users to try this program out. To do so, copy the above JavaScript and  paste it in a text editor and save it as “hello.htm”. Then open the file with Internet Explorer (my favorite browser for editing JavaScript), Chrome, Firefox, or whatever web browser you currently use. You should see something similar to: 

     C++

    #include <iostream.h>

void main()
{
     cout << "Hello, world!";
     return;
}

    Our C++ program starts with an ‘#include’ statement. This tells the compiler that our program will need resources that are included in another file (in this case, ‘iostream.h’ – we use this file for basic input and output). Notice that the ‘iostream.h’ file is included inside ‘<>’ brackets. Take note of that now. After that, we see the main function. Every C++ program must have a main function. This is where the program begins. Notice the statement ‘void’ in front of the word ‘main’. This says that the ‘return’ statement will not have a value after it (we could have instead said ‘int main()’, in which case we would need to have put ‘return 0;’). Notice next the (). This tells the compiler that main is a function (of no arguments). Then there is a ‘{‘ which shows that we are starting the main function. To output the “Hello, world!” statement, we use the statement ‘cout’ followed by ‘ << ‘. This is standard output syntax. Notice again that the statement is followed by a ‘;’. Like JavaScript, every statement in C++ must be followed by a ‘;’. Finally, the program closes with a ‘}’ closing the earlier ‘{‘.

    If you would like to compile this C++ program, you’ll need a C++ compiler. Downloading a C++ compiler depends a lot on your operating system and your preferences. You can go to http://en.wikipedia.org/wiki/List_of_compilers to select a proper compiler.

    Java

    public class HelloWorld
{
     public static void main(String [] args)
     {
          System.out.print("Hello, world!");
     }
}

    Java is an object oriented programming language, where everything must be inside an object – in this case the object is the class ‘HelloWorld’. The ‘{‘ indicates the beginning of the class. Notice that Java (like C++) has a main function, but it also has the keywords ‘public’ and ‘static’ in front of it. Every Java application must have a main function. Inside the parenthesis after the main function is the statement “String [] args”. This is the input to the program from the command line. We will discuss that more later. Then after the curly bracket ‘{‘, we have a call to the function ‘System.out.print()’. This is the basic output statement statement in Java. It writes things to the command line. What is passed to this function is the string “Hello, world!”. Following that, we have a semicolon to end the statement, a curly bracket to close the main function and a curly bracket to close the class HelloWorld.

    Again, if you would like to compile this Java program, you’ll need a Java compiler. I recommend Eclipse, but getting a Java compiler will depend on your operating system again. The same link as above (http://en.wikipedia.org/wiki/List_of_compilers) also lists a selection of Java compilers.

    Until next time, I would recommend going to a few sites that have helped me out.

    • One of my favorites is http://www.w3schools.com. They have a pretty good introduction to JavaScript as well as some other languages.
    • I also love the “Programming with C++” and “Programming with Java” books by Schaum’s outlines (actually I recommend just about everything they put out. Its quality material for a good price).
    • I recommend looking at source code and making modifications to it to see how the changes affect the output.

    Next time, I’ll try to go over variable types and user input, which make programs interactive. 

  • What Can I Do to Help End the Recession?

    I was reading through am article at UrbanCusp on Occupy Wall Street and it really got me to thinking about myself and my involvement in this movement. I’ve never attended an ‘occupy’ rally and rarely read the reports. I did attend the “One Nation” rally last year as well as the Jon Stewart/Stephen Colbert “Rally to Restore Sanity”, but does that really mean anything?

    In the midst of this recession, I have a few friends that are unemployed and others who feel underemployed. A large part of me wonders what I should be doing to help with this? Ultimately, I guess I would like to help end the recession, but how? And to what end? The OWS movement shines light on the growing wealth disparities between the different economic classes in America. There is also a large wealth gap between White family income and Black family income. These are problems I grew up learning about, and, honestly, feeling helpless in terms of doing something about it, and a large part of me wonders what I can do about it. A large part of me feels helpless, like there’s not much that I can do to help drop the unemployment rate or increase property values or help to solve a ton of other problems that America is currently facing.

    But as always, I guess there’s a little voice in my head telling me that maybe I can’t end poverty in itself, but I can do things to help those I come in contact with to help find jobs or to become better equipped on the job search, or to just keep their heads up during these tough times. I mean, that’s partially why I created this site.

    I don’t like hearing people, particularly my friends, say that they are limited by what their teacher/book/class is teaching them. Some of my friends are finished with school and are not interested in going back to take classes (or paying more money), but would still like to learn new material. We live in a world where information and new material is only a click away. So while a more ‘formal’ means to building your resume may be through classes and certifications, another comes through simply taking initiative and being aggressive and willing to try new things and to learn new things.

    I’ve found that there’s a certain feeling that comes along with learning something new. I don’t know about you, but suddenly I feel like I can take on the world. Doors that we didn’t know existed are suddenly opened and avenues that once seemed shut out suddenly become open.

    But a big part of the ‘learning game’ is understand that you are not limited by your teacher or your book. In the process of learning, especially learning online, you’ll come across many sources that you do not understand. Maybe its your first source, maybe its your first five or first 50 sources, but the key is to understand that its a process and never lose hope. All you need is one source to learn new material. And I also stress not to be afraid to ask questions – whether these are questions to yourself, questions to an informed friend, or just posting them at a message board. One of my largest frustrations with the teacher / student model for learning is that some teachers shun questions, which makes students feel unintelligent for asking questions. But one of my favorite musical lyrics goes “even the genius asks his questions”, which I constantly use to inspire me throughout this learning process.

    But that’s enough talking on my end, my question is what are you going to do to help end the recession?

     

  • The Degrees of Consciousness of a Black Nerd

    The great W.E.B. Du Bois may have underestimated things a little with his theory on double consciousness that he proposed in “Souls of Black Folk” – especially when it comes to Black nerds. There’s definitely the double-consciousness that of being both Black and American and loving a country that allows many of her children to dwell in the slums without caring much about them. But there’s also a treatment in America in general and Black America in specific that makes nerds feel like outcasts, like we’re weird or abnormal. In relationships, we’re stereotypically thought of as weak, or as the counter to the macho – testosterone images seen in movies. In school, the supposed sanctuary of a nerd, we’re often ignored – until mid-terms and finals when people beg for us to help them pass. These are just some things that come to mind as I sip my morning coffee, but I know that others can think of more.

    And what’s more is that we endure much of this in silence. We’ve learned to simply smile when people compare us to Urkel or Carlton. Many of us have learned to ‘look the part’ as we walk down the streets. We think to ourselves, “Don’t think too much about that problem you were working on earlier today, you’ll look like you’re talking to yourself.” or “No matter how excited you are about finishing that program, don’t talk about it in the bar cause you’ll just get cold stares and confused faces”.

    But is that really how we should respond to this? Should we hide from out intellect or our habits? I find that hard to do, bordering on the impossible. One thing is that I’ve been this way for so long that subconsciously I always find myself acting this way, analyzing patterns in things I see, looking for connections. But the more important thing is why should I care if you care about it? If it relaxes me, then why should I stop doing it? Just to please somebody (some people) who probably don’t like me anyway?

    This brings up an alternative approach which is to just stop hanging around these people? But how can I disconnect myself from my community that practically raised me? Who else can I connect with about the plights of being Black in America and the challenges we still face? I’m not naive enough to think that I could just walk into another community and and share these struggles. This approach leaves the nerds in a life of isolation because nobody quite understands our struggle.

    Unfortunately, I see countless examples of Black nerds taking these two approaches – either deciding that fitting in is more important, and thus living this secret life as a nerd, or simply deciding that they’d be better off outside of the harassment of our community. So the next time you see a Black nerd, try to understand that he’s struggling with a lot more than just some number crunching.

  • User Generated Flash Cards

    When I originally started LEARNINGlover.com, I had the idea in my mind that I would utilize my skills in programming and mathematics to help others. While this remains an important goal of mine, I remain curious about how I can use this site in other ways. One thought that has occurred to me for a while is how do I expect to handle users who want to learn things that are not currently offered by the site? I do plan to regularly add sections, data and programs to the site, but what about people who don’t want to wait, or who don’t want to learn the things that I have been studying? My thought process on this is that I’d like to provide users with tools that I believe can be used to help learn, in particular to help teach yourself, just about anything – as long as you have a good source. We live in an age where information is everywhere. With just the click of a mouse we have the power to download an online textbook, read journal articles, learn a new language and a host of other things – if we know how to use this information correctly.

    The concept of flash cards has been around much longer than I have. That said, I don’t see flash cards used outside the realm of vocabulary often. When I began studying theoretical mathematics, I found the number of vocabulary words offered in each class intimidating. So by instinct, I just used flash cards to learn these words. The class, though, also consisted of theorems, lemmas, proofs, corollaries, etc that do not fit into the vocabulary ‘box’ that I had seen flash cards used for. Nonetheless, I needed to study these concepts if I was going to do well in my classes.

    What I found is that in my notes, not only are the notes themselves important, but there is also a question – ‘Why is this line that I just underlined important?’ Or phrased differently, ‘What question was this line written to answer?’ Take for example the following note which may come up in a class on Graph Theory:

    The complexity of Kruskal’s algorithm is O(E log V).

    This is certainly an important fact, as we are interested in how well algorithms perform and would like to compare these complexities. But once I have underlined it in my notes, I want a way to remember it. I know the question that will come to me during an exam or in real life practice is:

    What is the complexity of Kruskal’s algorithm?

    So I create a flash card with this question and answer pair.

    I don’t have any ‘rules’ for creating these questions, but here are some things that come to mind:

    1. In general I try to make my questions open-ended (not yes/no questions).
    2. For definitions, I generally ask “What is the definition of <insert word>”.
    3. Many times, things such as theorems, lemmas, or corollaries will connect two things together (either in one direction or two), so I ask questions like “What is the relationship between <insert concept 1> and <insert concept 2>?” for these.
    4. Other times, theorems simply state facts (like the example above), or link a well known function (complexity) to a particular object (Kruskal’s algorithm). For these I form questions like “What is the value of <insert function> on <insert object>?”
    Of course I don’t live by these rules and feel free to change or add to them as you like. I have used similar concepts on reading and understanding journal papers as well as some philosophy books. I hope this helps you as much as it has helped me. 

  • Text Summarization

    I have written a text summarization program here

    This is a naive way of summarizing large blocks of text. It is based on the elementary school idea that the main idea of a text can be found in the first paragraph. So given a long text, it will output the first sentence of each paragraph as the summary.

  • Bellman-Ford Algorithm

    I just finished a script which executes the Bellman-Ford Algorithm on a randomly generated directed graph (possibly with negative arcs). It can be accessed here.

    The Bellman Ford algorithm is another shortest path algorithm. Unlike Dijkstra’s algorithm, though, this algorithm can handle edges with negative weights and detect negative cycles in a graph. Negative cycles are important because in a graph with negative cycles, there is no shortest path to some nodes since a negative cycle can be iterated an infinite number of times.

    The algorithm works by initially setting the distance from the source node to all other nodes to be infinity. The distance to the source is then updated to be 0 since we are already there.
    Next we proceed through each edge (u, v) and check the condition that if the distance to u plus the weight of the edge (u, v) is less than the distance to the node v, then we have just found a shorter route to v.

    This condition on the edges only needs to be checked at most |V| times for each edge since any path will contain at most |V| edges, which means that the distance of a node can be updated at most |V| times.

    If after |V| times there is still a node whose weight can be updated, it signifies the existence of a negative weight cycle and the Bellman-Ford will show that this cycle exists, but will be unable to find shortest paths in this problem as shortest paths no longer exist.

     

  • Dijkstra’s Algorithm

    I’ve just written a script that executes Dijkstra’s algorithm that seeks to find the shortest path tree on a randomly generated graph.

    Given a weighted graph G and a vertex s, the single node shortest path problem seeks to find the shortest path from s to every other vertex in this graph such that the sum of the weights of the edges along these paths is minimized. One famous algorithm for this problem is Dijkstra’s Algorithm, which constructs this shortest path tree using techniques of greedy algorithms and dynamic programming.

    Dijkstra’s Algorithm works as follows.

    • Initially we have an empty path tree T, and assume that the distance to every vertex in the graph has some maximum cost, say infinity, i.e. w(v) = infinity for all v in V.
    • Add the node s to the tree, and give the associated path cost a value of zero, i.e. w(s) = 0.
    • Find the edge which is adjacent to T that adds the vertex whose cost is minimum, i.e. we look for an e = (u, v) such that u is in T, and v is not in T and w(u) + cost(u, v) < w(v) is minimum. If no such edge exists go to 5.
    • Add the corresponding edge and vertex to the tree, and update the weight vector of the vertex v. Go to 3.
    • The path tree T now represents the shortest path from the vertex s to all other vertices reachable in the graph G. The weight vector w represents the costs of these paths.

    For an example of Dijkstra’s algorithm executed on the Graph with the following adjacency matrix:

    0 1 2 3 4 5 6 7
    0 – – 2 4 – – 20 –
    1 – – – 11 11 7 5 –
    2 2 – – – 10 – 7 –
    3 4 11 – – – – – 2
    4 – 11 10 – – – – –
    5 – 7 – – – – – 14
    6 20 5 7 – – – – –
    7 – – – 2 – 14 – –

    Graph with 8 Nodes

    Suppose we are interested in discovering the shortest paths from the node 0.

    Initially Dijkstra’s algorithm constructs an empty path tree, T = {}.

    Because we want to discover the shortest paths from the node 0, our first step will be to add this node to the tree and update the weight vector.
    T = {0}
    w(0) = 0.

    Now we will consider the edges adjacent to T, {(0, 2), (0, 3), and (0, 6)}. Our assumption is that the shortest path of every vertex in T has already been computed correctly and we will seek the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T. The edge that does that currently is (0, 2) since w(0) = 0 and c(0, 2) = 2. We add the node 2 to T and update the weight vector.
    T = {0, 2}
    w(2) = 2.

    The edges adjacent to T are now {(0, 3), (0, 6), (2, 4), (2, 6)}.
    The associated path costs are:
    w(0) + c(0, 3) = 0 + 4 = 4
    w(0) + c(0, 6) = 0 + 20 = 20
    w(2) + c(2, 4) = 2 + 10 = 12
    w(2) + c(2, 6) = 2 + 7 = 9
    We can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (0, 3). We add the node 3 to T and update the weight vector.
    T = {0, 2, 3}
    w(3) = 4

    The edges adjacent to T are now {(0, 6), (2, 4), (2, 6), (3, 1), (3, 7)}.
    The associated path costs are:
    w(0) + c(0, 6) = 0 + 20 = 20
    w(2) + c(2, 4) = 2 + 10 = 12
    w(2) + c(2, 6) = 2 + 7 = 9
    w(3) + c(3, 1) = 4 + 11 = 15
    w(3) + c(3, 7) = 4 + 2 = 6
    We can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (3, 7). We add the node 7 to T and update the weight vector.
    T = {0, 2, 3, 7}
    w(7) = 6

    The edges adjacent to T are now {(0, 6), (2, 4), (2, 6), (3, 1), (5, 7)}.
    The associated path costs are:
    w(0) + c(0, 6) = 0 + 20 = 20
    w(2) + c(2, 4) = 2 + 10 = 12
    w(2) + c(2, 6) = 2 + 7 = 9
    w(3) + c(3, 1) = 4 + 11 = 15
    w(7) + c(5, 7) = 6 + 14 = 20
    We can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (2, 6). We add the node 6 to T and update the weight vector.
    T = {0, 2, 3, 6, 7}
    w(6) = 9

    The edges adjacent to T are now {(2, 4), (3, 1), (5, 7) (6, 1)}.
    The associated path costs are:
    w(2) + c(2, 4) = 2 + 10 = 12
    w(3) + c(3, 1) = 4 + 11 = 15
    w(7) + c(5, 7) = 6 + 14 = 20
    w(6) + c(6, 1) = 9 + 5 = 14
    We can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (2, 4). We add the node 4 to T and update the weight vector.
    T = {0, 2, 3, 4, 6, 7}
    w(4) = 12

    The edges adjacent to T are now {(3, 1), (5, 7), (6, 1), (4, 1)}.
    The associated path costs are:
    w(3) + c(3, 1) = 4 + 11 = 15
    w(7) + c(5, 7) = 6 + 14 = 20
    w(6) + c(6, 1) = 9 + 5 = 14
    w(4) + c(4, 1) = 12 + 11 = 23
    We can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (6, 1). We add the node 1 to T and update the weight vector.
    T = {0, 1, 2, 3, 4, 6, 7}
    w(1) = 14

    The edges adjacent to T are now {(5, 7), (1, 5)}.
    The associated path costs are:
    w(7) + c(5, 7) = 6 + 14 = 20
    w(1) + c(1, 5) = 14 + 7 = 21
    We can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (5, 7). We add the node 5 to T and update the weight vector.
    T = {0, 1, 2, 3, 4, 5, 6, 7}
    w(5) = 20

    Now that T contains all the nodes from the tree, we know the shortest path from node 0 to all other nodes and and have solved the problem. The associated weight vector is w = [0, 14, 2, 4, 12, 20, 9, 6].

    To learn more and see more examples, view Dijkstra’s Algorithm at LEARNINGlover.com

  • Kruskal’s Algorithm

    I’ve just written a script that executes Kruskal’s algorithm on a randomly generated graph.

    Given a weighted graph, many times we are interested in finding a minimum spanning tree (MST) for that graph. These have several applications in areas like transportation and the network simplex method. We already discussed Prim’s algorithm. Another method for generating minimum spanning trees is Kruskal’s algorithm. A spanning tree is a subset of the edges of a graph that connects to every vertex, but contains no cycles. This spanning tree is called a minimum spanning tree if in addition the sum of the weights of the edges included in this tree is less than or equal to the sum of the weights of the edges of any other spanning tree for this graph.

    Kruskal’s algorithm works by the following procedure.
    1. Initially each vertex is a stand-alone tree, so for each v in V, we define the tree Treev = {v}. The set of selected edges E* is initially empty.
    2. Find the edge e = (u, v) of minimum weight such that u and v belong to different trees. If no such edge exists, go to 6.
    3. Merge the trees Tlookup(u) and Tlookup(v).
    4. Add the edge e to E* and remove the edge e from the graph.
    5. If the size of E* is less than n – 1, go to step 2. Else go to step 7.
    6. If you reached this step. then the graph is not connected.
    7. If you reached this step, then E* is a minimum spanning tree.

    For example, consider the graph represented by the following adjacency matrix:

    0 1 2 3 4
    0 – – – 13 12
    1 – – – – 16
    2 – – – – 24
    3 13 – – – 13
    4 12 16 24 13 –

    Graph with 5 nodes

    Initially we have 5 distinct trees and E* = {}/
    T0 = {0}
    T1 = {1}
    T2 = {2}
    T3 = {3}
    T4 = {4}.

    The first step of Prim’s algorithm says to find the cheapest edge such that its two endpoints belong to different trees. This will be the edge (0, 4) with a cost of 12. So E* = {(0, 4)}. We then merge the two trees so that our trees are now:
    T0 = {0, 4}
    T1 = {1}
    T2 = {2}
    T3 = {3}

    Again, we look for the cheapest edge such that the endpoints of the two edges are in different trees. There are two edges with a cost of 13 (either (0, 3) or (3, 4)) so we will arbitrarily choose (0, 3) and add it to our tree. So E* = {(0, 4), (0, 3)}. We again merge the associated trees and it results in the following trees:
    T0 = {0, 3, 4}
    T1 = {1}
    T2 = {2}

    The cheapest edge that has endpoints in distinct trees will be the edge (1, 4) with a cost of 16. We add this edge to our tree. So E* = {(0, 4), (0, 3), (1, 4)}. Once we merge the associated trees we have the following:
    T0 = {0, 1, 3, 4}
    T2 = {2}

    The cheapest remaining edge that has endpoints in distinct trees will be the edge (2, 4) with a cost of 16. This makes E* = {(0, 4), (0, 3), (1, 4), (2, 4)}. We merge the associated trees and arrive at:
    T0 = {0, 1, 2, 3, 4}

    Because T0 contains all the nodes in the graph it is a spanning tree. Its total cost is 12 + 13 + 16 + 24 = 65.

    To learn more and see more examples, view Kruskal’s Algorithm at LEARNINGlover.com

  • Prim’s Algorithm

    I have just written a script that executes Prim’s Algorithm that finds the minimum spanning tree on a randomly generated graph.

    Given a weighted graph, many times we are interested in finding a minimum spanning tree (MST) for that graph. This has many applications including the very important network simplex method. Prim’s algorithm is a greedy method which does finds this MST. A spanning tree is a subset of the edges of a graph that connects every vertex, but contains no cycles. This spanning tree is called a minimum spanning tree if in addition the sum of the weights of the edges included in this tree is less than or equal to the sum of the weights of the edges of any other spanning tree for this graph.

    Prim’s algorithm works by the following procedure.
    1. Let Treev be the set of vertices included in the tree, and TreeE be the set of edges included in the tree. Initially Treev and TreeE are empty.
    2. Add an arbitrary vertex to Treev (TreeE is still empty).
    3. Find the edge e of minimum weight such that one vertex is in Treev and vertex is not in Treev. Add the associated vertex to Treev, and add e to TreeE.
    4. If edge was found in step 3, goto 5, else go to 6.
    5. If the number of vertices in Treev is less than the number of vertices in the original graph, then the graph is not connected and thus does not contain a minimum spanning tree. Goto 8.
    6 If the number of vertices in Treev is less than the number of vertices in the original graph, go to 2, else go to 7.
    7. Output “The Minimum Spanning Tree is “, TreeE.
    8. Output “This graph does not have a minimum spanning tree because it is not connected. ”

    For example, consider the graph represented by the following adjacency matrix:

    0 1 2 3 4
    0 – – – 13 12
    1 – – – – 16
    2 – – – – 24
    3 13 – – – 13
    4 12 16 24 13 –

    Graph with 5 nodes

    Initially our tree (Tv is empty). The first step says to choose a random vertex and add it to the tree, so lets choose vertex 2.

    Iteration 1: Now our tree contains the vertex 2 (i.e. Tv = {2}) and likewise TE contains the edges coming from Tv. Thus TE = {(2, 4)}.
    We want to choose the cheapest edge that has one endpoint in Tv and one endpoint not in Tv. These edges are represented by TE. Notice that TE only contains one edge, so we select this
    edge, which has a cost of 24.

    Iteration 2: Our tree thus contains the vertices 2 and 4 (i.e Tv = {2, 4}) and likewise TE contains the edges coming from Tv. Thus TE = {(0, 4), (1, 4), (3, 4)}.
    Again, we want to choose the cheapest edge that has one endpoint in Tv and one endpoint not in Tv. This will be the edge (0, 4) which has a cost of 12.

    Iteration 3: Now Tv = {0, 2, 4} and TE = {(1, 4), (3, 4), (0, 3)}. The cheapest of these three edges is the edge (0, 3) with a cost of 13, which means we will add it to our tree.

    Iteration 4: Now Tv = {0, 2, 3, 4} and TE = {(1, 4)}. Since (1, 4) is the only edge connected to our tree we add it and it has a cost of 16.

    Iteration 5: Now Tv = {0, 1, 2, 3, 4} and TE = {}. Because our tree contains all the vertices of the graph it is now spanning tree. The cost of this spanning tree is 24 + 12 + 13 + 16 = 65.

    To learn more and see more examples, view Prim’s Algorithm at LEARNINGlover.com

  • Gaussian Elimination

    I have just written a script which executes the Gaussian Elimination Algorithm.

    When we have a collection of lines we wish to know if they all intersect at some point. Many times we are interested in determining what that point is. In order to calculate this information, we first need an understanding of the lines themselves. The way the Gaussian Elimination Algorithm works is that the collection of lines are input using a notation of Ax = b, where the matrix A is called the coefficient matrix, as the nth row of it corresponds to the coefficients for the nth line being considered. The vector b represents the right hand side vector (in two dimensions, we would call these constants the y-intercepts of the lines. In higher dimensions they hold a similar property). The vector x represents the point where the lines intersect. It is this quantity which Gaussian Elimination seeks to determine.

    The basic procedure of Gaussian Elimination is to use \”elementary row operations\” on the matrix (A|b), which is called the augmented matrix, to transform A into upper triangular form. Once this is done, a procedure called back-substitution can find the solution (x) to this problem.

    The elementary row operations that we are allowed to perform are:

  • Interchange two rows.
  • Multiply a row by a nonzero number.
  • Add a row to another one multiplied by a number.

    • For the last property listed above, we will determine this number by dividing the coefficient of the term we which to eliminate by the negative of the coefficient of the element on the main diagonal of the same column of the matrix. This will have the property of cancelling out, or producing a desired zero in the resulting row.

    If this algorithm produces an upper triangular matrix from which we can solve for x using back-substitution. This procedure of back-substitution is simply solving for the vector x from the bottom of the matrix to the top. If the algorithm does not produce an upper triangular matrix (because somewhere along the line, we are unable to obtain a ratio because we have zero’s on the diagonal and all zeros below the diagonal), then we say the matrix is singular. This means that there is no unique point where the lines all intersect.

    To learn more and see more examples, check out My Script on Gaussian Elimination.