Computer Science 308-252B
Algorithms and Data Structures
November 18, 2004


Winter 2005 -- Course syllabus
The final exam will be held on Monday, April 18th, at 2 pm in Wilson 110.
Important: please have a look at this review sheet!


Instructors


Bruce Reed


Martin Courchesne


Teaching assistant


Ian Reid


Assignments


  • Assignment 1, due January 27th at 2:30 pm.
    •       - Solutions
  • Assignment 2, due February 3rd at 2:30 pm.
    •       - Solutions
  • Assignment 3, due February 10th at 2:30 pm.
    •       - Solutions
  • Assignment 4, due March 22nd at 2:30 pm.
    •       - Solutions
    Warning! In assignment 4, question 4, part d, was modified and turned into a bonus question!
  • Assignment 5, due April 5th at 2:30 pm.
    •       - Solutions
    Note that clarifications have been brought to questions 1 and 4!
  • Assignment 6, due April 12th at 2:30 pm.
    •       - Solutions


    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
      • Dynamic programming
      • Greedy methods
    • Graph algorithms.
      • Depth-first search and breadth-first search
      • Shortest path problems
      • Minimum spanning trees
      • Directed acyclic graphs


    Lectures


    Material covered in each lecture. To be filled in as we move along in the style of Material covered in each lecture for a previous year. However, the pace and order may be different.


    Prize Problems


    Check out last year's challenging prize problems.


    Evaluation


    • Assignments: 30% (4-6 assignments)
    • Class Test: 25% (will be held in class on February 17th)
    • Final: 45%


    Prerequisites


    Computer Science 308-250. 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. D. Stein "Introduction to Algorithms", MIT Press, Cambridge, MA, 2001. There are several printings of the second edition of this book. All are equivalent. A CD with six of the best Data Structure books, including our textbook, is available from Dr. Dobb's, PO Box 1525, Martinez, CA 94553, for 60 US dollars. If you want to check it out, email Professor Luc Devroye.


    On-line resources


    Class notes

  • Class notes for 1997 (compiled by students)
    • 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
    •




    Copyright © 2002 Luc Devroye
    Email: luc@cs.mcgill.ca