Instructor:

• Prof. Mathieu Blanchette (mathieu.blanchette@mcgill.ca)

Teaching Assistants:

• Head TA (First contact person for all marking-related issues): Jeremy Georges-Filteau: jeremy DOT georges-filteau AT mail DOT mcgill DOT ca
• Faizy Ahsan: faizy DOT ahsan AT mail DOT mcgill DOT ca
• Hong Chuan Guo: hong DOT c DOT guo AT mail DOT mcgill DOT ca
• David Becerra Romero: david DOT becerra AT mail DOT mcgill DOT ca
• Christopher Cameron: christopher DOT cameron AT mail DOT mcgill DOT ca
• Navin Mordani: navin DOT mordani AT mail DOT mcgill DOT ca
• Caitrin Armstrong: caitrin DOT armstrong AT mail DOT mcgill DOT ca
• Zheng Dai: zheng DOT dai AT mail DOT mcgill DO ca
• Yue Wang: yue DOT wang8 AT mail DOT mcgill DOT ca
• Omar Asad: omar DOT asad AT mail DOT mcgill DOT ca

Lectures:

• Tuesday, 8:30 - 9:30, STBIO S1/4.
• Thursday, 8:30 - 9:30, STDIO S1/4.
• Friday, 9:30 - 10:30, LEA 132.

Office hours:

Prof. Mathieu Blanchette	Tuesday 9:30-11:00	ENGTR 3107
Navin Mordani	Monday 9:00-10:30	ENGTR 3110
Hong Chuan Guo	Monday 13:00-14:30	ENGTR 3110
Yue Wang	Tuesday 15:00-16:30	ENGTR 3110
Caitrin Armstrong	Friday 13:30-15:00	ENGTR 3110
Omar Asad	Wednesday 10:30 to 12:00	MC 102
David Becerra Romero	Wednesday 14:30 to 16:00	ENGTR 3110
Zheng Dai	Thursday 10:00-11:30	ENGTR 3110
Jeremy Georges-Filteau	Thursday 11:30-13:00	ENGTR 3110
Faizy Ahsan	Thursday 13:00-14:30	ENGTR 3110
Christopher Cameron	Friday 10:30-12:00	ENGTR 3110
Caitrin Armstrong	Friday 13:00-14:30	ENGTR 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):

• [D2012] Allen B. Downey, How to think like a computer scientist - Java version.
  http://www.cs.mcgill.ca/~blanchem/250/thinkapjava.pdf

We also recommend the following textbooks:

• [CH2014] Frank M. Carrano and Timothu M. Henry, Data structures and abstractions with Java, 4th edition, Pearson Editors.
• [GT2010] Michael T. Goodrich, Roberto Tamassia, Data Structures and Algorithms in Java, 5th Edition, John Wiley and Sons.

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:

• 30% for 6 assignments (5% each)
• 20% for the midterm
• 50% for the final exam

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.

Release Date	Due Date	Announcement
Jan 5		Welcome to COMP250!
Jan 16	Jan 30th, 23:59	Assignment #1 is now available HERE
Jan 21		COMP 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

	Date	Topic	Material
Lecture 1	Jan 5	Syllabus. What is an algorithm? Language for describing algorithms. Algorithm vs implementation.	Lecture notes
Lecture 2	Jan 6	Example 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 3	Jan 10	Basics of java: Compilation, Programming style, Variables, Primitive types, Conditionals, Loops, Arrays	Lecture notes [D2012], chapters 1 - 6 Eclipse tutorial (by Alex Butyaev)
Lecture 4	Jan 12	Methods	Lecture notes [D2012], Chapters 7-11.
Lecture 5	Jan 13	Object-Oriented Programming in Java	Lecture notes (same as previous lecture) [D2012], Chapters 7-11, Sections 12-16
Tutorial	Jan 13 16:00-17:00 in ENGTR 3120	Special 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
Tutorial	Jan 16 16:00-17:00 in ENGTR 3120	Special Eclipse tutorial Second session of the tutorial.	Slides
Lecture 6	Jan 17	Iterative algorithms: Selection Sort, Insertion Sort, Bubble Sort	Lecture notes by Prof. Michael Langer [CH2014] Chapter 8
Lecture 6	Jan 19	Thinking Recursively: Examples	Lecture notes [CH2014] Chapter 7
Lecture 7	Jan 20	More Recursion examples. Merge sort	Lecture notes [CH2014] Chapter 9
Lecture 8	Jan 24	Proofs by induction - part I	Lecture notes For more examples, see "Discrete Mathematics and its applications" by Kenneth Rosen, available on reserve at the library.
Lecture 8	Jan 26	Proofs by induction - part II	Lecture notes For more examples, see "Discrete Mathematics and its applications" by Kenneth Rosen, available on reserve at the library.
Lecture 9	Jan 27	Loop invariants	Lecture notes and addendum
Lecture 10	Jan 31	Running Time	Lecture notes [CH2014] Chapter 4
Lecture 11	Feb 2	Big O definitions	Lecture notes [CH2014] Chapter 4 Examples
Lecture 12	Feb 3	Big O examples non-recursive	Lecture notes [CH2014] Chapter 4
Lecture 13	Feb 7	Running Time and Recursion	Lecture notes [GT2009] Section 5.2
Lecture 14	Feb 9	QuickSort. In-place sorting	Lecture notes [CH2014] Chapter 9
Lecture 15	Feb 10	Introduction to ADTs: Lists	Lecture notes Java Source code: Node.java, LinkedList.java, TestList.java [CH2014] Chapter 14
Lecture 16	Feb 14	ADTs: Lists implementation with linked lists	Lecture notes
Lecture 17	Feb 16	ADTs: Stacks	Lecture notes [CH2014] Chapter 5 and 6
Lecture 18	Feb 17	ADTs: Queues and deques	Lecture notes [CH2014] Chapter 5 and 6
Lecture 19	Feb 21	Review session	Lecture 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 EXAMINATION	Wednesday 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 20	Feb 23	ADTs: Trees	Lecture notes [CH2014] Chapter 5 and 6
Lecture 21	Feb 24	ADTs: Binary Search Trees	Lecture notes [CH2014] Chapter 25
Lecture 22	Mar 7	ADTs: Heaps	Lecture notes [CH2014] Chapter 26
Lecture 23	Mar 9	LECTURE CANCELED
Lecture 23	Mar 10	ADTs: Hash Tables	Lecture notes [CH2014] Chapter 21 & 22
Lecture 24	Mar 14	Data structures in Java	Lecture notes
Lecture 25	Mar 16	ADTs: Graphs	Lecture notes [CH2014] Chapter 28 & 29
Lecture 26	Mar 17	Graph algorithms: Breadth-first search (BFS) and depth-first search (DFS)	Lecture notes [CH2014] Chapter 28 & 29
Lecture 27	Mar 21	Survey of graph problems	Lecture notes [CH2014] Chapter 28 & 29
Lecture 28	Mar 23	Web search engine	Lecture notes
Lecture 28	Mar 24	Computers playing games	Lecture notes
Lecture 29	Mar 28	Binary numbers	Lecture notes
Lecture 30	Mar 30	Introduction to dynamic programming and greedy algorithms	Lecture notes
Lecture 31	Mar 31	Heuristics and fastest descent	Lecture notes
Lecture 32	Apr 4	Cryptography	Lecture notes
Lecture 33	Apr 6	Computer Graphics - Ray tracing	Lecture notes
Lecture 37	Apr 7	Review session I	Practice material to prepare for the final exam
Lecture 38	Apr 11	Review session II

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.