Computer Science 252
Algorithms and Data Structures
Last update: January 3, 2014

Winter 2014 --- Course Syllabus





Instructor  


Luc Devroye | Email to lucdevroye@gmail.com | Tel: (514) 398-3738 (office) | McConnell Engineering Building, Room 300N | Office hours: Monday and Wednesday, 10-11:30am, and any time my door is open. You don't work for me---I work for you.


Time and location


Tuesday, Thursday, 10-11:30 am, January 7, 2014 --- April 10, 2014.
Room: Trottier 60.
Midterm: February 18, 2014, 10-11:30am, Trottier 60.
Study break: March 3-7, 2014.
Extra lectures: Friday, March 14, 2014, 3-6pm, Trottier 1080.
Final exam: April 16, 2014, 9-12am, Trottier 1100.
Final: TBA

Moodle: students log in with their CS username, and the password is their McGill ID. This secure site has PDF copies of some assignments and some solutions.


Teaching assistant


Hang Ma. Office hours: Tuesday, 9-12am. Office: McConnell 108. Email to hang.ma@mail.mcgill.ca.


Lectures (2014)


Material covered in each lecture in 2014.


Objectives


  • Introduce the student to algorithmic analysis.
  • Introduce the student to the fundamental data structures.
  • Introduce the student to problem solving paradigms.


Contents


Part 1. Data types.

  • Abstract data types.
  • Lists. Linked lists. Examples such as sparse arrays.
  • Stacks. Examples of the use of stacks in recursion and problem solving.
  • Queues.
  • Trees. Traversal. Implementations. Binary trees.
  • Indexing methods. Hashing.
  • Introduction to abstract data types such as mathematical set, priority queue, merge-find set and dictionary.
  • Heaps.
  • Binary search trees, balanced search trees.
  • Tries, suffix trees.
  • Data structures for coding and compression.

Part 2. Algorithm design and analysis.

  • The running time of a program.
  • Worst-case and expected time complexity.
  • Analysis of simple recursive and nonrecursive algorithms.
  • Searching, merging and sorting.
  • Amortized analysis.
  • Lower bounds.
  • Introductory notions of algorithm design:
    • Divide-and-conquer. Recurrences. The master theorem. Quicksort. Other examples such as fast multiplication of polynomials and matrices. Fast Fourier transform.
    • Dynamic programming. Examples such as Bellman-Ford network flow, sequence alignment, knapsack problems and Viterbi's algorithm.
    • Greedy methods. This includes the minimal spanning tree algorithm and Huffman coding.
  • Graph algorithms.
    • Depth-first search and breadth-first search
    • Shortest path problems
    • Minimum spanning trees
    • Directed acyclic graphs
    • Network flows and possibly bipartitie matching


Evaluation


  • Assignments: 42% (Six theoretical assignments will be given, each worth 7% of the total mark.)
  • Midterm: 8%
  • Final: 50%


Prerequisites


Computer Science 250. Mathematics 240. Recommended background: Mathematics, discrete mathematics, arguments by induction. Restricted to Honours students in Mathematics and/or Computer Science.


Textbook


T.H. Cormen, C.E.Leiserson, R.L.Rivest, and C. Stein: "Introduction to Algorithms (Third Edition)", MIT Press, Cambridge, MA, 2009. There are several printings of the first edition of this book. All are equivalent. A list of errata of the second printing is available on-line. Pirated copies of this book are navigating the web.

Another appropriate text, with a different focus (more algorithms, fewer data structures) is by J. Kleinberg and E. Tardos: "Algorithm Design". Pearson, Boston, 2006.


On-line resources


Class notes

  • (Outdated) class notes from 1997 compiled by students, listed below. Use at your own risk.

  • Old Assignments
  • Assignment 1 (Jan 18, 2000)
  • Assignment 2 (Feb 8, 2000)
  • Solution of assignment 2
  • Assignment 3 (Mar 14, 2000)
  • Solution of assignment 3
  • Assignment 4 (Mar 21, 2000)
  • Solution of assignment 4

  • Old Tutorials
  • Tutorial 2 (Feb 1, 2000)
  • Tutorial 4 (Mar 7, 2000)

  • Old Midterms
  • Midterm 1992: PostScript
  • Midterm 1996: PostScript
  • Midterm 1997: PostScript; PDF
  • Midterm 1999: PostScript; PDF
  • First midterm 2000: HTML
  • Second midterm 2000: HTML

  • Old Finals
  • Finals pre-1996: PostScript
  • Final 1996: PostScript
  • Final 1997: PostScript; PDF
  • Final 1997 answers: ascii text
  • Final 1999: HTML
  • Final 2000: HTML

  • Practice questions
  • Practice questions set 1
  • Practice questions set 1: answers
  • Practice questions set 2
  • Practice questions set 2: answers
  • Practice questions set 3
  • Practice questions set 3: answers
  • Practice questions set 4
  • Practice questions set 4: answers
  • Practice questions set 5
  • Practice questions set 5: answers