Mathematical tools (binary numbers, induction, recurrence relations, asymptotic complexity, establishing correctness of programs), Data structures (arrays, stacks, queues, linked lists, trees, binary trees, binary search trees, heaps, hash tables), Recursive and non-recursive algorithms (searching and sorting, tree and graph traversal). Abstract data types, inheritance. Selected topics.

GENERAL INFORMATION


Instructor:

Teaching Assistants:

Lectures:

Office hours:

Prof. Mathieu BlanchetteTuesday 9:30-11:00ENGTR 3107
Navin MordaniMonday 9:00-10:30ENGTR 3110
Hong Chuan GuoMonday 13:00-14:30ENGTR 3110
Yue WangTuesday 15:00-16:30ENGTR 3110
Caitrin ArmstrongFriday 13:30-15:00ENGTR 3110
Omar AsadWednesday 10:30 to 12:00MC 102
David Becerra RomeroWednesday 14:30 to 16:00ENGTR 3110
Zheng DaiThursday 10:00-11:30ENGTR 3110
Jeremy Georges-FilteauThursday 11:30-13:00ENGTR 3110
Faizy AhsanThursday 13:00-14:30ENGTR 3110
Christopher CameronFriday 10:30-12:00ENGTR 3110
Caitrin ArmstrongFriday 13:00-14:30ENGTR 3110

Course Webpage: http://www.cs.mcgill.ca/~blanchem/250

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

Discussion Board:
The official discussion board for this class is on MyCourses. 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.

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.

ANNOUNCEMENTS


Release DateDue DateAnnouncement
Jan 5Welcome to COMP250!
Jan 16Jan 30th, 23:59Assignment #1 is now available HERE
Jan 21COMP 250 Midterm exam:
When: Wednesday Feb 22nd, 6:00pm - 7:30pm

Where:
Last name starting with A to L: McIntyre room 522
Last name starting with M to Z: McIntyre room 504

What to bring:
0) A couple of pencils (not pen) to fill the scantron sheets
1) Your student ID card
2) A 1-page double side crib sheet (8.5 inches x 11 inches)
3) Your brain and energy!

Mathieu

SCHEDULE


DateTopicMaterial
Lecture 1Jan 5Syllabus. What is an algorithm? Language for describing algorithms. Algorithm vs implementation.Lecture notes
Lecture 2Jan 6Example 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 notes
Lecture 3Jan 10Basics of java: Compilation, Programming style, Variables, Primitive types, Conditionals, Loops, ArraysLecture notes
[D2012], chapters 1 - 6
Eclipse tutorial (by Alex Butyaev)
Lecture 4Jan 12MethodsLecture notes
[D2012], Chapters 7-11.
Lecture 5Jan 13Object-Oriented Programming in Java Lecture notes (same as previous lecture)
[D2012], Chapters 7-11, Sections 12-16
TutorialJan 13 16:00-17:00 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.
Slides
TutorialJan 16 16:00-17:00 in ENGTR 3120Special Eclipse tutorial
Second session of the tutorial.
Slides
Lecture 6Jan 17Iterative algorithms: Selection Sort, Insertion Sort, Bubble SortLecture notes by Prof. Michael Langer
[CH2014] Chapter 8
Lecture 6Jan 19Thinking Recursively: ExamplesLecture notes
[CH2014] Chapter 7
Lecture 7Jan 20More Recursion examples. Merge sortLecture notes
[CH2014] Chapter 9
Lecture 8Jan 24Proofs by induction - part ILecture notes
For more examples, see "Discrete Mathematics and its applications" by Kenneth Rosen, available on reserve at the library.
Lecture 8Jan 26Proofs by induction - part IILecture notes
For more examples, see "Discrete Mathematics and its applications" by Kenneth Rosen, available on reserve at the library.
Lecture 9Jan 27Loop invariantsLecture notes and addendum
Lecture 10Jan 31Running TimeLecture notes
[CH2014] Chapter 4
Lecture 11Feb 2Big O definitionsLecture notes
[CH2014] Chapter 4
Examples
Lecture 12Feb 3Big O examples non-recursiveLecture notes
[CH2014] Chapter 4
Lecture 13Feb 7Running Time and RecursionLecture notes
[GT2009] Section 5.2
Lecture 14Feb 9QuickSort. In-place sortingLecture notes
[CH2014] Chapter 9
Lecture 15Feb 10Introduction to ADTs: Lists Lecture notes
Java Source code: Node.java, LinkedList.java, TestList.java
[CH2014] Chapter 14
Lecture 16Feb 14ADTs: Lists implementation with linked listsLecture notes
Lecture 17Feb 16ADTs: Stacks Lecture notes
[CH2014] Chapter 5 and 6
Lecture 18Feb 17ADTs: Queues and dequesLecture notes
[CH2014] Chapter 5 and 6
Lecture 19Feb 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.
MIDTERM EXAMINATIONWednesday Feb 22 6:00 - 7:30pm, Textbooks and eletronic devices not allowed Where:
Last name starting with A to L: McIntyre room 522
Last name starting with M to Z: McIntyre room 504

What to bring:
0) A couple of pencils (not pen) to fill the scantron sheets
1) Your student ID card
2) A 1-page double side crib sheet (8.5 inches x 11 inches)
3) Your brain and energy!

Mathieu
Lecture 20Feb 23ADTs: TreesLecture notes
[CH2014] Chapter 5 and 6
Lecture 21Feb 24ADTs: Binary Search TreesLecture notes
[CH2014] Chapter 25
Lecture 22Mar 7ADTs: Heaps Lecture notes
[CH2014] Chapter 26
Lecture 23Mar 9LECTURE CANCELED
Lecture 23Mar 10ADTs: Hash Tables Lecture notes
[CH2014] Chapter 21 & 22
Lecture 24Mar 14Data structures in JavaLecture notes
Lecture 25Mar 16ADTs: GraphsLecture notes
[CH2014] Chapter 28 & 29
Lecture 26Mar 17Graph algorithms: Breadth-first search (BFS) and depth-first search (DFS) Lecture notes
[CH2014] Chapter 28 & 29
Lecture 27Mar 21Survey of graph problemsLecture notes
[CH2014] Chapter 28 & 29
Lecture 28Mar 23Web search engineLecture notes
Lecture 28Mar 24Binary numbersLecture notes not yet available
Lecture 29Mar 28Computers playing gamesLecture notes
Lecture 30Mar 30Introduction to dynamic programming and greedy algorithmsLecture notes
Lecture 31Mar 31Heuristics and fastest descentLecture notes
Lecture 32Apr 4CryptographyLecture notes
Lecture 33Apr 6Text compressionLecture notes
Lecture 37Apr 7Review session I
Lecture 38Apr 11Review session II

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 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 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 3107, Montreal QC H3A 0C6
(E-mail) blanchem@cs.mcgill.ca
(Phone) +1 514 398 5209

Based on a template from BlackTie.co