CSC263 at UTM - Data Structures and Analysis - Spring 2010

Lecture: Monday 11 - 13, SE 3131
Tutorial: Wednesday 16 - 17, NE 268
Instructor: Avner Magen
Office hours: Monday 14-15 (SB 4062, 905-569-4741).
Tutor: Bryce Zimny

Useful Information/links

  • Course Information Sheet
  • Important Dates
  • Textbook: Goodrich and Tamassia, Algorithm Design, Wiley (required).
    We will also use the following text which is available free on-line to U of T students through the library website:
    Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, second edition, McGraw-Hill.
  • additional references:
    check this useful writeup about AVL by Vassos Hadzilacos.
    Here is the chapter about Binomial Heaps from CLRS

  • Assignments

  • A1 and solution
  • A2 and solution
  • A3 and solution
  • A4 and solution

    Exercises (not to be submitted)

  • E1
  • E2
  • E3
  • E4
  • E5
  • E6

    The story of the course so far


    Date Announcement(s)
    here is a list of questions that will help you prepare to the exam. This list somewhat represents questions you'll get in the exam (although some questions are a bit harder than the ones in the exam). I will add some more during the weekend, so it's highly recommended that you'll revisit this file.
    There will be a review session with Bryce on April 7th, in the usual Tutorial time, 3-4pm. Location: SE 2068.
    here is a list of topics you are responsible for for the exam.
    here is the header page of the exam, with useful information. Notice especially the aid sheet that you are allowed to bring. (only handwritten please!).
    Office hour with the TA, Bryce, Wednesday Mar 31, at 3:00. Room SE 4062.
    ex6 was uploaded.
    Some typos in A4 were corrected. What used to be "rst nds" is now, "First finds" (some funny bug of fi being removed). At any event, the current version should be good.
    I will be available for ofice hour Wednesday 24/3 at 2:00.
    Exercise 5 was uploaded.
    Assignment 4 in its entirety was uploaded.
    A4 to be submitted only at the last day of class, March 29.
    Exercise 4 was uploaded.
    Exercise 3 was uploaded.
    Clarification: A3 Q2b. By "sequence S as above" I simply meant a sequence of INSETT/SEARCH/DELETE, and not a sequence such as the one provided in Q2a.
    Assignment 3 was uploaded.
    To clarify: for the test, no aids are allowed.
    solution to A2 was uploaded.
    I have compiled a list of questions that bear similarities to ones you are going to get on the test. Do them well and you will stand a great chance to succeed in the test. Check this list from time to time as I will be adding some stuff. I typically don't supply solutions to these sample questions, as just getting this list is already very valuable. I wil however be happy to discuss them in office hours on Monday.
    Material for the test will be anything we covered so far not including hasging. This means asymptotics, average-case complexity, quicksort, dictionaries (BST,AVL tree), and heaps (binary and binomial).
    If you rather submit your assignment by mail, feel free to do so, by 12PM today to Bryce ( and CC me.
    Check assignment 2 for clarification in Q1: you may assume that the AVL tree supports a data field at each node x which is the number of nodes in the subtree rooted at x.
    solution to A1 was uploaded.
    A2 to be submitted by 12PM, Friday 12/2 to the drop box which is located in the basement of the South Building, by the stairwell near classroom 1153
    Office hour with the TA, Bryce, Wednesday Feb 10, at 3:00. Room SE 4062.
    In the questionnaire today some of you have indicated tht you would like to get practice-exercises (not to be submitted). So I am starting to post such exercises. Please try to at least think about them. In tutorial Bryce may cover some of them. Check the "exercises" section above.
    Assignment 2 was uploaded. Due Friday Feb 12th
    If you are looking for a partner email me and perhaps I can help to match you up with another student in a similar situation.
    Office hour of the TA 3:00-4:00 in SE 4062
    Extension for Assignment 1. Due Monday Feb 1 in class.
    Assignment 1 in its entirety was uploaded.
    Office hour with the TA, Bryce, Wednesday Jan 20, at 3:00. Room SE 4062.
    IMPORTANT: if you need a waiver the deadline is today. I am in St. George, BUT - you don't have to come here. You can send a scanned-copy of the waiver form, and I will (depending on its content) sign it.
    (First part of) assignment 1 was uploaded.
    Don't forget. Tutorial today Jan 6th, 16-17. Bryce will cover background material, like asymptotics and probability theory, as well as some complexity analysis examples.