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


Instructors:

Teaching Assistants:

Lectures:

Contact:

All course-related email (assignments, quizzes, general issues) should be set to cs250@cs.mcgill.ca. Emails sent to personal addresses will not likely be seen.

Office hours:

TA Office Hours will be held in Trottier 3090

Please consult this calendar for the most up to date Office Hour schedule.

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 is available in MyCourse.

Evaluation
Your final grade will be calculated as follows:

Notes:

ANNOUNCES


Release DateDue DateAnnouncements
Feb 16March 2 11:59 PMAssignment 2 released
Jan 30Feb 13 11:59 PMAssignment 1 released
Jan 8Welcome to COMP250!

SCHEDULE


DateTopicMaterialInstructor
Lecture 1Jan 8-9Syllabus. What is an algorithm? Language for describing algorithms. Algorithm vs implementation.Lecture notesJ. Waldispühl
Lecture 2Jan 10-11Example 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 notesJ. Waldispühl
Lecture 3Jan 12Binary numbersLecture notesJ. Waldispühl
Lecture 4Jan 15-16Eclipse TutorialLecture notesC.G. Oliver
Lecture 5Jan 17-18Basics of java: Compilation, Programming style, Variables, Primitive types, Conditionals Input/OutputLecture notes and [D2012], chapters 1 - 6C.G. Oliver
Lecture 6Jan 19Loops, Arrays, and Strings.Lecture notes
[D2012], Chapters 7-11.
C.G. Oliver
Lecture 7Jan 22-23Object-Oriented Programming in Java Lecture notes
[D2012], Chapters 7-11, Sections 12-16
C.G. Oliver
Lecture 8Jan 24-25Thinking Recursively: ExamplesLecture notes
[CH2014] Chapter 7
J. Waldispühl
Lecture 9Jan 26More Recursion examples. Merge sortLecture notes
[CH2014] Chapter 9
J. Waldispühl
Lecture 10Jan 29-30Proofs by inductionLecture notes
For more examples, see "Discrete Mathematics and its applications" by Kenneth Rosen, available on reserve at the library.
J. Waldispühl
Lecture 11Jan 31-Feb 1Loop invariantsLecture notesJ. Waldispühl
Jan 30 - Feb 13 Assignment 1 released Submit on MyCourses
Lecture 12Feb 2Running TimeLecture notes
[CH2014] Chapter 4.
J. Waldispühl
Lecture 13Feb 5-6Big O definitionsLecture notes
[CH2014] Chapter 4
Examples
C.G. Oliver
Lecture 14Feb 7-8Big O examples non-recursiveLecture notes
[CH2014] Chapter 4
C.G. Oliver
Lecture 15Feb 9Running Time and RecursionLecture notes
[GT2009] Section 5.2
C.G. Oliver
Lecture 16Feb 12-13QuickSort. In-place sortingLecture notes
[CH2014] Chapter 9
C.G. Oliver
Lecture 17Feb 14-15Introduction to ADTs (1)Lecture notes
Java Source code: Node.java, LinkedList.java, TestList.java
[CH2014] Chapter 14
J. Waldispühl
Lecture 18Feb 16Introduction to ADTs (2)Lecture notesJ. Waldispühl
Feb 16 - March 2 Assignment 2 released Submit on MyCourses
Lecture 19Feb 19-20ADTs: Stacks Lecture notes
[CH2014] Chapter 5 and 6
J. Waldispühl
Lecture 20Feb 21-22ADTs: Queues and dequesLecture notes
[CH2014] Chapter 5 and 6
J. Waldispühl
Lecture 21Feb 23ADTs: TreesLecture notes
[CH2014] Chapter 5 and 6
J. Waldispühl
Lecture 22Feb 26-27ADTs: Binary Search TreesLecture notes
[CH2014] Chapter 25
J. Waldispühl
Lecture 23Feb 28-Mar 1ADTs: Heaps (1) Lecture notes
[CH2014] Chapter 26
J. Waldispühl
Lecture 24Mar 2ADTs: Heaps (2) Lecture notes
[CH2014] Chapter 21 & 22
J. Waldispühl
Reading Week
Lecture 25Mar 12-13ADTs: Hash TablesLecture notes
[CH2014] Chapter 28 & 29
J. Waldispühl
Lecture 26Mar 14-15ADTs: GraphsLecture notes
[CH2014] Chapter 28 & 29
J. Waldispühl
Lecture 27Mar 16Graph algorithms: Breadth-first search (BFS) and depth-first search (DFS)Lecture notes
[CH2014] Chapter 28 & 29
J. Waldispühl
Lecture 28Mar 19-20Survey of graph problemsLecture notesC.G. Oliver
Lecture 29Mar 21-22Introduction to dynamic programming and greedy algorithmsLecture notesC.G. Oliver
Lecture 30Mar 23Greedy algorithms and fastest descentLecture notesC.G. Oliver
Lecture 31Mar 26-27Computer playing gamesLecture notesC.G. Oliver
Lecture 32Mar 28-29Web search engineLecture notesC.G. Oliver
Lecture 33Apr 3Machine Learning (1)Lecture notes
Note: Section 1 & 2 are merged.
C.G. Oliver
Lecture 34Apr 4-5Machine Learning (1)Lecture notesC.G. Oliver
Lecture 35Apr 4-5BioinformaticsLecture notesC.G. Oliver
Lecture 36Apr 6BlockchainLecture notesC.G. Oliver
Lecture 37Apr 9-10More on JavaLecture notesC.G. Oliver
Lecture 38Apr 11-12ReviewJ. Waldispühl
Lecture 39Apr 13Beyond COMP250J. Waldispühl

Note: Schedule subject to changes

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
The assignments, quizzes and final exams will be graded automatically. However, if you wish to check that your answers have been properly recored, we will provide you all the material needed to verify the correctness of your grades.

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 (for programming questions). Do not compress your files. All files must open on LINUX SOCS workstations. Failure to submit your solution in the required format will result in an absence of grading.
The quality of the presentation of your solution is very important. Unreadable material, cryptic notations, or bad organization of your code 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:

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

Carlos G. Oliver
3630 University Street, Room 3140, Montreal QC H3A 0C6
(E-mail) carlos.gonzalezoliver@mail.mcgill.ca

Based on a template from BlackTie.co