An introduction to the design of computer algorithms, including basic data structures, analysis of algorithms, and establishing correctness of programs. Overview of topics in computer science.

GENERAL INFORMATION


Instructor:

Teaching Assistants:

Tutors:

Lectures:

Office hours:

Prof. Mathieu BlanchetteThursday 10-12 (*)ENGTR 3107
Prof. Jérôme WaldispühlWednesday 12:35-2:25 (*)ENGTR 3106
Airin Ahia-TabibiTuesday 3:30-5:00ENGTR 3110
Faizy AhsanWednesday 3:30-5:00ENGTR 3110
Mohammed AlshamraniOnline!
Omar AsadMonday 10:30-12:00MC 102
Alexander ButyaevTuesday 11:00-12:30ENGTR 3110
Christopher CameronFriday 10:00-11:30ENGTR 3110
Victor ChenalThursday 10:00-11:30ENGTR 3110
Willie ChangTuesday 1:10-2:10ENGTR 3110
Zheng DaiMonday 9:00-10:30ENGTR 3110
Alexandre ParmentierWednesday 10:30-11:30ENGTR 3110
Vladimir ReinharzTBA
(*) Office hours will be held during the weeks the instructor is teaching (See schedule) and the week before the exams.

Course Webpage: http://www.cs.mcgill.ca/~jeromew/comp250.html

Course Material:
All the material needed for this class will be available on the public course web page. There is one required textbook (free):

We also recommend the following textbooks: Lecture slides will be made available in PDF form on the course web page. Lectures will be recorded and available on MyCourse.

Discussion Board:
The official discussion board for this class is available at https://cs250qanda.cs.mcgill.ca/. You can automatically login into this forum using your SOCS login and password. If you do not have a SOCS account, you can create one at https://newuser.cs.mcgill.ca/ from any computer in the mcgill network.

Evaluation
Your final grade will be calculated as follows:

The exams are closed book, but you will be allowed 2 pages of notes at the final exam. No electronic devices will be allowed (this includes noise-cancelling headphones).
A bonus of 1% of the final grade will be given to the best contributor to the online forum.

ANNOUNCES


Release DateDue DateAnnounce
Nov 20Dec 7 at 23:59pmAssignment 6 is now released. Do not forget to follow carefully the guidelines. There is no programming involved, so you must submit a single PDF file. No late submission will be accepted.
Nov 15Fill our survey and vote for the special topics you would like to cover during the last lectures
Nov 14Dec 7 at 23:59pmAssignment 5 is now released. Do not forget to follow carefully the guidelines. No late submission will be accepted. For this assignment you have two choices: a searchEngine programming project, or a Sudoku solver programming project. You should submit the solution for only one of the two, in the appropriate submission box on MyCourses.
Oct 27Nov 11 at 23:59pmAssignment 4 is now released. Do not forget to follow carefully the guidelines. No late submission will be accepted.
Oct 27Faizy Ahsan has updated Office hours (Wednesday 3:30-5).
Oct 27The solutions of the midterm will be presented in class on Nov. 2nd, 2014.
Oct 17Oct 22 The exam:
Date: October 22nd, 18:00 - 19:30
Location: What to bring:
  • The exam is a multiple choice exam, with a Scantron answer sheet. You must bring with you a couple of lead pencils. Pens will not work. We will not have pencils to lend you.
  • You are allowed a single double-sided 8” x 11” piece of paper as notes. No other documents will be accepted.
Preparing for the exam:
Oct 16There will be 2 review sessions on Monday Oct. 19 and Tuesday Oct. 20 from 12:30 to 1:30 in TR3120.
Oct 16A practice mid-term exam is now available
Oct 15Let us know what you would like to review for the midterm on Oct 21, and give us your feedback on the lectures so far. Start to fill the online survey. All answers are anonymous.
Oct 14Jérôme Waldispühl will have his office hours only until 1pm today.
Oct 10Oct 25 at 23:59pmAssignment 3 is now released. Do not forget to follow carefully the guidelines!
Oct 6The office hours of Willie Chang are cancelled this Tuesday.
Sep 26Oct 9 at 23:59pmAssignment 2 is now released. For this assignment, you must use the Java template file HW2.java. The file HW2_full_output.txt contains a sample output of the solution. Do not forget to follow carefully the guidelines!
Sep 14Sep 23 at 23:59pmAssignment 1 is now released. Do not forget to follow carefully the guidelines!
Sep 9There will be two Eclipse tutorial by A. Butyaev at 4pm on Sep 9 and 10 in Trottier building room 3120. The Eclipse software is a workspace for programming in Java. We highly encourage you to attend this optional session if you are not confortable in programming in Java.
Sep 4Welcome to COMP250!

SCHEDULE


