COMP 360 Algorithm Design Techniques

Fall 2003-04


General Information


  • Instructor
  • Teaching Assistants
  • Time and Place
  • Tutorials
  • Overview
  • Prerequisites
  • Assessment
  • Academic Integrity
  • Graduation Requirements
  • Textbook
  • Attendance

    Read on .... or return to the COMP 360 home page.


    Instructor

  • Prof. Sue Whitesides
  • Telephone: 398-7080
  • Office: Room 303, McConnell Engineering Building
  • Office hours: Tues. Wed. Thurs. 9:30-10:30am
  • Email: sue@cs.mcgill.ca
  • Top


    Teaching Assistants

  • Maxime Descoteaux, mdesco@cim.mcgill.ca, 398-5606
  • Mark Mercer, jmerce1@cs.mcgill.ca, 106 McConnell, McGill extension: x0524
    Top


    Time and Place

  • Tues. and Thurs., 11:30am-1:00pm in room 103, Wilson Hall, through Thurs., Sept. 18; after that, we move to the new Trottier Building, room 2120.
  • First class meeting is Thurs. Sept. 4.
    Top


    Tutorials

  • The actual dates for tutorials will be announced in class and under the "announcements" menu on the course web page. Generally, these will be held every other week. (That is, homeworks will typically be due on Fridays at noon, and there will typically be tutorials on Tuesday and Wednesday of the weeks for which homework is due on Friday.) The location for the tutorials is: Stuart Biology Building, room S3/3 (S313). The time is 6:05-7:25pm.
  • Top

    Overview

    This course continues the work of COMP250 and COMP251. It presents a number of fundamental algorithms, their applications, and techniques for designing and evaluating them. It also studies the issue of recognizing and dealing with those problems that do not appear to have any efficient algorithmic solution.

    The approximate course contents are as follows: dynamic programming, greedy algorithms, a review of elementary graph algorithms including depth-first search and breadth-first search (it is assumed this is familiar material for COMP 360 students), the shortest path algorithms of Dijkstra, Bellman-Ford, and Floyd-Warshall, network flows and the Ford-Fulkerson method, a brief introduction to linear programming, problem formulation and transformation, an introduction to problems that appear to be computationally hard and how to recognize them (i.e., NP-completeness), and an introduction to dealing with such problems (e.g., randomized algorithms, fixed parameter tractability approaches, approximation algorithms).

    See the approximate schedule for more details.
    Top

    Pre-requisites

  • a grade of C or higher in course COMP-251;
    Also, since COMP-251 has MATH-240 as a prerequsite, it is expected that students will have already completed MATH-240 with a grade of C or higher.
    Top

    Assessment


    There will be two mid-term exams (Oct. 7 and Nov. 4) and a final exam. Your grade will be based on the following weighting of course work:
  • Homework 10% total for approximately 6 assignments, Mid-terms 20% each, Final exam 50% OR
  • Final exam 100%.
    The higher of the two resulting marks will be taken as your final mark.

    Homework assignments will count only minimally to the final grade. However, questions very similar to assignment questions will appear on the mid-term and final exams.

    Note: There will be no make-up midterms. The corresponding part of the final exam will be weighted more to compensate for any missing midterm mark (OR the final exam will count 100%, whichever gives the better grade).

    A detailed account of the process of converting a numerical mark to a McGill letter grade can be found here.

    Top


    Academic Integrity

    As members of the McGill community, we value the ideal of academic integrity, which basically means that we respect ourselves and each other as we go about our learning, teaching, and research. In particular, this means understanding what the rules for fair play in written work. In COMP-360, you are encouraged to learn from each other, to work on homework together, to consult the web if your curiosity leads you there. What is not ok is to present someone else's work as your own, to copy something from another person or another source without making it your own by understanding it and reformulating it in your own terms. Midterm and Final exams are closed book, closed notes, and consultation is not permitted. Your mind is your only resource. Make it a valuable one.
    Top


    Graduation Requirements

    For CS majors, COMP-360 is required for graduation and must passed with a C or better. If you are planning to graduate in 2003-04, please plan on satisfying this requirement the first time around.
    The course grade is based entirely on actual achievement as measured on course work. Personal situations such as job offers, desire to graduate earlier, avoid paying tuition an additional term, etc., are not taken into account in arriving at the course grade.
    There is no extra work that can be done to make up for a low mark. The course can be retaken in Winter term, 2003-04, when it will be offered again. A supplemental exam will be given in May 2004. The mark on the supplemental exam replaces the entire course grade. However, there are conditions (e.g., your course grade is below a C) for taking this exam, a sign-up procedure, and deadlines for signing up. See the Calendar 2003-2004 for details.
    Top


    Textbook

  • Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein (2nd edition)

    The first edition should also be okay to use, but chapter numbers and page numbers will be different, and some material covered in lecture may be missing. Guidance will be given for cross-referencing the two editions. Note that this is the same text that some sections of COMP-251 have used. From McGill machines, the textbook can be accessed online. It is one of the electronic books available in McGill's electronic library. See the list of available electronic books . In particular, see the text .
    Top


    Attendance

    You are expected to attend class. Information may be made available on the web for your convenience, but is not a substitute for class attendance. Should you miss a class, you are responsible for finding out what material or announcements you may have missed. The course is not structured for distance learning.
    Top