COMP271 Design and Analysis of Algorithms
Spring 2003
Important Notes: Revised
Sunday, May 25, 2003:
Due to
the SARS situation and following the HKUST academicaffairs office
recommendations we will make the following changes in the COMP271 class this
semester:
 There will be no more facetoface lectures this
semester. That is, all formal classes will be cancelled (unless the SARS
situation unexpectedly quickly improves)
 All Tutorial sessions will also be cancelled
(although we will continue posting tutorial assignments for you to
practice on).
 You will be responsible for learning the material yourselves from the
notes and reading assignments posted on the class
lecture
page. See the
lecture
page for more detailed instructions as
to exactly which material you will be responsible to know and when. The next
five lecture notes have already been posted. The remaining ones
will be posted soon.
 The instructor will hold officehours in his office (room 3559) during
the scheduled class hours: tuesday/thursday 9:001020. You are welcome to
stop by and ask questions then. You are also welcome to email questions
at anytime to
golin@cs.ust.hk
or to ask for an appointment outside of officehours.
 As previously announced the class grading scheme has been changed as
follows: The midterm has been cancelled. There are now five
assignments worth 6% of the final grade each (rather than four worth 5%
each). The final exam will now be worth 70% of the final grade.
 Assignment 2 is due Tuesday April 15, 2003. Assignment 3 is due
Thursday, April 24, 2003.
 There
will be a voluntary Question and Answer session on Thursday, April 17, 2003,
9:40AM, in the standard 271 classroom. Nothing will be taught but the
instructor will be there to answer any questions you might have about the
readings.

17/04/03: Lecture 13 was just revised and reposted to
web (errors corrected on pages 15/16). I also just posted solutions to
Assignment 2.

21/04/03: There was an error in the example given in
Problem 4 of Assignment 3. A revised version of Assignment 3 with the error
corrected has just been posted.

21/04/03: This week's tutorial (on greedy
algorithms) was just posted to the
Question Bank and
Tutorial Page. The problems in this tutorial come from Question Bank
4; QB4 and its solutions were also just posted to the
Question Bank and
Tutorial Page. Lecture 18 was just posted on the
lecture
page.

21/04/03:There will be a voluntary Q&A session on
Thur, April 24, 2003, 9:40AM, in the 271 classroom.

23/04/03: Assignment 4 was just posted on the web
page. It will be due on May 6, 2003. Also a box has been placed at the
front of the computer science department administration office for collection
of assignment 3. By 5 PM, Thursday, April 24, 2003, please either put
your assignments in the box or email them to me. As before, make sure
that you keep copies of your solutions.

There will be a voluntary Q&A session on Tuesday, April 29, 2003, 9:40AM, in
the 271 classroom (note that Thursday, 01/05/03, is a public holiday so
there will be no Q&A session then). Also, there will be no tutorial
posted this week.

Lectures 19 and 20 were just posted to the
lecture
page. A revised version of Lecture 14 (last
page changed) and Lecture 18 (pp. 12 and 25 changed) were also posted.
After consideration of the time remaining in the semester I have decided
not to teach the supplementary material on Heuristics and Approximation this
year. If you are interested in this topic, please read Chapter 35 of the
CLRS textbook and let me know if you have any questions. Also, Question
Bank 5 and selected solutions have just been posted to the
Question Bank and
Tutorial Page.
 Due
to requests the duedate for Assignment 4 has been delayed one day. It is now
due Wednesday, May 7, at 5:00 PM. As usual, there will be a box in the CS
department office for submitting your assignments. Alternatively, you
can email them to me at golin@cs.ust.hk
or slip them under my office door.
 There
will be NO Q&A session on Tuesday, May 6. If you want to ask questions,
I will however, hold office hours
that afternoon, Tuesday May 6, 34PM
in my office, 3559
(other times by email appointment).
 Thursday,
May 8, is a public holiday. If there is interest, though, I
can hold a Q&A session or office hours on that day. If you would like
this, please send me email.

Assignment 5 was just posted to this page. It will be due on May 19, 2003
at 5PM. Solutions to assignments 3 and 4 were also just posted.