DateTopicMaterialInstructor
Lecture 1Sep 4Syllabus. What is an algorithm? Language for describing algorithms. Algorithm vs implementation.Lecture notesProf. Blanchette & Waldispühl
Lecture 2Sep 9Example of intersection of student lists. What can be gained by a good algorithm? Notion of data structure. Tools for analyzing the running of an algorithm.Lecture notesProf. Blanchette
TutorialSep 9, 4-5pm in ENGTR 3120Special Eclipse tutorial
The Eclipse software is a workspace for programming in Java. We highly encourage you to attend this optional session if you are not confortable in programming in Java.
SlidesA. Butyaev
TutorialSep 10, 4-5pm in ENGTR 3120Special Eclipse tutorial
Second version of the tutorial of Sep. 9.
SlidesA. Butyaev
Lecture 3Sep 11Basics of java: Compilation, Programming style, Variables, Primitive types, Conditionals Input/OutputLecture notes I and Lecture notes II
[D2012], chapters 1 - 6
Eclipse tutorial (by Alex Butyaev)
Prof. Blanchette
Lecture 4Sep 14Loops, Arrays, and Strings.Lecture notes
[D2012], Chapters 7-11.
Assignment 1 is now released (Due on Sep 23).
Prof. Blanchette
Lecture 5Sep 16Object-Oriented Programming in Java Lecture notes
[D2012], Chapters 7-11, Sections 12-16
Prof. Blanchette
Lecture 6Sep 18Thinking Recursively: ExamplesLecture notes
[CH2014] Chapter 7
Prof. Waldispühl
Lecture 7Sep 21More Recursion examples. Merge sortLecture notes
[CH2014] Chapter 9
Prof. Waldispühl
Lecture 8Sep 23Proofs by inductionLecture notes
For more examples, see "Discrete Mathematics and its applications" by Kenneth Rosen, available on reserve at the library.
Prof. Waldispühl
Lecture 9Sep 25Loop invariantsLecture notesProf. Waldispühl
Lecture 10Sep 28Running TimeLecture notes
[CH2014] Chapter 4
Assignment 2 is now released (Due on Oct 9).
Prof. Blanchette
Lecture 11Sep 30Big O definitionsLecture notes
[CH2014] Chapter 4
Examples
Prof. Blanchette
Lecture 12Oct 2Big O examples non-recursiveLecture notes
[CH2014] Chapter 4
Prof. Blanchette
Lecture 13Oct 5Running Time and RecursionLecture notes
[GT2009] Section 5.2
Prof. Blanchette
Lecture 14Oct 7QuickSort. In-place sortingLecture notes
[CH2014] Chapter 9
Prof. Blanchette
Lecture 15Oct 9Introduction to ADTs (part I)Lecture notes
Java Source code: Node.java, LinkedList.java, TestList.java
[CH2014] Chapter 14
Assignment 3 is now released (Due on Oct 25)
Prof. Waldispühl
Lecture 16Oct 14Introduction to ADTs (part II)Lecture notesProf. Waldispühl
Lecture 17Oct 16ADTs: Stacks Lecture notes
[CH2014] Chapter 5 and 6
Fill the online survey!
Prof. Waldispühl
Lecture 18Oct 19ADTs: Queues and dequesLecture notes
[CH2014] Chapter 5 and 6
Prof. Waldispühl
Lecture 19Oct 21Review sessionLecture notes.
Previous midterm exams are available here: http://www.cs.mcgill.ca/~blanchem/250/practice_midterms.html. In addition, you can also access a set of additional questions. Note however that unlike these past exams, ours will be multiple choice.
Prof. Waldispühl
Mid-term ExamOct 22, 6-7:30pm in MNI TIMMINSTextbook and electronic devices are not allowed.
Lecture 20Oct 23ADTs: TreesLecture notes
[CH2014] Chapter 5 and 6
Prof. Waldispühl
Lecture 21Oct 26ADTs: Binary Search TreesLecture notes
[CH2014] Chapter 25
Prof. Waldispühl
Lecture 22Oct 28ADTs: Heaps Lecture notes
[CH2014] Chapter 26
Assignment 4 has been released
Prof. Waldispühl
Lecture 23Oct 30ADTs: Hash Tables Lecture notes
[CH2014] Chapter 21 & 22
Prof. Waldispühl
Lecture 24Nov 2Review of the midterm examProf. Blanchette
Lecture 25Nov 4ADTs: GraphsLecture notes
[CH2014] Chapter 28 & 29
Prof. Blanchette
Lecture 26Nov 6Graph algorithms: Breadth-first search (BFS) and depth-first search (DFS) Lecture notes
[CH2014] Chapter 28 & 29
Prof. Blanchette
Lecture 27Nov 9Survey of graph problemsLecture notes
[CH2014] Chapter 28 & 29
Prof. Blanchette
Lecture 28Nov 11Web search engineLecture notesProf. Blanchette
Lecture 29Nov 13Computers playing gamesLecture notesProf. Blanchette
Lecture 30Nov 16Introduction to dynamic programming and greedy algorithmsLecture notes
Assignment 5 is now released and due on Dec 7 at 23:59
Prof. Blanchette
Lecture 31Nov 18Greedy algorithms and fastest descentLecture notesProf. Blanchette
Lecture 32Nov 20CryptographyLecture notes
Assignment 6 is now released and due on Dec 7 at 23:59
Prof. Blanchette
Lecture 33Nov 23Text compressionLecture notesProf. Waldispühl
Lecture 34Nov 25BioinformaticsLecture notesProf. Waldispühl
Lecture 35Nov 27Human-computingLecture notesProf. Waldispühl
Lecture 36Nov 30Machine LearningLecture notesProf. Waldispühl
Lecture 37Dec 2Computer GraphicsLecture notesProf. Waldispühl
Lecture 38Dec 4Review part IProf. Blanchette
Lecture 39Dec 7Review part IIProf. Blanchette

