COMP271 Design and Analysis of Algorithms
Spring 2003

Mordecai Golin, Room 3559, Tel 2358-6993, Email golin@cs.ust.hk

Syllabus  Lectures (schedule and notes) Assignments  Question Banks & Tutorials Marks (Extra Credit)


Important Notes:  Revised  Sunday, May 25, 2003:

Due to the SARS situation and following the HKUST academic-affairs office recommendations we will  make the following changes in the COMP271 class this semester:

  1. There will be no more face-to-face lectures this semester. That is,  all formal classes will be cancelled (unless the SARS situation unexpectedly quickly improves)
  2. All Tutorial sessions will also be cancelled (although we will continue  posting tutorial assignments for you to practice on).
  3. 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.
  4. The instructor will hold office-hours in his office (room 3559) during the scheduled class hours: tuesday/thursday 9:00-10-20. 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 office-hours.
  5. 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.
  6. Assignment 2 is due Tuesday April 15, 2003.  Assignment 3 is due  Thursday, April 24, 2003.
  7. 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.
  8. 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.
  9. 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. 
  10. 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.
  11. 21/04/03:There will be a voluntary Q&A session on Thur, April 24, 2003, 9:40AM, in the 271 classroom.
  12. 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.
  13. 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.
  14. 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.
  15. Due to requests the due-date 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.
  16. 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, 3-4PM in my office, 3559 (other times by email appointment).
  17. 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.
  18. 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.
  19. 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.
  20. There will be a voluntary Q&A session on Thursday, May 15, 2003, 9:40AM, in the 271 classroom.
  21. 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).
  22. Information on the final exam contents can be found below in the exam section of this page.
  23. The last review session before the final will be held Tuesday May 20, 11AM-12: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.
  24. 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. 
  25. 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.
  26. Solution to Assignment 5 has just been posted below.
  27. 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 2-3PM on Friday, May 23rd and Monday, May 26, in room 4209. 
  28. 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 2-3PM on Monday, May 26, in room 4209.
  29. I will hold one last office hour from 3-4PM 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 2-3).
  30. 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.
  31. 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.
  32. 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 divide-and-conquer,  dynamic programming, and greedy algorithms), graph algorithms (minimum spanning trees and shortest paths) and NP-completeness.


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)

  1. Jon Bentley. Programming pearls (2nd Ed). Addison-Wesley, 2000. QA76.6 .B454 2000.
  2. Michael R. Garey and  David S. Johnson. Computers and intractability : a guide to the theory of NP-completeness. W. H. Freeman, 1979. QA267.7 .G37 1979.
  3. Robert Sedgewick.  Algorithms in C++ (3rd ed) Volumes 1 and 2. Addison-Wesley, 1998. QA76.73.C153 S38 1998.
  4. Jurai Hromkovic. Algorithmics for hard problems :  Introduction to combinatorial optimization,  randomization, approximation, and heuristics. Springer-Verlag, 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:

 

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.


Assignment Schedule:

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.

     Distributed Revised  Due Date  
Assignment 1     20/02/03 27/02/03  06/03/03 Solution
Assignment 2     18/03/03      15/04/03 Solution
Assignment 3     04/04/03    21/04/04  24/04/03 Solution
Assignment 4     22/04/03    07/05/03 Solution
Assignment 5     08/05/03    20/05/03 Solution


Exam Schedule:

   Date/Time  Venue
Midterm CANCELLED  
Final Exam 27/05/03 (TUE)    08:30-11: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:   

  1. The final exam will cover ALL material covered in the lecture notes (1-20) presented on the class lecture page
  2. Lectures 18, 19, 20 (NP completeness) will only be worth 10% of the final exam
  3. 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 1-20 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 make-ups 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


 

Contacts 

Name  Office  Ext.  Email  Office Hours 
Mordecai Golin 3559  6993 golin@cs.ust.hk Anytime instructor is in office or by appointment
Leung Yiu Cho     cscho@cs.ust.hk TBA
Yeung Siu Yin      siuyin@cs.ust.hk TBA