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.

**Instructor:**

**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

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

**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

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 | Binary numbers | Lecture notes not yet available |

Lecture 29 | Mar 28 | Computers playing games | 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 | Text compression | Lecture notes |

Lecture 37 | Apr 7 | Review session I | |

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.

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