In Connection with the Exam
The order is not chronological. Instead, general questions regarding
the exam are listed first, and the rest are ordered according to
the sequence in which the topics are covered in the course.
- Will you hold a question session before the exam?
- I don't usually do that. I've done it occasionally, but there are usually
very few questions, and it's often difficult to find a good time for
it. It'll often end up being too early, so that students are not
prepared to ask the relevant questions. You are welcome to drop by
my office. I'm fairly available these days, so I suggest that you
just come by without an appointment, if you're at the university
anyway. If you're not, you're welcome to make an appointment via email.
In my experience, individual counceling works better than a question
session, and you're welcome to drop by more than once.
Naturally, I can also answer simple questions via email, but
more complicated questions often require a whiteboard. If I get questions
that might be relevant to others, I'll post the question and my answer
on this page, so that everyone gets the same information.
Finally, if a number of you would rather have a questions
session, let me know, and I'll be happy to arrange one.
- You have listed Section 2.2 in the curriculum, but you haven't
lectured on it, have you ?
- Yes and no. I didn't cover it in connection with Section 2.1,
but I have discussed implementation and representation questions
in later lecures. It's really just about being concrete regarding
what we mean when we talk about moving around in a partition of a
polygon in the algorithms we discuss. The advice is that we represent
all the abstract concepts of vertices, edges, and faces in terms of
objects. And if we want an efficient implementation, one must store
the edges leaving a vertex in an appropriate sorted order, and in
order to efficiently being able to go from faces to neighboring faces,
it's convenient to represent an undirected edge by two "twin" edges
going each their way. Based on this, one can use constant space in
each object to store pointers to neighboring entities of the various
types and implement most local operations in constant time.
I've talked about these issues in different lectures, but it not
something I consider interesting in the context of an oral exam
unless doubt arises regarding whether or not an algorithm can actually
be implemented in such a way that the stated time complexity is obtained.
There's nothing in the section that you wouldn't be able to figure out
and design yourself with your background in algorithms and data structures.
Last modified: Mon Jan 11 22:20:02 CET 2016
Kim Skak Larsen
(kslarsen@imada.sdu.dk)