Decomposition algorithm

In order to illustrate how Question 4 of Assignment 1 should be answered, I will give a sample answer. This demonstrates how I would like you to write the pseudocode in cases like this. Please do not use terms specific to individual computer languages in answering such questions, just ones which occur widely, such as “for”, “if” and “while” commands.  Since you will be using Python as part of the course, I suggest that you see if you can run the code successfully (after installing Python), and play around with it to see if you can improve it or make it applicable to other problems. Also, notice how the pseudocode I have written forms the basis for a Python script. Before you start writing a script, you should write out in a crude form what you want the script to do, and have a clear idea of the components of your code.

The answer I give below is longer than the answer you would need to give when answering such a question. I am giving the lengthier answer to demonstrate the reasoning one would use.

Question: Write an algorithm that decomposes a graph into its connected components, using as input the adjacency matrix of the graph.

Roughly, we start with row 1 of the matrix and check which vertices are connected to the first one. We put these all into a set which we will call V_1. Remove the first vertex from V. We move on to the next row. If the second vertex is connected to the first, we add all the other vertices connected to the second to V_1. If it is not connected to the first, we create another set V_2 and include the second vertex and all those connected to it in V_2. Moving through all the rows, and following a similar process, we are sure to cover all the vertices and generate all the connected components. We want the algorithm to return all these components at the end, which will be our result.

There are more efficient ways of doing this, of course. For instance, we can start with a set V containing all the vertices, and remove each vertex as soon as it appears in one of the components, and only keep on doing this until the set V is non-empty. Thus, if the graph is connected, we might be able to have our algorithm halt more quickly. For now though, we just want a basic algorithm in place, and can refine it later (if it proves too cumbersome for applications to large graphs, for instance).

Algorithm:

Let V = \{v_1, \dots ,v_n\} be the set of vertices. The adjacency matrix is A = (a_{ij}), i,j \in \{1,\dots ,n\}.

while V \neq \emptyset do:

for i=1 to n: # this tells the algorithm to go through each row

if v_i \in V_k for some k<i, and k is the largest such value: # To see if it is connected to an earlier vertex

V_i = V_k

V = V\setminus \{v_i \}

V_k = V_k \cup \{v_i \}

for j = 1 to n: # this is for going through each entry of a row

            if a_{ij} == 1:

               V_k = V_k \cup \{v_j \}

V = V\setminus \{v_j \}

    else:

        V_i = \{v_i \}, V = V\setminus \{v_i\}

        for j = 1 to n:

            if a_{ij} == 1:

           V_i = V_i \cup \{v_j \}

return all V_i

 

(This could be done a lot quicker by creating a function which examines each row for entries of value 1 and adding them to a certain set, which is what you would (preferably) do in Python.)

Note that we do not actually need to go through each entry of row k. We will actually only need to go through all entries from k+1 on. However, looking at all entries does not affect the complexity too much, and we stick with this method for simplicity.

Does this algorithm actually work? Test it by creating a graph and running the algorithm by hand. You could also code this in Python to verify, but you will then need to involve some more technicalities, such as how to create arrays and lists…

Lastly, does this algorithm have the desired complexity? If not, what is its complexity, and how can you alter it to have the required complexity?

 

 

 

 

Advertisements

Learning resources

One significant problem with studying mathematics or related topics is that, throughout all your years of education, nobody ever actually taught you how to study it! In my continuing quest to improve my own learning abilities, I have come across some great resources. Some of those I will mention here in future posts, but most of my summaries of the most useful concepts I am posting on my other blog, which you can find at

https://nonlinearprogrammingblog.wordpress.com/.

Even though the blog is seemingly aimed at a second-level course, I still urge you to check it out. All the concepts and techniques I discuss there are ones I use every day as a professional mathematician.

Some resources for algorithms

The following link takes you to an animated explanation of Dijkstra’s algorithm. If at first it doesn’t load, just load again:

http://www.csanimated.com/animation.php?t=Dijkstra%27s_algorithm.

The next link has some demos of various algorithms, including Dijsktra and Ford-Fulkerson:

http://weierstrass.is.tokushima-u.ac.jp/ikeda/suuri/dijkstra/DijkstraApp.shtml?demo1.

If you have access to Mathematica, you should take a look at

www.combinatorica.com.

P vs NP: New book

From Lance Fortnow comes “The Golden Ticket: P, NP and the Search for the Impossible”:

“The P-NP problem is the most important open problem in computer science, if not all of mathematics. The Golden Ticket provides a nontechnical introduction to P-NP, its rich history, and its algorithmic implications for everything we do with computers and beyond. In this informative and entertaining book, Lance Fortnow traces how the problem arose during the Cold War on both sides of the Iron Curtain, and gives examples of the problem from a variety of disciplines, including economics, physics, and biology. He explores problems that capture the full difficulty of the P-NP dilemma, from discovering the shortest route through all the rides at Disney World to finding large groups of friends on Facebook. But difficulty also has its advantages. Hard problems allow us to safely conduct electronic commerce and maintain privacy in our online lives.”

It can be bought for the Kindle at Amazon.com. It seems to be available through the Exclusive Books website as a hardcopy, but it is quite expensive. I would suggest rather buying the Kindle edition and reading it with a Kindle reading app on your PC, if you don’t own a Kindle.

The author has a complexity blog at http://blog.computationalcomplexity.org/.

Update: It is more reasonably priced on Kalahari.com than on the Exclusive Books site (like most books).