RULES & POLICIES


Prerequisites
Familiarity with a high level programming language and CEGEP level mathematics. Computer Science Major and Honours students are advised to take MATH 240 simultaneously with COMP 250 or with COMP 251. Although it not a prerequisite either, COMP 202 will provide you a solid background for programming in Java.

Policy on discussion Board
We will use a new forum system available at: https://cs250qanda.cs.mcgill.ca/ (i.e. we will not use the forum in MyCourse).
You will be automatically registered in this forum and will have the possibility to vote for the most useful questions and answers. Students with the most voted questions and answers (after validation by a moderator) will receive bonus points.
Please follow common sense rules and etiquette for discussion board postings: be polite, avoid texting shorthand ("ur" instead of "you are", ...), choose a suitable subject line for your posting and use multiple postings for multiple subjects, keep your postings brief, etc.

Policy on collaborations
We greatly encourage you to discuss the assignment problems with each other. However, these discussions should not so far that you are sharing code or giving away the answer. A rule of thumb is that your discussions should considered public in the sense that anything you share with a friend should be sharable with any student in the class. We ask you to indicate on your assignments the names of the persons with who you collaborated or discussed your assignments (including the TA’s and instructors).

Policy on re-grading
If you wish us to re-grade a question on an exam (or assignment), we will do so. However, to avoid grade ratcheting, we reserve us the right to re-grade other questions on your exam as well.

Policy on final grades
I will use the same rules and formula for calculating the final grade for everyone. We understand that your performances may be influenced by many factors, possibly out of your control. However, that is the only way we can be fair. The only exceptions will be medical exceptions. In that case, I will require a medical note, which has to be also reported to McGill, and to be informed as early as possible. Failure to comply to these rules, may results in the impossibility to invoke a medical exception.

Policy on Assignments
Due date/time, location/mode for returning your solutions, and accepted formats will be announced in class and indicated on the course web page.
Failure to return your assignment in time will results in penalties or even absence of grading. Late submission of 24h or less will receive a penalty of 20%. In all other cases, your assignment will be refused and not graded.
Importantly, solutions that do not follow the requested format will receive a penalty. By default, we only accept PDF or TEXT files. Images (if any) must be embedded in a PDF. Do not compress your files. All files must open on LINUX SOCS workstations.
The quality of the presentation of your solution is very important. Unreadable material, cryptic notations, or bad organization of the material will results in penalties, and potentialy even an absence of grading. If you scan your hand-written solutions, it is your responsability to ensure that you submit a high-quality image (i.e. excellent luminosity, contrast, focus and resolution). The clarity of your explanations will also be an integral part of your final grade.

Policy on programming code
Questions in assignments may require you to write a Java program. We will provide, as much as possible, input and output data to test your programs. However, it will be your duty to ensure that your Java files compile on LINUX SOCS workstations. We will not grade programs that do not compile on these machines.
Submission of class files (instead of Java source files) will be considered as an absence of submission. Do not compress your files.

Use of French in assignments and exams
In accordance with McGill University’s Charter of Students’ Rights, students in this course have the right to submit in English or in French any written work that is to be graded.

McGill policies
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 this link for more information.

CONTACT


If you have any additional question, you can contact the instructors:

Mathieu Blanchette
3630 University Street, Room 3105, Montreal QC H3A 0C6
(E-mail) blanchem@cs.mcgill.ca
(Phone) +1 514 398 5209

Jérôme Waldispühl
3630 University Street, Room 3106, Montreal QC H3A 0C6
(E-mail) jerome.waldispuhl@mcgill.ca
(Phone) +1 514 398 5018

Based on a template from BlackTie.co