"The beginning of wisdom is the definition of terms." - Socrates
Hints on How to Pass this
Course Smiling
Welcome to Computer Science 308-507A: Computational Geometry.
This course is an introduction to the design and analysis of geometric
algorithms.
Below is a description of the main ingredients involved in taking this
course with hints for passing, enjoying and making the best out of it.
Please study it carefully.
This course is NOT a programming
course (despite the title of the text book) and there will not be
any programming homework assignments in C or
any other language. The course is instead concerned with the principles
behind
the design of efficient algorithms for solving a variety of different classes
of geometric problems. It is NOT concerned
with the details of implementing geometric algorithms on real computers
with real programming languages. Instead we will use idealized computers
(mathematical models of computers if you like) such as Toothpicks,
the
Ruler and Compass and the Real RAM (Random Access Machine
with real numbers as inputs) to measure the computational complexities
of our algorithms. We will also use idealized data structures to
study the algorithms and their memory requirements.
However, there is a Web project requirement
which
requires knowledge of HTML and Java
for the design of an applet. The emphasis here however is not
on programming but on designing and building a working
system. Hence finding free software on the web and putting it together
are not only allowed but encouraged. In fact it is suggested that no code
be written if is is already available somewhere. The idea is to do as little
programming as possible! However, you must clearly give credit where credit
is due, when using code written by others.
Although in this course we are concerned with designing algorithms
that are ultimately intended for machines to process, we are NOT
interested
in communicating with the machines but rather with each other. We are interested
in communicating with other humans about algorithms. Therefore we
will NOT use code in this course to
describe algorithms. Code was designed to be understood my machines not
humans. We will describe algorithms in a natural language such as English
and in the language of mathematics as has been done sucessfully and elegantly
for thousands of years. Furthermore mathematics should not be confused
with mathematical notation. The essence of mathematics lies in the precision
of concepts and not symbolic notation. Mathematical notation will be minimized.
Algorithms described in code will get a mark of
ZERO. Students using mathematical notation gratuitously will
be penalized. Mathematical notation should be used only when absolutely
necessary if it helps the reader. Remember that storage space is no longer
a problem and we need not save precious space at the cost of making things
difficult to read. In this course we will learn how to think and use English
(the international scientific language) in a precise way.
One of the most important properties of an algorithm is its correctness.
In fact this is so important that many people refuse to call a procedure
an algorithm if it is not guaranteed to give the correct solution. Many
"algorithms" inhabiting the computers in society at large are incorrect.
This can cause great cost and tragic suffering. For example, patients have
been killed by overdoses of radiation because of incorrect algorithms.
The American astronauts aboard the space shuttle Challenger were killed
because of an incorrect geometric algorithm used in rebuilding the booster
rockets. In fact a nuclear world war could be caused by an incorrect algorithm.
Therefore it is very important to design correct algorithms. Students often
have trouble proving the correctness of algorithms. This
course will emphasize proving the correctness of algorithms.
Students have the most trouble with induction proofs. In a very
important sense this is the most relevant method of proof for computer
scientists since it lies at the heart of recursion and divide and conquer,
two fundamental techniques for obtaining efficient algorithms. Therefore
this course will emphasize proofs by induction.
Students should consult the course web page regularly. It can be
found at: http://www-cgrl.cs.mcgill.ca/~godfried/teaching.html.
This page contains several sections which we will now describe.
This section of the course web page details the performance evaluation
of the students, the coordinates of the lecturer and teaching assistants,
the text book used in the course and similar logistics matters.
This web page contains the calendar of events for the course such
as the in-class exam and quizzes, the dates the practice assignments are
handed out and "due", and a very short title of each lecture. The bulletin
board at the beginning contains messages
from
me to you of important day to day events, matters related to the assignments,
etc and must be checked every week-day.
This web page contains a detailed list of topics covered in every
lecture. It contains the reading assignments made every week from the text
book, handouts and web material. It also contains suggested play. While
this section is not required, students are strongly encouraged to play
with the applets listed in this section. Students who do will be at an
advantage as it greatly facilitates learning the material in this course.
This page contains a skeletal outline of the course contents.
This page contains much of the material that we will cover in the
course that is not contained in the course text book (Joe
O'Rourke: Computational Geometry in C).
Many of the reading assignments will concern pages in this section. Here
you will also find alternate descriptions of material that is in the text
book. It sometimes helps students to learn when they read different explanations
of the same thing by different people. This web page also contains the
applets for the suggested play section of the assignments. Finally, this
web page serves as a library to satisfy your curiosity concerning material
directly relevant to the course. There is much more here than we will cover
in the course and I don't expect you to read it all. However, I
do suggest you browse through all of it and read what you find most interesting.
This page contains (by year) a list of student projects with links
to their web pages. Your project will be added to this list at the end
of the term. Please browse through the projects and play with the applets.
This will give you a good idea of what standards are expected of you for
your own project.
There are two in-class 75-minute exams
during the course (after 4 and 9 weeks approximately). They
are closed book. However, I am not
interested in measuring your memory. Computers are much better than we
humans at that. The test will measure your ability to think creatively.
Students often ask: what material will be covered in the test? My answer
is always the same. I don't want to insult your intelligence by asking
you to regurgitate material we have covered in class or that has been assigned
reading. A machine can do that much better than we can, and I don't want
to treat you like machines lest I be labelled as machinist. I want to test
you on what machines cannot do (yet), and that is to generalize or apply
your knowledge to solve new problems in new contexts. Therefore the tests
will cover everything that we have NOT covered in the course.
The material I learned as a student in university concerning radios, cathode
ray tubes and transistors is useless to me now. Many of the things I teach
today did not exist ten years ago. However, the creative problem solving
techniques and critical thinking skills I learned as a student can be applied
to things other than transistors, such as the latest trends in computational
geometry. How can you do well on my tests? University is (still, thank
heaven) a place for discussing knowledge in a free and open atmosphere
and I encourage you to discuss all matters of the course with your class
mates. On the other hand the modern harsh reality dictates that university
is also a certification method for certain skills - hence the test. The
best way to study for the tests in my courses is to do the assignments
and exercises on your own. Only
personal discovery leads to true understanding. The text book by Joe
O'Rourke also contains many exercises at the end of each
chapter. Doing these exercises is an excellent way to learn the material.
There are practice assignments (not collected, not marked and not
counted). However, students may if they wish hand in their assignments
to the TA's for feedback. The TA will give tutorials on these as necessary.
Solutions will be handed out on the "due" dates. The exams will have some
questions that are similar to those on the practice assignments.
The TA's are responsible for marking the exams. If you have any
questions about how you were marked please go and see the TA. If you have
general questions about the course material please see them too. They are
there to help you.
If for some reason the TA's cannot help you please come and see
me. In any case please come by sometime to say hello and tell me how you
are doing in the course. I expect to see you more frequently early in the
term to discuss your course project and its progress. My
door is always wide open during my office hours.
Godfried Toussaint