Boston University Logo

CAS CS 132 Geometric Algorithms - Fall 2010

Course Info - Course Objectives - Course Materials - Grading Policy
Collaboration and Academic Integrity - Help - Course Schedule - Assignments - Links

Lectures: Tuesday, Thursday 11:00 am - 12:30 pm in PSY B39
Instructor: Prof. Margrit Betke
Teaching Fellow: Mike Breslav
Class web page:
Class mailing list:
Contact Information:

Staff Email Phone Office Hours Office
Margrit Betke betke @ 353-8919   Tue 2-3:30, Thu 3:30-5:00,
and by appointment  
MCS 286  
Mike Breslav breslav @ Please email. Tue 4-6 and Wed 2:45-3:45
and by appointment  
Undergrad CS Lab,
730 Commonwealth Ave  

Seeing Me in My Office:
Please feel free to stop by my office anytime. My office is in MCS 286 (111 Cummington St). I am generally around every day, but often in meetings, so the best time to reach me is during office hours. You can also make an appointment by email. I'm happy to talk with you about the course, computer vision research, your plans for the future, or anything else. Check out my personal web page to get to know me a little.

Teaching Fellow Responsibilities:
Mike is responsible for leading the discussion sections, helping you out during his office hours, and grading the homework. Please email him if you have questions about your homework grades.

Course Objectives

Our goal is to learn how to design data structures and algorithms for geometric objects. We will discuss basic concepts of linear algebra, such as Cartesian geometry, transformations and their representation, and triangulations. You will learn tools for rigorous reasoning and analysis, advance your algorithmic maturity, and gain expertise in applying geometric algorithms to solve problems in computer vision, computer graphics, artificial intelligence, and pattern recognition.

Prerequisites: No prerequisites are required. Some exposure to programming and calculus are recommended (e..g, CAS CS 111 and CAS MA 123).

Course Materials

Handouts: The updated course syllabus and most handouts are made available online. Check our course web page at least once a week for homework assignments and other information.

Textbook: Introduction to Linear Algebra by Gilbert Strang. Fourth Edition. (February 2009) ISBN 978-09802327-14. If you are concerned about the book's price, you may use the book I will place on reserve in the Science Library.

Computing Environment: You will use MATLAB as your programming environment. We will assume that you have no prior knowledge of MATLAB. MATLAB is installed on the computers in the Computer Science Department's Undergraduate Lab located at 730 Commonwealth Ave, 2nd floor. Bring your BU ID to the Lab to get an account (see website for Lab hours). Your account will give you access to the Computer Science Department's servers csa2 and csa3 to submit your homework solutions. You can access the servers remotely using scp and ssh. We recommend that you work on Windows and Linux platforms in the Lab instead of working alone in your dorm room. In the lab, you have immediate access to tutors and computing staff, and, during his office hours, to Mike, our teaching fellow.

Grading Policy

Homework: The homework includes reading assignments, Matlab programming, and problem sets. The due dates are listed below. Programs and reports must be submitted electronically. Solutions to problem sets must be submitted in class. They can be hand-written. Make sure they look professional with a title page and a large margin for grading comments. Guidelines for submission are provided with each assignment. Late solutions will be levied a late penalty of 20% per business day (up to three days). After three days, no credit will be given.

Class Participation: Come to class and participate regularly. Reading the textbook and listening in class will only give you a "passive understanding" of the material. I encourage discussions in class to help you acquire an "active understanding" of the material so that you can evaluate existing geometric techniques critically and develop your own creative solutions. I may give a short (announced) quiz so that shy students have a chance to discuss a topic in written form.

Exams: There will be two exams, a mid-term and a final exam. The mid-term exam will be held in class on October 14, 2010. The final exam grade will be computed as follows: adjusted final-exam grade = max { mid-term grade + final-exam grade, 2 * final-exam grade }. This way, if you have trouble with the mid-term exam, you can still pass the course with a good final grade. To prepare for the exams, come to class, participate in our discussions, and keep up with homework assignments.

Final Grades: Your final grade will be determined as follows:

Collaboration and Academic Integrity

You are encouraged to collaborate on the solution of the homework. If you do, you must code up your solutions on your own and acknowledge your collaborators. Each student must submit his or her own electronic version of the solutions. You can request an exception to this rule for your final project. If you use algorithms or code that are not your own original work and that were not provided in class or discussed in the textbook, you must give a detailed acknowledgment of your source .

Cheating and plagiarism are not worthy of Boston University students. I expect you to abide by the rule stated above and the standards of academic honesty and computer ethics policy described in and


Geometric Algorithms is a background course that will introduce material needed in many interesting areas of computer science. It should be fun and not too much of a struggle for you. Depending on your level of mathematics background, the course may be challenging for you. If you do not understand the material, ask for help immediately. Ask questions in class. If one student is confused about something, others may also be confused and grateful that someone asked. Come and see me or Mike for help or send us email. Our task is to help you learn a very interesting topic!

You may also ask help from graduate students who are tutors in the undergraduate laboratory. Many of them have expertise in geometric algorithms. The names of tutors and their hours are listed on the Tutoring Schedule.

Course Schedule


Assignments and solutions are posted here:

Problem Set 1, due in class on Thursday, September 16, 2010. Graded and solutions handed back, September 30, 2010.

Programming Assignment 1, due by electronic submission on Wednesday evening, September 22, 2010.

Problem Set 2, due in class on Thursday, September 30, 2010.

Programming Assignment 2, due by electronic submission on Wednesday evening, October 6, 2010.

Problem Set 3. Assigned October 6. Your solutions will NOT be collected and graded. Please bring your solutions to the discussion section on TUESDAY, October 12, (Monday schedule due to Columbus Day), and any questions you may have about the problem set.

Problem Set 4, due in class on Thursday, October 28, 2010.

Programming Assignment 3, due by electronic submission on Wednesday evening, November 3, 2010.

Problem Set 5, due in class on Thursday, November 11, 2010.

Problem Set 6, due in class on Thursday, November 18, 2010.

Problem Set 7, due in class on Tuesday, November 23, 2010.

Programming Assignment 4, due by electronic submission on Wednesday evening, December 8, 2010.

Student Results

Student Results Student Grades


List of potential carrier opportunities where your knowledge of geometric algorithms would be important.

Image of Research Results
Margrit Betke, Associate Professor
Computer Science Department
Boston University
111 Cummington Street, Rm MCS 286
Boston, MA 02215 ( campus map )
Email: betke @
Phone: 617-353-8919 (or 6412)
Fax: 617-353-6457
Last updated: Wednesday, November 25, 2010
Valid CSS!
Valid HTML 4.01 Transitional