COMP 271 Design and Analysis of Algorithms [3-1-0:3]
2005 Spring Term

Lecture 1, TTh 13:30-14:50, Rm 3008
Dr. Dekai WU, Rm 3539, 2358-6989, dekai@cs.ust.hk

Lecture 2, TTh 16:30-17:50, Rm 2464
Gerhard TRIPPEN, 2358-8834, trippen@cs.ust.hk

PU Ruonan / Stanley LEUNG Man Fung / Tom HUANG Jinxin, Tutorial 1A, Fr 14:00-14:50, Rm 1505
PU Ruonan / Stanley LEUNG Man Fung / Tom HUANG Jinxin, Tutorial 1B, Fr 15:00-15:50, Rm 1505

ZHOU Hong / CHEN Shi / CHEN Tao, Tutorial 2A, Fr 16:00-16:50, Rm 2502
ZHOU Hong / CHEN Shi / CHEN Tao, Tutorial 2B, Fr 17:00-17:50, Rm 2465

Announcements<- Important

Always check http://www.cs.ust.hk/~dekai/271/ for up-to-the-minute announcements.
Tutorial info is at http://course.cs.ust.hk/comp271/tutorials/.
Newsgroup is hkust.cs.class.271. Always read before asking/posting/emailing your question.

2005.05.11 ASSIGNMENT 3 will be due May 17 at 3pm in 4209 (L19/20) (ps pdf). Please review the PLAGIARISM and COLLABORATION policy below CAREFULLY.

2005.03.31 ASSIGNMENT 2 will be due Apr 19 (ps pdf). Please review the PLAGIARISM and COLLABORATION policy below CAREFULLY.

2005.03.30 MIDTERM is on Apr 12, 18:30-20:30. Lecture 1 is in Rm 3008, and Lecture 2 is in Rm 3007. There will be no other lecture that day.

2005.03.03 ASSIGNMENT 1 will be due Mar 17 (ps pdf). Please review the PLAGIARISM and COLLABORATION policy below CAREFULLY.

Policies

ACADEMIC CALENDAR DESCRIPTION

Time and space complexity analysis of algorithms. Design paradigms: dived-and-conquer, greedy algorithms, dynamic programming. Graph algorithms: searching and backtracking, connectivity, biconnectivity, minimum spanning tree, shortest path. NP-completeness. Prerequisite: COMP 171/171H.

TEXTBOOKS

  1. Introduction to Algorithms (2nd Edition), by Cormen, Leiserson, Rivest, and Stein. MIT Press, 2001.

REFERENCE BOOKS

  1. Dave MOUNT: Lecture Notes.
  2. Programming Pearls (2nd Edition), by Jon BENTLEY. Addison-Wesley, 2000.
  3. Computers and intractability: A guide to the theory of NP-completeness, by Michael R. GAREY and David S. JOHNSON. W.H. Freeman, 1979.

TAS AND TUTORIALS

All information for tutorials is at http://course.cs.ust.hk/comp271/tutorials/.

OFFICE HOURS

You are welcome to knock on the doors of the instructor any time. The TA's office hours are TBA.

REQUIRED SIGNATURE ON HONOR STATEMENT

To receive a passing grade, you are required to sign an honor statement acknowledging that you understand and will uphold all policies on plagiarism and collaboration.

PLAGIARISM

All materials submitted for grading must be your own work. You are advised against being involved in any form of copying (either copying other people's work or allowing others to copy yours). If you are found to be involved in an incident of plagiarism, you will receive a failing grade for the course and the incident will be reported for appropriate disciplinary actions.

COLLABORATION

You are encouraged to collaborate in study groups. However, you must write up solutions on your own. You must also acknowledge your collaborators in the write-up for each problem, whether or not they are classmates. Other cases will be dealt with as plagiarism.

EXAMINATIONS

No reading material is allowed during the examinations. No make-ups will be given 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.

There will be one midterm worth 350 points, and one final exam worth 450 points.

ASSIGNMENTS

All programming assignments must be submitted at the beginning of lecture on the due date. Late assignments cannot be accepted. Sorry, in the interest of fairness, exceptions cannot be made.

There will be 3 assignments, which together will account for a total of 200 points.

GRADE GUARANTEES

The total points you can achieve in the course is 1000.  The course will be graded on a curve, but subject to the following guarantees:
 
If you achieve 900 points you will receive no less than a A grade.
800 points B
700 points C
600 points D

Theme Date Wk Event Notes Chapters Assignments
Introduction and Review Feb 01 1 lec Introduction (ps pdf) 1.1-4.2
Feb 03 lec Review (slides reference)
Divide and Conquer Feb 08 2 lec Maximum contiguous subarray problem (ps pdf)  
Feb 10 Lunar New Year
  Feb 15 3 lec Polynomial multiplication (ps pdf)  
  Feb 17 lec Randomized selection and randomized quicksort (ps pdf) 7
  Feb 22 4 lec Deterministic linear-time selection (ps pdf) 9.2, 9.3
Graph Algorithms Feb 24 lec Depth-first search and its applications (ps pdf) 22.3
Mar 01 5 lec Depth-first search and its applications (cont)
  Mar 03 lec Minimum spanning tree and Prim's algorithm (ps pdf) 23
  Mar 08 6 lec Minimum spanning tree and Prim's algorithm (cont)
  Mar 10 lec Kruskal's algorithm (ps pdf) 23
  Mar 15 7 lec Disjoint set union and find (ps pdf) 21.3
  Mar 17 lec Dijktra's algorithm (ps pdf) 24.3 A1 due (ps pdf)
Dynamic Programming Mar 22 8 lec 0-1 Knapsack (ps pdf)  
Mar 24 lec 0-1 Knapsack (cont)
  Mar 29 8 lec Matrix chain multiplication (ps pdf written notes (jpeg) 1 2 3 4) 15.2, 15.3
  Mar 31 lec All-pairs shortest paths (ps pdf written notes (jpeg) 1 2 3 4 5 6 7 8) 25.1, 25.2
Apr 5 9 Ching Ming Festival
  Apr 7 lec All-pairs shortest paths (cont)
Apr 12 10 exam Midterm (18:30-20:30, Rm3008 for L1, Rm3007 for L2)
Greedy Algorithms Apr 14 lec Fractional Knapsack (ps pdf written notes (jpeg) 1 2 3 4) 16.2
  Apr 19 11 lec Huffman coding (ps pdf written notes ps pdf) 16.3 A2 due (ps pdf)
  Apr 21 lec Huffman coding (cont)
More Algorithms Apr 26 12 lec String matching (ps pdf written notes ps pdf) 32.1, 32.4
Apr 28 lec String matching (cont)
NP-completeness May 03 13 lec Introduction to NP (ps pdf) 34.1, 34.2
May 05 lec Introduction to NP (cont)
May 10 14 lec Introduction to NP (cont)
  May 12 lec Polynomial time reduction (ps pdf written notes (jpeg) 1 2 3 4) 34.3, 34.5
  May 17 15 (15:00, Rm 4209, Lifts 19/20) A3 due (ps pdf)
May 21 exam Final (08:30-11:30, LG4204)

dekai@cs.ust.hk
Last update: 2005.05.11