Series of Corner Case Questions

[Miles Pedrone]

Question 1:
When implementing maxst() in AdjMatrixGraph, we have an ArrayList of
Edges which we update every time we add an edge. Our problem is that
if we don't use this ArrayList and instead iterate through our matrix,
it will take O(V^2) instead of the required O(E(logV)). Is this
allowed? We're basically not using the data structure in order to
achieve the correct runtime.

Question 2:
When implementing clustering(), there are two cases which arise in
division by zero: k = 0 and k = 1. What should we return for these
values?

Question 3:
Is there any reason we should be using a LinkedList over an ArrayList
for the AdjListGraph implementation? We have heard conflicting
information.

Question 4:
For maxst() and both recommendation systems we need the weights of the
undirected graph. If two vertices each have edges pointing towards
each other with different weights, what should we use for the weight
of the edge: the sumation or the larger of the two?

TLDR: if A--->B has weight 5 and B--->A has weight 4, is our
undirected weight 5 or 9?

Question 5:
For the 1.2 deliverables, we need to create charts for indegree and
outdegree. What exactly should we put in these? What does it mean by
"distribution"? Are we just outputting a range of indegrees/outdegrees
for every vertex for the graphs given, or is it somethign else?

[Keith Newman]

For Question 4, I believe it was explained somewhere that you use the
sum of the two weights.

[Ariana Mott]

Question 2: Robert said he would accept NaN or -1

[Teddy Ni]

Question 3: For an adjacency list, we would like to find the list of
vertices connected to vertex v in O(1). Is this possible if the outer
list in your implementation is a linked list?

I have opinions on Question 1 and Question 5 that are most likely
correct, but it would be better if another TA with definite answers
can chime in and answer those.

Teddy

[Robert Escriva]

On Sun, May 01, 2011 at 05:45:59PM -0400, Miles Pedrone wrote:
> Question 1:
> When implementing maxst() in AdjMatrixGraph, we have an ArrayList of
> Edges which we update every time we add an edge. Our problem is that
> if we don't use this ArrayList and instead iterate through our matrix,
> it will take O(V^2) instead of the required O(E(logV)). Is this
> allowed? We're basically not using the data structure in order to
> achieve the correct runtime.

Your actual Max ST algorithm should take the required O(E log V) time;
however, you may take O(V^2) time for culling all edges from the matrix.

This is one downside of using an Adjacency Matrix.

> Question 2:
> When implementing clustering(), there are two cases which arise in
> division by zero: k = 0 and k = 1. What should we return for these
> values?

NaN or -1.

> Question 3:
> Is there any reason we should be using a LinkedList over an ArrayList
> for the AdjListGraph implementation? We have heard conflicting
> information.

LinkedList is a doubly-linked list, and so each element will have
forward and backward pointers (8 or 16 bytes depending on your
platform). ArrayList is a contiguous list in memory with amortized
insertion time, and no per-element pointers.

I'd go with the ArrayList as it uses less memory.

> Question 4:
> For maxst() and both recommendation systems we need the weights of the
> undirected graph. If two vertices each have edges pointing towards
> each other with different weights, what should we use for the weight
> of the edge: the sumation or the larger of the two?
>
> TLDR: if A--->B has weight 5 and B--->A has weight 4, is our
> undirected weight 5 or 9?

It says to use the sum, so 9.

> Question 5:
> For the 1.2 deliverables, we need to create charts for indegree and
> outdegree. What exactly should we put in these? What does it mean by
> "distribution"? Are we just outputting a range of indegrees/outdegrees
> for every vertex for the graphs given, or is it somethign else?

From looking at the graph, I should be able to tell how many vertices
have a given indegree. Notice that there is just one indegree graph, so
you should fit both Twitter and LiveJournal graphs on to this (no need
to show the small ones, just the large ones). Thus, each graph will
have two lines showing the way in which indegree is distributed across
vertices.

-Robert

[Alden Coots]

Q1: Is it acceptable if the culling of edges is inherent in our Max ST algorithm, making the whole process O(V^2) time?  No matter how you slice it we're gonna have to pick out the edges at some point, so why should it matter when?

2011/5/2 Robert Escriva <esc...@cs.cornell.edu>

[Nikos Karampatziakis]

Would a subsequent invocation of maxst be O(V^2) or O(E logV)?

-Nikos

[Joseph Manganelli]

@Nikos - The person who asked Question 1 said they have an ArrayList
of edges when they load the graph into the class. Isn't this
"condensed list" non-representative of a true adjacency matrix?

On May 2, 2:27 pm, Nikos Karampatziakis <n...@cs.cornell.edu> wrote:
> Would a subsequent invocation of maxst be O(V^2) or O(E logV)?
>
> -Nikos
>
>
>
>
>
>
>
> On Mon, May 2, 2011 at 2:16 PM, Alden Coots <i...@cornell.edu> wrote:
> > Q1: Is it acceptable if the culling of edges is inherent in our Max ST
> > algorithm, making the whole process O(V^2) time?  No matter how you slice it
> > we're gonna have to pick out the edges at some point, so why should it
> > matter when?
>

> > 2011/5/2 Robert Escriva <escr...@cs.cornell.edu>

[Alden Coots]

A subsequent invocation of maxst would be O(V^2) because the algorithm is reading the edges from the matrix each time.  I agree with Joseph, if we use our maxst algorithm to cull edges first and store them in a different data structure aren't we essentially changing the graph into something that more resembles an adjacency list?  Why even use a matrix if we're not really using it?

2011/5/2 Nikos Karampatziakis <n...@cs.cornell.edu>

[Nikos Karampatziakis]

On Mon, May 2, 2011 at 2:40 PM, Joseph Manganelli <jtm...@gmail.com> wrote:
> @Nikos - The person who asked Question 1 said they have an ArrayList
> of edges when they load the graph into the class. Isn't this
> "condensed list" non-representative of a true adjacency matrix?
>

I am not sure, what you mean by "non-representative". At some point,
in order to compute a MaxST, especially if you are doing Kruskal's
algorithm, you need to sort a list of edges.

-Nikos

[Nikos Karampatziakis]

I think an array/list of edges is slightly different from an adjacency list.

In any case I think we should wait and see what Robert or Steve had in
mind for this question.

-Nikos

[Joseph Manganelli]

Creating that condensed list can only be done in V^2 time (purely from
the matrix).

If the AdjMatrixClass class already computed this "condensed
list" (from loading the file), alongside the 2d array, then MST would
only use the condensed list which would take E(Log(V)).

I don't see how O(E(Log(V))) could possible represent MST if the
algorithm ONLY uses the 2d array, which I though was the purpose...

[Robert]

This isn't really related to the current discussion, but it's a corner
case I've been puzzled on.

If a vertex has an edge that connects it to itself, should that edge
add one to the vertex's indegree and outdegree?

[Nishant George]

In my implementation it does, if that helps any.

As such, I decremented k by 2 in the clustering function if I found that an edge connected to itself (indegree and outdegree each overcounted.)

Someone correct me if this interpretation is wrong, and indegree and outdegree should NOT count an edge that connects a vertex to itself?

--
Nishant George
Cornell University '11
Applied & Engineering Physics

[Robert Escriva]

I think that the original question 1 will be answered by the
clarification we are releasing on CMS. In short, as long as MaxST is
O(V^2) on AdjMatrix, and O(E log V) on AdjList, we will be happy.

You should probably not store max st between invocations as the graph
may change dramatically.

-Robert

[Robert Escriva]

Self-edges do affect in/out degree.

-Robert