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.
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):
Discussion Board:
The official discussion is available in MyCourse.
Evaluation
Your final grade will be calculated as follows:
| Release Date | Due Date | Announcements |
|---|---|---|
| April 14 | Apr 17 18:30 PM | The quizzes have been publicly released to everyone. You can also practice using a previous final exam. More material is accessible on the COMP250 webpages of Mathieu Blanchette and Michael Langer. |
| April 14 | Apr 17 18:30 PM | The final exam is schedule on April 17th at 18h30 in the GYM FIELD HOUSE rows 1-23 |
| Mar 29 | Apr 13 11:59 PM | Assignment 4 released |
| Mar 15 | The class of today is cancelled. Lecture 26 for Section 1 is postponed to Mar 16 in LEA132. Section 2 is thus not required to attend the lecture on Friday. | |
| Mar 12 | Mar 26 11:59 PM | Assignment 3 released |
| Feb 20 | Feedback specifying how you lost marks will be uploaded to mycourses as a file in the assignment feedback (within the assignment tab). Not everyone has received grades matching their latest submission, we are currently looking into this and your grade might change between now and tomorrow. You should be able to see it at some point tonight, but it might be tomorrow. If you have questions about your performance on the assignment, please hold your questions until the next announcement, and only email cs250@cs.mcgill.ca | |
| Feb 20 | Eclipse Tutorial Slides (Thank you Matt) | |
| Feb 16 | March 2 11:59 PM | Assignment 2 released |
| Jan 30 | Feb 13 11:59 PM | Assignment 1 released |
| Jan 8 | Welcome to COMP250! |
| Date | Topic | Material | Instructor | |
|---|---|---|---|---|
| Lecture 1 | Jan 8-9 | Syllabus. What is an algorithm? Language for describing algorithms. Algorithm vs implementation. | Lecture notes | J. Waldispühl |
| Lecture 2 | Jan 10-11 | 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 | J. Waldispühl |
| Lecture 3 | Jan 12 | Binary numbers | Lecture notes | J. Waldispühl |
| Lecture 4 | Jan 15-16 | Eclipse Tutorial | Lecture notes | C.G. Oliver |
| Lecture 5 | Jan 17-18 | Basics of java: Compilation, Programming style, Variables, Primitive types, Conditionals Input/Output | Lecture notes and [D2012], chapters 1 - 6 | C.G. Oliver |
| Lecture 6 | Jan 19 | Loops, Arrays, and Strings. | Lecture notes [D2012], Chapters 7-11. | C.G. Oliver |
| Lecture 7 | Jan 22-23 | Object-Oriented Programming in Java | Lecture notes [D2012], Chapters 7-11, Sections 12-16 | C.G. Oliver |
| Lecture 8 | Jan 24-25 | Thinking Recursively: Examples | Lecture notes [CH2014] Chapter 7 | J. Waldispühl |
| Lecture 9 | Jan 26 | More Recursion examples. Merge sort | Lecture notes [CH2014] Chapter 9 | J. Waldispühl |
| Lecture 10 | Jan 29-30 | Proofs by induction | Lecture notes For more examples, see "Discrete Mathematics and its applications" by Kenneth Rosen, available on reserve at the library. | J. Waldispühl |
| Lecture 11 | Jan 31-Feb 1 | Loop invariants | Lecture notes | J. Waldispühl |
| Jan 30 - Feb 13 | Assignment 1 released | Submit on MyCourses | ||
| Lecture 12 | Feb 2 | Running Time | Lecture notes [CH2014] Chapter 4. | J. Waldispühl |
| Lecture 13 | Feb 5-6 | Big O definitions | Lecture notes [CH2014] Chapter 4 Examples | C.G. Oliver |
| Lecture 14 | Feb 7-8 | Big O examples non-recursive | Lecture notes [CH2014] Chapter 4 | C.G. Oliver |
| Lecture 15 | Feb 9 | Running Time and Recursion | Lecture notes [GT2009] Section 5.2 | C.G. Oliver |
| Lecture 16 | Feb 12-13 | QuickSort. In-place sorting | Lecture notes [CH2014] Chapter 9 | C.G. Oliver |
| Lecture 17 | Feb 14-15 | Introduction to ADTs (1) | Lecture notes Java Source code: Node.java, LinkedList.java, TestList.java [CH2014] Chapter 14 | J. Waldispühl |
| Lecture 18 | Feb 16 | Introduction to ADTs (2) | Lecture notes | J. Waldispühl |
| Feb 16 - March 2 | Assignment 2 released | Submit on MyCourses | ||
| Lecture 19 | Feb 19-20 | ADTs: Stacks | Lecture notes [CH2014] Chapter 5 and 6 | J. Waldispühl |
| Lecture 20 | Feb 21-22 | ADTs: Queues and deques | Lecture notes [CH2014] Chapter 5 and 6 | J. Waldispühl |
| Lecture 21 | Feb 23 | ADTs: Trees | Lecture notes [CH2014] Chapter 5 and 6 | J. Waldispühl |
| Lecture 22 | Feb 26-27 | ADTs: Binary Search Trees | Lecture notes [CH2014] Chapter 25 | J. Waldispühl |
| Lecture 23 | Feb 28-Mar 1 | ADTs: Heaps (1) | Lecture notes [CH2014] Chapter 26 | J. Waldispühl |
| Lecture 24 | Mar 2 | ADTs: Heaps (2) | Lecture notes [CH2014] Chapter 21 & 22 | J. Waldispühl |
| Reading Week | ||||
| Mar 12- March 26 | Assignment 3 released | Submit on MyCourses | ||
| Lecture 25 | Mar 12-13 | ADTs: Hash Tables | Lecture notes [CH2014] Chapter 28 & 29 | J. Waldispühl |
| Lecture 26 | Mar 14-15 | ADTs: Graphs | Lecture notes [CH2014] Chapter 28 & 29 | J. Waldispühl |
| Lecture 27 | Mar 19-20 | Graph algorithms: Breadth-first search (BFS) and depth-first search (DFS) | Lecture notes [CH2014] Chapter 28 & 29 | J. Waldispühl |
| Lecture 28 | Mar 21-22 | Survey of graph problems | Lecture notes | C.G. Oliver |
| Lecture 29 | Mar 23 | Introduction to dynamic programming and greedy algorithms | Lecture notes | C.G. Oliver |
| Lecture 30 | Mar 26-27 | Web search engines | Lecture notes | C.G. Oliver |
| Lecture 31 | Mar 28-29 | Computers playing games | Lecture notes | C.G. Oliver |
| Mar 29- Apr 13 | Assignment 4 released | Submit on MyCourses | ||
| Lecture 32 | Apr 3 | Cryptography | Lecture notes Note: Section 1 & 2 are merged. | C.G. Oliver |
| Lecture 33 | Apr 4-5 | Blockchain | Lecture notes | C.G. Oliver |
| Lecture 34 | Apr 6 | Machine Learning | Lecture notes | C.G. Oliver |
| Lecture 35 | Apr 9-10 | Bioinformatics | Lecture notes | J. Waldispühl |
| Lecture 36 | Apr 11-12 | Review | Lecture notes | J. Waldispühl |
| Lecture 37 | Apr 13 | Beyond COMP250 | Lecture notes | J. Waldispühl |
| Practice for the final exam | April 14 | Practice material released. | The quizzes have been publicly released to everyone. You can also practice using a previous final exam. More material is accessible on the COMP250 webpages of Mathieu Blanchette and Michael Langer. | |
Note: Schedule subject to changes
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). 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.
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.
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