There will be a
voluntary Q&A session on Tuesday, May 13, 2003, 9:40AM, in the 271
classroom. Assignments 2 and 3 will be returned at that time. If
you do not come to the Q&A you can pick the assignments up from my office.

There will be a
voluntary Q&A session on Thursday, May 15, 2003, 9:40AM, in the 271 classroom.

I will hold one review session next week to answer any questions you might
have in your exam preparation. The date of the review session will be
set depending upon student response to email sent out (and will be posted
soon).

Information on the final exam contents can be found below in the
exam section of this page.
 The last review session before the final will be
held
Tuesday May 20, 11AM12:20PM, Room 3598.
Please note that the time is NOT the normal 271 class time and the room is NOT
the normal 271 class room. The purpose of this review session is to answer any
questions you might have so, please prepare in advance for this.
Also, you can pick up all of your marked assignments, including
assignment 4, at the review session.
 The
assignment marks
and extra
credit marks have all been posted on the web. Please check the marks
to see that they are correct and let me know ASAP if you think that there is
an error in the record. A zero mark indicates that the indicated assignment
was not submitted.
 Due to student requests, the due date of
Assignment 5 has been delayed one day. Assignment 5 is now due at 5PM on
Tuesday, May 20.
 Solution
to Assignment 5 has just been posted below.
 The review session on Tuesday was the last formal session of the semester.
If you still have question please stop by my office to ask me in person (it is
better to send email to golin@cs.ust.hk
first to make sure that I will be around when you want to come).
Alternatively, especially if you prefer explanation sin Cantonese,
Leung Yiu Cho, one of the TAs, will hold office hours, from 23PM on
Friday, May 23rd and Monday, May 26, in room 4209.

The
assignment marks
have just been updated to include the assignment 5 grades. You
can pick up your marked assignment 5 (along with any other assignments you
have not yet picked up) from Mr. Leung Yiu Cho, one of the 271 TAs,
during his office hours from 23PM on Monday, May 26, in room 4209.
 I will
hold one last office hour from 34PM on Monday May 26, to answer any last
minute questions you might have. (Please note that you will not be able
to pick up your assignments from me during this hour; as mentioned above,
your assignments will be available from the TA between 23).

Lecture 19 was just slightly revised. The revision was the correction of
a typographical error in the first line of the proof on page 33.
 I was
asked by a student whether you would be allowed to bring a review sheet into
the exam. The answer is no. You may not bring any materials other
than pens and/or pencils into the exam. No review sheets, calculators or
pocket PCs will be allowed.
 New 02/06/03:
Please check out all of the
marks
of the assignments and grades. I will hold office hours in my room
(3559) on Tuesday June 3, 2009 at which you can took a look at your final
exams. Please also note that that final course grades will be assigned
late afternoon on June 3rd so this will be your only time to ask questions
about your exam grades. Finally, if you do plan on checking out
your exam, please download the exam
solutions
first and take a look at them so you'll have a better idea as to what
the solutions are.
Course Overview:
This course presents the fundamental techniques for
designing efficient computer algorithms, proving their correctness, and
analyzing their running times. General topics include review of asymptotics,
mathematical analysis of algorithms (summations and recurrences), algorithm
design techniques (such as divideandconquer, dynamic
programming, and greedy algorithms), graph algorithms (minimum spanning trees
and shortest paths) and NPcompleteness.
Textbook
(available at the HKUST bookstore and on reserve in the library)
T. Cormen, C. Leiserson, R. Rivest,
C. Stein. Introduction to
Algorithms, Second Edition, McGraw Hill and MIT Press, 2001. QA76.6 C662
2001.
References
(all available on reserve in
the library)
 Jon Bentley. Programming pearls (2nd Ed).
AddisonWesley, 2000. QA76.6 .B454 2000.
 Michael R. Garey and David S. Johnson. Computers and
intractability : a guide to the theory of NPcompleteness. W. H. Freeman,
1979. QA267.7 .G37 1979.
 Robert Sedgewick. Algorithms in C++ (3rd ed) Volumes 1 and 2.
