COMP 251 HOME PAGE
Data Structures and Algorithms
Autumn 2013

E-mail addresses: prakash@cs.mcgill.ca and gheorghe.comanici@mail.mcgill.ca

Announcements

Announcements about the course will be posted here. Long handouts will be in pdf format.

• The mid term examination will be on the 17th of October.
• The mid term examination will be in rooms McDonald-Harrington G-10 and Leacock 219 . If your last name begins with A-O please go to McDonald-Harrington G10. If your last name begins with P-Z please go to 219 Leacock.
• Here is last year's mid-term exam with solutions if you would like to practice.
• Instructors' office hours will begin on 3rd Sept. TAs' office hours will begin on 9th Sept.
• You can access the textbook Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein using free access to the ebook via the McGill Library system.
  Here is the message from the library: For the e-book, Introduction to Algorithms by Cormen et al. (MIT Press) 2nd edition. Here is the catalogue link.
  It comes from an e-book provider, books24x7 which requires one to register an account in order to open its e-books. You need to enter your McGill e-mail
  and then you will receive the password in your McGill email. After that, you could login this book with your McGill email and the password received.

Course Information

• Lecture Times: Mondays, Wednesdays and Fridays 8:35 to 9:25
• Lecture Place: McConnell Engineering Building Room 304
• Panangaden's Office Hours: Mondays and Wednesdays 12 noon to 2pm
• Panangaden's Office: McConnell (North Wing) 105N
• Comanici's Office Hours: Mondays, Wednesdays and Fridays 9:30 to 10:30
• Comanici's Office: 111 McConnell Engineering

Course Outline and Lecture Schedule

• Outline of the Course , pdf version
• Schedule , pdf version.

Teaching Assistants

• Philip Bachman; Office hours: 2:00 - 3:30 Mondays and Wednesdays. Room 312 McConnell Engineering
• Mingzhou Yang; Office hours: 2:00 - 3:30 Tuesdays and Thursdays. Room 312 McConnell Engineering
• Maziar Gomrokchi; Office hours 3:30 to 5:00 Tuesdays and Thursdays, Room 110 McConnell Engineering (Hayden Quantum Information Lab).
• Tao Wei; 9:00 to 12:00 Thursday in Room 337 McConnell Engineering.

Framework and Instructions for Programming Questions

• Language: The programming language that will be used for the homework questions is Java. It is mandatory that code submissions follow the guidelines and are written in Java.
• Editor: In this class we will provide support for the Eclipse IDE. Although highly recommended, it is not mandatory to use Eclipse. Note that only basic knowledge of Eclipse is needed for this class. The following tutorials should be more than enough:
  a) Introduction to Eclipse.
  b) Debugging in Eclipse.
  
• Homework format: Each homework contains one programming question. For each such question we will provide an archive file on the course web-site. To illustrate we show you an example called Homework 0. This is not a homework that you have to turn in; it is just an example for you to test whether all the systems you need to use are set up. The archive file for HW0 is called HW0.zip. This file contains the following:
  • A JAR file containing all classes which you may need to use. It may be the case that your solution does not require all the classes that we have provided. (lib/HW0.jar)
  • The implementation that we have provided uses abstract classes. This is between an ordinary class and an interface. In an interface the methods are declared but not implemented. In an ordinary class the methods are declared and implemented. In an abstract class some methods are implemnted and some are just declared: the latter are called abstract methods. The Javadoc will say which methods are abstract and which are not. You have to implement all the abstract methds. Thus, for example, in Assignment 1, you have to implement heapify-up but you do not have to implement toString.
  • Javadoc (see details here) for all classes which you can or have to use. (HW0 Javadoc)
  • A Java file to be completed by student. This will either have to implement some Interface or extend an Abstract class. Please do not change the name of the class or the name of the package. (HelloWorldStudent.java)
  • Start working: In Eclipse, follow "File -> Import -> Existing Projects in Workspace -> Select Archive File -> Browse.." for HW0.zip.
  • In case you are not using Eclipse, you should still have all the necessary files in the archive.
  • Your submission: Only submit the Java file which you are required to complete. If you feel it is necessary to create additional classes, these should be included in the same source file. (HelloWorldStudent.java)

Assignments

Assignments and their solutions will be posted here. They will be either in pdf format or plain text. The programming part of the assignments should be submitted using the myCourses system. The theory questions should be submitted as hard copies and handed in at the beginning of the class on the due date.

• Assignment 1 is here. The due date is 20th September 2013.
• The solutions to the theory questions of Assignment 1 are here.
• Resources for programming question : HW1.zip and Javadoc
• Assignment 2 is here. The due date is 4th October 2013.
• Resources for programming question of HW2: HW2.zip and Javadoc
• The solutions to the theory questions of Assignment 2 are here.
• Assignment 3 is here. The due date is 21st October 2013.
• Resources for programming question of HW3: HW3.zip and Javadoc

Notes

Supplementary notes will be here.

• Slides on the stable matching problem prepared by Kevin Wayne of Princeton University.
• My handwritten notes on recurrences.
• My notes on amortized analysis.
• My handwritten notes on binomial heaps.
• Handwritten notes on union of binomial heaps plus the picture with all the pointers.
• Notes on 2-3 trees by Franklyn Turbak of Wellesley College. These excellent notes are posted here with the kind permission of Prof. Turbak.
• The invariant that must be maintained in a 2-3 tree, plus a few examples of 2-3 trees.
• Red-black trees handwritten and scanned.
• Red-black trees handwritten and scanned.
• Insertion and deletion cases for a red-black tree; handwritten and scanned.
• Notes on primality testing and RSA.

Academic Integrity

McGill University values academic integrity. Therefore all students must understand the meaning and consequences of cheating, plagiarism and other academic offenses under the Code of Student Conduct and Disciplinary Procedures ( see http://www/mcgill.ca/integrity for more information). Most importantly, work submitted for this course must represent your own efforts. Copying assignments or tests from any source, completely or partially, or allowing others to copy your work, will not be tolerated.