Algorithms and Data Structures coursework2 15/16 (QandA)

This page is to keep a record of questions I have been asked about the second coursework, and my answers. For reference, here is the specification for coursework 2, and here is the template java file acyclic.java.

Questions and Answers

Qn: Could you please clarify whether in the programming part we are allowed to manipulate the original inputs, or should those remain untouched and a copy be produced.
Ans: This question was regarding the code to be written for (T1) and (T2), each of these methods having a graph given as input. For both these questions, the answer is that the input graph should not be modified; a new output graph should be created and returned.
Qn: In T1, we are given with a "directed graph" and can I assume that this graph doesn't contain any self loop?
Ans: Probably you can assume that you won't be passed any graph with a self-loop in it. However, I think that the acylicity algorithm is *just* as easy to implement if we check for self-loops (I don't believe the assumption of no self-loops makes anything easier). So why not just write the more general algorithm which also checks for self-loops...
Qn: Another question is for both T1 and T2. Can I just assume that the graph given is correct. For example in T2 we are given with an "simple undirected graph", do we need to test that "graph[i][j] = graph[j][i] "?
Ans: You don't need to check for this symmetricity. However, if you *assume* you are always getting correct input, make sure that the graphs you construct (in T3 say) are always built to *satisfy* this condition.
Qn: I have a question respect to T2 of the assignment 2. I am testing a graph with |E| = 8, therefore my uniform probability is 1/256. That means, as I understand, less than 1% of the times an edge from the original graph will be a directed edge in the new graph. Is this correct? is correct to return a graph with only nodes and no edges?
Ans: No, it's not correct. Your method accepts an **original** graph with some number of edges (8 in your example).
You must give **directions** to each of the edges, each randomly decided by a toss of the coin - with probability 1/2 it gets (i -> j) and with the other probability it gets (j -> i).
No matter what you do, you will have 8 **arcs** (not edges) in your output graph ... but the arrows may be in very different orders. For any ***particular*** collective assignment of arrows, the probability that particular orientation comes up is 1/2^8.
Qn: I was also wondering, for Erdos-Renyi you specify an example in which you generate a simple undirected Graph. In the task you give for this question though, you just say "random undirected graph" - does this mean that it does not have to be a simple graph? In your second observation you point out that the expected number of edges would be p * (n C 2), which can't be the case if we make a simple graph (which would only allow for a maximum number of edges that is smaller than this value).
Ans: No, the Erdos-Renyi model *always* generates a simple graph; the graph generated will never have loops or parallel edges. Your observation about the expectation is not correct. For n vertices, there are (n \choose 2) = n(n-1)/2 different pairs of vertices. Each one has probability p of getting added by the Erdos-Renyi process.
Qn: I'm having a bit of difficulty understanding the equation at the top of page 5, representing the expected number of AO's for the Erdos-Renyi graphs.
Ans: Ok. This is the first equation on that page, I take it. The sum is explicit - it is summing over all (simple undirected) graphs G= (V,E) such that |V| =n ... so over all (simple) undirected graphs G on n vertices. If you want you could think of the sum being taken over all (simple undiredected) sets E of edges for n vertices, given that V is always the same.
The term being summed for each such G is:

(the-probability-that-G-is-generated-in-Erdos-Renyi(p,n))*(number of AOs of G)
Qn: Problems getting an understanding of the recurrence of Theorem 7 for A_n(x) (in the "Task 4").
Ans: Why don't you expand out the right-hand side of the A_n(x) equation, for some smallish values of n. Do that for a few small n values and see what that looks like.
Qn: Could you send me a correct value for E for a particular n and p so that I could verify the correctness of my algorithm?
Ans: One thing you can check is n=3, with any p. The expectation will be the value of (1-p)^3 + 6p.
Qn: What are the base cases for the A_n recurrence?
Ans: A_0(x) = 1 and A_1(x) = 1 for any x. These are directly from the *definition* of the A_n(x) in terms of the A_{m,n}. (in fact you only need to define the A_0(x) value and the recurrence can compute the 1 value for A_1(x)).
Qn: I just wanted to verify how large and precise results our implementation should support. Given the rapid growth of the Robinson-Stanley recurrence generic data types will not allow going higher than around n=10. At least if we would like to get valid return values. On the other hand, using classes like BigDecimal would make the program run much slower.
Are we concerned with simply the runtime of the algorithm implemented, and assuming constant-time arithmetic operations (add, multiply)?
Ans: Yep, the numbers grow pretty big with n. I'm not expecting you guys to wheel in BigDecimal, just work with the Java int. As it is, the main interest is in getting you to understand/design the algorithms rather than knowing what the answer will be for a particular p and n.
Qn: I have another question: What do you consider the complexity of the java pow() method to be? If you consider it to be Θ(n), do I need to implement a divide-and-conquer power algorithm for my dynamic programming solution to be considered Θ(n^2)?
Ans: It would be considered to be Θ(lg(n)).
Qn: Just looking to clarify what's expected for question 5 of the coursework. Are we to import a library with a 'choose' function and use that to calculate "n choose i", or are we find our own way of generating the "choose" values?
Ans: You can use the built-in "choose" if you want. If you do this, you should assume Θ(\min{i, (n-i)}) time for the running time (number of mults) for *one* (n \choose i) call.
Of course if you compute the choose values directly, you might be able to share work among the different choose calls, to have a lesser amount of work/multiplications for the set of "choose" operations as a whole.
Qn: I noticed that on question 6 in the assignment, you ask us to calculate an expected value for |AO(G)|. In the code that you provided to us, the comment above estimErdosRenyi is instead asking for the variance of the number of AOs. Do you want the method to return the former, or the latter?
Ans: :-/.
The comment in acyclic.java (above "estimErdosRenyi") is incorrect. My original plan was to get you to estimate variance, but I changed my mind and forgot to edit acyclic.java. Please implement "estimErdosRenyi" exactly as described in the coursework specification.

Mary Cryan, mcryan AT inf DOT ed DOT ac DOT uk, Informatics Forum 5.18, ext. 505153