AddisonWesley, 1998. QA76.73.C153 S38 1998.
 Jurai Hromkovic. Algorithmics for hard problems : Introduction to
combinatorial optimization, randomization, approximation, and
heuristics. SpringerVerlag, 2001 QA76.9.A43 H76 2001.
Course Work:
Course work will consist of 4 homework assignments and 2
exams (a midterm and a comprehensive final). Homeworks are to be turned in by
the start of class on the due date. No late homeworks will be
accepted. (So turn in what you have by the start of class.) In
exceptional circumstances (illness, university business, or religious
observances) extensions may be granted. However, all extensions must be approved
by me before the due date.
The primary benefit to working on homeworks is to prepare for the exams; exam questions are often variants of homework problems. For this reason
I encourage you to spend time alone thinking about each problem and your
approach in solving it. You are allowed to and encouraged to
discuss homework problems with your classmates. However, you
must write up the solutions on your own. In particular:
 Homework solutions must be written in your own words (not copied or
modified from someone else's writeup).
 You must understand your solution and its derivation. (I may ask you to
explain your solution to me.)
 You must acknowledge your collaborators (whether or not they are
classmates) or any other outside sources on each homework.
Failing to do any of these will be considered plagiarism, and may result in a
failing grade on an assignment or in the course in the course and notification for appropriate disciplinary
action. As an example of plagiarism, if we find that your solution
is copied, without attribution, from something on the web, this would be
treated as plagiarism. On the other hand, if you report that you found a
solution to a similar problem on the web, tell where this was, and write
down the solution in your own words, this would be fine.
As a courtesy to the graders, homeworks should be written
neatly. Poorly written work will not be graded. When writing
algorithms be sure not only that your solution is correct, but also that it is
easy for the grader to understand why your solution is correct. Part of your
grade will be based not only on correctness, but also on the clarity,
simplicity, and elegance of your solution.
Assignments should either be emailed to the instructor at
golin@cs.ust.hk or submitted to the
computer science department office (room 3528) by 5:00PM of the due date.
When submitting to the department office please specify (and write on your
paper) that this is meant for Dr Golin. Please also keep copies of
your homeworks so that, if there is a mixup, I can ask you to
resubmit it.
Exam Schedule:

Date/Time 
Venue 
Midterm 
CANCELLED 

Final Exam 
27/05/03 (TUE) 08:3011:30 (am) 
Room LG1031 (new room) 
Old Exams: To assist you in
preparing for the here are copies of last semester's
midterm and
final. Please
note that the material taught during the first few weeks last semester was
slightly different than this semester's so you did not learn the
background to question 2 of the midterm.
Exams Coverage:
 The final exam will cover ALL material covered in the lecture notes (120)
presented on the class
lecture
page.
 Lectures 18, 19, 20 (NP completeness) will only be worth 10% of the final
exam
 The exam format will be similar to last semester's
midterm and
final. Please
note that the material taught during the first few weeks last semester was
slightly different than this semester's so you did not learn the
background to question 2 of the midterm. Please also note that last semester's
final was not comprehensive (i.e., did not cover a lot of the material from
the first half of the term). This semester's final will be
comprehensive. All material in lectures 120 can be on the exam.
Grading (this has been modified due
to the class cancellations)
5 assignments 
30% (6% each) 
Midterm 
CANCELLED 
Final 
70% 
No makeups will be given for midterm and final unless prior approval is
granted by the instructor, or you are in unfavorable medical condition with
physician's documentation on the day of the examination. In addition, being
absent at the final examination results in automatic failure of the course
according to university regulations, unless prior approval is obtained from the
department head.
Lectures 
Days 
Time 
Room 
Tue & Thu 
9:00  10:20 
4502  
Tutorials 
Section 
Day 
Time 
Room 
TA 
1A 
Fri 
10:00  10:50 
4475 
Yeung Siu Yin 
1B 
Fri 
11:00  11:50 
4475 
Leung Yiu Cho  