Announcements:

    Date/Subject Message
    04-Dec-01
    Coursework and Exam
    There has been a rumour that you need to obtain at least xx% of coursework mark in order to pass the course. I would like to clarify that there is no such a rule.
    However, there is a rule that "For a student to pass the course, at least 30% of the maximum mark for the examination must be obtained. ".
    So, to pass this course:
    you should get a total of not less than 40% of the final mark.
    And, IN ADDITION,
    if you got good marks in coursework, please also be well-prepared for the exam so that you can get at least 30% of it.
    if you got poor marks in coursework, please try your best for the exam so that you can make up not less than 40% of the final mark.
    03-Dec-01
    Assignment marks
    The following email has been sent to you by email:

    To all CS3381 students,

    Please find your marks of the assignment in the attached file.
    I have found some plagiarisms in your submissions. There will be punishments since you are not supposed to have COPIED or ALLOWED OTHERS TO COPY assignments.
    Individual students will receive a separate email concerning the punishment. (the punishments -- deduction of marks -- are not reflected in the attached file)
    28-Nov-01
    Assignment model answers
    Here are the model answers of the assignment questions.
    28-Nov-01
    Answers of tutorial exercises
    As requested by some of you, some tut answers are now posted here: 2, 3, 4, 5, 6, 7.

    Disclaimers: [ see the announcement: 03-Oct-01 Answers of tutorial exercises ]
    26-Nov-01
    Amendment of assignment (Q7)
    There is a typing mistake in Q7 of the assignment. Please note the following amended question:
    ".. Prove that HC is NP-complete assuming that HPBTP is NP-complete. .."
    Please also note the amendments to Q1,3,5b in 19-Nov and 17-Nov's announcements.
    19-Nov-01
    Amendment of assignment (question 5b)
    Following is the amended question for 5b in the assignment:
    To find the longest path between 2 given vertices in a graph G with positive weights, we can change the weight of every edge e from w(e) to k w(e), where k is a value larger than any edge weight in G, and then find the shortest path in the resultant graph.
    17-Nov-01
    Amendment of assignment (question 1 and 3)
    For question 1 in the assignment, the indentation of the given code was wrong and thus misleading. Please refer to the following amended code:

    / * suppose the rods are labeled 1, 2, and 3 */
    Hanoi (m, i, j) /* to move m rings from rod i to rod j*/
    1    If(m>0)
    2         If (i=1 and j=2) or (i=2 and j=1)
    3             Then intermediate_rod = 3
    4         If (i=1 and j=3) or (i=3 and j=1)
    5             Then intermediate_rod = 2
    6         If (i=2 and j=3) or (i=3 and j=2)
    7             Then intermediate_rod = 1
    8         Hanoi(m-1,i,intermediate_rod)
    9         Move top ring of rod i to rod j
    10        Hanoi(m-1,intermediate_rod,j)

    For question 3 in the assignment, we assume that there is a way to sort the courses according to increasing difficulties, and that the prerequisites of a course Si must be easier than Si.
    07-Nov-01
    Assignment

    The assignment sheet is here.

    Assignment submission date/time: Nov 28 (Wed) 6:35-6:40 pm during week 13 lecture. Submissions before or after the above collection time will not be accepted.

    24-Oct-01
    Quiz and sample answers
    The quiz and sample answers can be found : here.
    8-Oct-01
    Quiz: time changed
    As requested by some of you, the time of the quiz is changed to (Week 7 lecture session) 17 Oct 2001 7:35pm-8:20pm .
    5-Oct-01
    Appendix for the quiz
    This appendix will be given to you during the quiz: click here.
    03-Oct-01
    Quiz
    Please note that we'll have a quiz during Week 7 lecture session (17 Oct 2001 6:35pm-7:20pm) The duration of the quiz will be 45 minutes. It will involve fill-in-blanks and short questions etc., to test your understanding of the concepts and your ability of algorithm analysis and design. The scope will cover the following topics:
    1. Introduction
    2. Analysis of Algorithms
    3. Divide and Conquer (and recurrences)
    4. Dynamic Programming
    5. Greedy Algorithms

    This quiz will contribute to 15% of the final mark of this course. All questions are compulsory.
    During the quiz you'll be supplied with an appendix of useful equations and some algorithms taught in this course. This appendix will be released on the course web page within this week.
    03-Oct-01
    Answers of tutorial exercises
    As requested by some of you, some tut answers are now posted here: 2, 3.

    Disclaimers:
    1. I won't post those answers that are available directly from text book or lecture slides.
      -
    2. Most questions can have more than 1 answer. So posted answers may be different from those given during the classes.
      -
    3. The posted answers are initially for my own reference. They may be incomplete, not detail enough, and with errors that I am just too lazy to correct. But I am sure that if you have understood them during the classes, you should have no problem fixing them.
      -
    4. Due to the effort of creating typed / written solutions, I don't guarantee that future tut answers will all be posted to you.
    11-Sep-01
    Supplementary answer to Q6 (Tutorial Exercise - Analysis)
    For interested students only:
    You can find a robust method to solve Q6 (Tutorial Exercise - Analysis) here. [Don't read it before you attend week 2 tutorial]