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 . Remove the first vertex from . 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 . If it is not connected to the first, we create another set and include the second vertex and all those connected to it in . 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 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 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).
Let be the set of vertices. The adjacency matrix is , .
for to : # this tells the algorithm to go through each row
if for some , and is the largest such value: # To see if it is connected to an earlier vertex
for to : # this is for going through each entry of a row
for to :
(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 . We will actually only need to go through all entries from 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?