October 30:
Question: I just wonder what format of output of linked list you
expect. The
way I did is
0 ->1 ->5
Answer: My intention was that the format of the output for the list
version
would be in matrix format (exactly the same as the matrix version.) As
below:
1 ->0 ->2 ->4
2 ->1 ->4
3 ->4
4 ->3 ->1 ->5 ->2
5 ->0 ->4
0 1 2 3 4 5
Since it was assumed and not stated in the assignment other different
formats will be
accommodated.
0 0 1 0 0 0 1
1 1 0 1 0 1 0
2 0 1 0 0 1 0
3 0 0 0 0 1 0
4 0 1 1 1 0 1
5 1 0 0 0 1 0
October 29:
Question: What do I do if there is an course not adjacent to any other
courses, so I have no chance to add it to the vertexlist struct.
Answer: You may assume the input is such that the situation that you
describe does
not happen. This would be an example of a student who takes a single
course. There is no need to add this course to the graph and involve it
in colouring since for this student taking just this course it can not
conflict with any other course. (This course may create a conflict for
another student but for that other student the course would have been
entered as one of a pair of adjacent courses.)
October 28:
Prof. Rosenthal has started a parallel question and answers page. Check
it periodically for answers to your questions.
October 28:
Question: Do we have to worry about memory leaks?
Answer:
If you mean whether you need to free dynamically allocated memory when it
is no longer needed, the answer is no.
October 28:
Question:
Do we have to implement a seperate struct that is an array of struct
vertex? Kind of confused with what he means with implemented as an
array of vertex structs.
Answer:
You need an array of
VERTEX.
That array of VERTEX
is what you are using to store your list of vertices in vertexlist.c.
It should be implemented
accordance with the desired OOPinC style.
October 28:
Question: When we sort the vertex list, does the index of the vertex
change? I
dont
think it should because there is no function that would allow us to do
that in vertex.h.
Answer: By 'index', if you mean the position of the vertex within the
array,
that
should change (unless the list was already in sorted order). If you mean
the
index
field in the struct (see vertex.c), that should not change.
October 28:
Prof. Cheng from Scarborough has an
example
that
illustrates how to write C code in an OO style. It may clarify some of
your questions about the starter code. You should use a similar style if
you add additional structs.
October 28:
When the array of vertices is
sorted, the adjacency lists are not modified. Since the adj lists use the
original vertex numbers (before sorting), therefore we need the original
index numbers in the vertex struct (for checking adjacencies).
October 28:
Question: Why does the emalloc function return a char* pointer? Why char*
and
not void* ?
Answer (as per Prof. Rosenthal): I guess
it should have returned void*, sorry, but it works as is.
October 28:
Question: For adjnode.c, are we suppose to use the course code or the
index (ie. 0,
1,
2 etc) for the label of the adjnode? Or either would be alright?
Answer:
(Either would work, but it seems
index makes things easier.) To have the code for your new implementation
of adjacencylist.c agree with our old implementation it was intended that
you store the index.
October 28:
Question:
Concerning the
sortVerticesByDegree() and the sortVerticesByColor() functions in the
vertexlist.c file, are we allowed to use any reasonable sorting
algorithim that we choose or are you looking for something more specific
or maybe something with more restriction.
Answer:
Any sorting algorithm that's O(n^2) or better is fine (where n is the
number of items to be sorted). (I actually used a selection sort in my
solution. If you are looking for a challenge maybe you want to try a
heapsort or quicksort. You may have talked about heaps in the quadrature
section the numerical lectures and we may see it again in the simulation
lectures.)
October 28:
Question: I would like to
know
why the addVertex() function in the vertexlist.h file has a return type
of int
(as opposed to void) when all that is being done is adding a vertex.
Answer: The addVertex function returns the index of the vertex in the
vertex list. You need the index of the vertex in the vertex list to add
the adjacency to the adjacency data structure (either matrix or lists.)
October 28:
The Rosen algorithm is here.
October 25:
Question: I just want to confirm that we are supposed to create
vertexlist.c from
scratch. Right?
Answer:
Yes that is the intention. You are provided the vertexlist.h file and
the vertex.h and vertex.c files.