Computer Science 252
Algorithms and Data Structures
Last update: April 10, 2016

Winter 2016 --- Course Syllabus





Instructor  


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


Time and location


Wednesday & Friday, 10-11:30am, January 8, 2016 --- April 15, 2016.
Room: Trottier 70.
Midterm: February 19, 2016, 10-11:30am, Trottier 70.
Study break: February 29-March 5, 2016.
Extra lectures: Monday March 21 (Trottier 70), Thursday, March 24 (Trottier 60), and Monday, April 11 (Trottier 90), all from 6-7:30pm. These lectures replace those of April 1, 6 and 8.
Last day of lectures: April 15.
Final exam: April 18, 2-5pm, room Wong 1020.

Teaching assistants

Email to Tommy Reddad. Office hours: Tuesday, 10-11:30am, Thursday, 8:30-10am. Office: McConnell South 109.
Additional office hours for week of April 11-15: Wednesday, 9-11:30am, Friday, 9-10am.


Lectures (2016)


Material covered in each lecture in 2016


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 bipartite 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. Amazon link. 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. Excellent 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