Description: (3 credits; 3 hours) 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.

Prerequisite: 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.

Instructor: Prof. Claude Crépeau
Office Hours: Friday 12:00-15:00, McConnell 110N, (514) 398-4716
SPECIAL Office Hours: Monday (Mar 15, 2016) 11:30-14:30, McConnell 110N,
avoid sending me HomeWork questions directly; uses links below for faster replies...

FOR ALL CLASS MATTERS CONTACT US
via e-mail: cs250@cs.mcgill.ca
or
via Facebook: group COMP250 Winter 2016
or
Discussion board: cs250qanda.cs.mcgill.ca/ NOW WORKING; you will need a cs.mcgill.ca account to use it.


Teaching Assistants:

• Faizy Ahsan (faizy.ahsan@mail.mcgill.ca) Tu 10:00-11:30 TR3110
• Omar Asad (omar.asad@mail.mcgill.ca) M 10:00-11:30 MC102
• David Becerra-Romero (david.becerraromero@mail.mcgill.ca) W 10:00-11:30 TR3110
• David Bourque (david.bourque@mcgill.ca) W 13:30-15:00 TR3110
• Christopher Cameron (christopher.cameron@mail.mcgill.ca) F 10:00-11:30 TR3110
• Faiz Khan (faiz.khan@mail.mcgill.ca) TBA TR3110
• DoYeon Kim (doyeon.kim@mail.mcgill.ca) W 12:00-13:30 TR3110
• Hardik Vala (hardik.vala@mail.mcgill.ca) Th 15:00-16:30 TR3110






---

L E C T U R E S

Lecture 1 (January 12th, 2016) Course Outline. Intro to Algorithms (SLIDES) Outline and intro to Algorithms (VIDEO) Lecture 2 (January 14th, 2016) Grade School Algorithms (NOTES)   (SLIDES)   (SLIDES SxS)   (VIDEO) Lecture 3 (January 19th, 2016) Binary representation (NOTES)   (SLIDES)   (SLIDES SxS)   (VIDEO) Homework 1 OUT Overview of solution Homework 1 tester Java code Binary Calculator used as reference Useful Java Background Lecture 4 (January 21st, 2016) Fractional Binary Numbers (NOTES)   (SLIDES)   (SLIDES SxS)   (VIDEO) Lecture 5 (January 26th, 2016) (Singly) Linked Lists (NOTES)   (SLIDES)   (SLIDES SxS)   (VIDEO) Arrays + Insertion sort Demo Lecture 6 (January 28th, 2016) (Doubly) Linked Lists + ArrayList (NOTES)   (SLIDES)   (SLIDES SxS)   (VIDEO) Lecture 7 (February 2nd, 2016) Stacks (NOTES)   (SLIDES)   (SLIDES SxS)   (VIDEO) Lecture 8 (February 4th, 2016) Queues (NOTES)   (SLIDES)   (SLIDES SxS)   (VIDEO) HW-1 IN; Homework 2 OUT UPDATED Lecture 9 (February 9th, 2016) Asymptotic Notations and running time analysis (NOTES)   (SLIDES)   (SLIDES SxS)   (VIDEO) Lecture 10 (February 11th, 2016) Recursion, induction (NOTES)   (SLIDES)   (SLIDES SxS)   (VIDEO) Lecture 11 (February 16th, 2016) Recurrences and running time analysis (NOTES)   (SLIDES)   (SLIDES SxS)   (VIDEO) Lecture 12 (February 18th, 2016) Master Theorem and Applications (NOTES)   (SLIDES)   (SLIDES SxS)   (VIDEO) HW-2 IN (click for solutions) Lecture 13. (February 23rd, 2016) MID-TERM EXAM during class time MIDTERM EXAM FORMAT MIDTERM EXAM with SOLUTIONS MIDTERM EXAM Spring 2004

Lecture 14 (February 25th, 2016) Cryptography special Lecture (SLIDES)   (SLIDES SxS)   (VIDEO) Homework 3 OUT (v3.0) Lecture 15 (March 8th, 2016) Geometry special Lecture (SLIDES)   (VIDEO) Lecture 16 (March 10th, 2016) Graphs ADT (SLIDES)   (VIDEO) Lecture 17 (March 15th, 2016) Trees ADT (SLIDES)   (VIDEO) Lecture 18 (March 17th, 2016) DFS, BFS (SLIDES)   (VIDEO) HW-3 IN; March 18th Homework 4 OUT (v4.0) Homework 4 tester Java code Please use code from here. DUE DATE POSTPONED TO SUNDAY APRIL 3rd 2016, 23:59 Lecture 19 (March 22th, 2016) Search and BST (SLIDES)   (VIDEO) Lecture 20 (March 24th, 2016) Heaps, heapsort and n log n lower bound. (SLIDES)   (VIDEO) Lecture 21 (March 29th, 2016) O(n) sorting methods: couting and radix sorts. (SLIDES)   (VIDEO) Lecture 22 (March 31th, 2016) Quicksort and String matching. (SLIDES)   (VIDEO) HW-4 IN; HW-5 OUT; April 4th; 2:00am Lecture 23 (April 5th, 2016) KMP string matching algorithm (SLIDES)   (VIDEO) Lecture 24 (April 7th, 2016) Tries + data compression (Lossless vs lossy) (SLIDES)   (SLIDES SxS)   (VIDEO) Lecture 25 (April 12th, 2016) SORRY - - NO SHOW !!! Lecture 26 (April 14th, 2016) Review of course material (SLIDES)   (VIDEO) HW-5 IN; April 17th FINAL EXAM. (April 28th, 2016) FINAL EXAM instruction sheet

Lectures are being recorded and will be available here as well as on MyCourse.
Note: Allow up to 24 hours for each recording to become available.

---

FINAL EXAM Spring 2004

FINAL EXAM Spring 2000

A SAMPLE FINAL EXAM (based on the actual one Y2K)

SOLUTIONS to SAMPLE FINAL

---

Required Textbook:



• Allen B. Downey,
  
  How to think like a computer scientist - Java version.
  

  ---

Recommended Textbook:



• Michael T. Goodrich, Roberto Tamassia
  
  Data Structures and Algorithms in Java (6th Edition)
  John Wiley and Sons; ISBN: 9781118771334

  ---

  Other Useful Books:

  
  
  
  
  • Jon Kleinberg and Éva Tardos, Cornell University,
    
    Algorithm Design
    Addison-Wesley, 2006.
    

    ---

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest,and Clifford Stein,
    
    Introduction to Algorithms, 3/e
    MIT Press, 2009.
    ONLINE ACCESS TO THE 3/e OF THE BOOK (from within McGill)
    

    ---

  • Dasgupta, Papadimitriou and Vazirani
    
    Algorithms
    McGraw-Hill,2008, ISBN:9780073523408
    Preliminary version of the book
    Solutions to exercices...
    

    ---

  • Gilles Brassard et Paul Bratley,
    
    Fundamentals of Algorithmics
    Prentice-Hall, 1996. ISBN: 9780133350685

    ---

---

Send comments/questions to crepeau@cs.mcgill.ca


2016/01/25