Do u know where i can get some past exam paper for
this course? And can u tell me how many questions will
be on the exam?

Answer:

I dont know where you can find past exams for the course.  As far as
how many questions, well i couldn't tell you that because i don't know yet!

Question:

will there be any induction type questions??

Answer:

There may be induction type questions.  You are responsible for any material covered in the course.

> Actually i have heard that the prof. from the other section
> is preparing the final exam for 2011 and i believe they spent almost 4 weeks
> on graphs and implementing them.
> So i was wondering how much time do i have to spend on graphs and do we have
> to know complete implementations of graphs.
> Also i really appreciate it if you put the list of the chapters that we have
> to study for the final exam and what is the percentage of each chapter in
> the final exam.

Instructors from all sections will write the exam.  Yes, the other section
did cover directed graphs however we did not (section 12.4).  You are not
responsible for section 12.4 as stated in the link provided from the web
page.  The list of sections you are responsible for the final is
available from a link on the section N web page.  As far as the percentage
of each chapter on the final, I do not know.

>  Could you please tell me which part of chapter 12 will be in the
> final exam. Only 12.1 to 12.3 are covered in the lectures, so only 12.1 -
> 12.3 would be in the final?

Answer:

Actually, 12.2 was also covered.  So as far as chapter 12 goes,, you are responsible for sections 12.1, 12.2 and 12.3.

> I've got a question for the final exam. If I need to write methods in
> pseudocode, I wonder the precondition, postcondition, input and output of
> the method would be given or I've got to  write by myself?

Answer:

You should be prepared to provide this yourself however, there may
be cases where the input for example is given. e.g. as in the midterm, the method signature provided the input arguments.

> Can you add more office hours?

Answer:

Yes, additional office hours have been added:

Monday May 21 2001 - 12:00pm - 2:00pm if CCB is opened.
Tuesday May 22 2001 office hours will be extended from 11:30am - 1:30pm.
Depending on demand, more hours may be added!
Meet at CCB 21 (regular office) and if necessary, we could find an empty room.

Questions below posted Monday, May 21 2001

Question: (this one consists of three parts)

> some questions for the pseudo code of "Implementation of a
> simple graph with an adjacency list".
>
> 1. What type should the "pointers" be as an instence variable of the edge
> object?

Answer:

These pointers "point" to lists of edges.  if this is an undirected edges,
then this edge will have pointers to to I_un of vertex1 and of vertex2.
Take a look at the edge insertion methods.

Question:

> 2. In the "insertEdge(first, second, element)", it says "and pointers to
> Iun of first and second".  But in "makeUndirected(edge)", it says "remove
> pointer to edge in Iout of origin".
> So, I'm confused by these statements. I wanna know the pointer points to
> either the container I which contains the edges, or to the exact edge in
> the container I.

Answer:

It points to the container.  When inserting an undirected edge, you have
the pointers point to I_un of the each vertex.  When the edge is directed
however, you set the pointers to either I_out, I_in accordingle.  When
making a directed edge into an undirected edge, we dont need the pointers
to I_in,I_out but rather, we need a pointer to I_un.

Question:

> 3.  In the "areAdjacent(first, second)", I think we should use a while
> loop instead of the for loop in order to get a "true" found.
>

Answer:

You can do it with a while loop however, the for loop used in the pseudo
code is still correct.  Recall that in each iteration you have an "or"
statement with "found" as one of the two arguments.  When "found" is set
to true, then since it is one of the arguiments of the "or" statement,
found will always be true.

> 1. You said that if m < n-1 then G is not connected.....

Yes. This is true.

> 2. So if the graph is connected, then m >= n-1

Yes.  This is a slo true.

> I think this property only works for non-cycle graph(forest) right??
>

Well, you can still have a connected graph that is connected and not a
forest.  So this property doesn not apply for forests only.

> According to the pesudocode for EDGE LIST
>
> UndirectedEdges(), goes through each edges and detects each edges is
> directed or not by
> checking the instance variable "directed" for each edges....
>
> Here is his code:
>
> col <- empty collection
> for each edge in edges  do
>     if edge is not directed then
>         add edge to col
>
>
> However, I remember that you define a graph is undirected iff (a,b) -> (b,a)
>

Answer:

The method UndirectedEdges() simply returns a "collection" (all) the
undirected edges of a graph.  Recall, that a graph may have directed and
undirected edges e.g. "mixed graph".  This method simply returns all the
Undirected edge objects.  Since edges can be directed or undirected, the
edge object (position) contains a boolean variable (directed) to let us
know whether the edge is directed or undirected.

A graph is undirected only if all edges are undirected, it is directed
only if all edges are directed and when it contains both directed and
undirected edges it is a mixed graph. (see definition in the text book).

Questions below posted Tuesday May 22 2001

Question:

> would you please give me a hint how to proof that the run time for
> findAllElements or removeAllElements of a binary search tree is O(h +
> s), which h is height and s is the size of the iterator.

Answer:

I beleive this is one of the exercises (C-9.1)?  In any case, it involves
modifying the original akgorithm.  Well if you have more than one element
with the same key ("k"), why not simply have one node in the binary search
tree with the key and simply keep a collection (list, vector etc.) in this node of all
keys with value "k".  Now, when you want to
retreive an element with key "k", you traverse the tree to find the node
with key "k" (this takes O(h) and then obtain the collection and search
through it to find the particular element (this takes O(s) - hence you
have O(h + s) ).

Question:

> What's the exact time and location for tomorrow's (May 22)  review class?

Answer:

11:30am CCB 210 (e.g. as regular office hours).  From there we will find a
room (hopefully!).  Also, in case anyone is late I will post a note at
CCB210 letting people know what room we are in.

Questions below posted Tuesday May 23 2001

Question:

> Suppose we have
> pre: 0,1,3,4,7,8,2,5,9,6
> pose: 3,7,8,4,1,9,5,6,2,0
>
>                                 The graph looks like this
>
>                                                         0
>                                         1                                2
>                             3                4                    5
> 6
>                                         7        8            9
>
>
> Then we asked to draw the tree....Do we have formula or any techniques to do
> this kind of question??

Answer:

Not sure what you mean by pre and post - that applies to trees.  Do you
mean given the sequence of vertices visited by DFS and BFS?  Well if so,
that would be very difficult as when performing DFS and BFS we arbitrarily
pick an edge to traverse.

Question:

> if I was not able to attend the exam for COSC 2011 tomorrow
> when can I write the exam and are you still going to have office hours after
> the exam.

Answer:

You will have to go to the registrars office before the exam to pick up
and fill out a "Deferral Agreement" form.  This form will have to be
signed by Professor van Breugel before the exam.  You will then be able to
re-write the exam during the summer examination period.  If you do not
have this form completed and you do not write the exam, there will be no
re-make exam - you will have to petition etc. (e.g. go through university
procedures).