COMP-507A Computational Geometry

"The beginning of wisdom is the definition of terms." - Socrates

Hints on How to Pass this Course Smiling

  1. Welcome!

  2. 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.

  3. No Programming Assignments (but):

  4. 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.

  5. Algorithms for Humans:

  6. 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.

  7. Correctness of Algorithms:

  8. 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.

  9. Induction Proofs:

  10. 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.

  11. Course Web Page:

  12. Students should consult the course web page regularly. It can be found at: This page contains several sections which we will now describe.

  13. In-Class Exams:

  14. 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.

  15. Assignments:

  16. 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.

  17. Teaching Assistants:

  18. 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.

  19. Enjoy the Course!

  20. 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