COMP 171 Data Structures and Algorithms
2002 Fall Term, MWF 12:00-12:50, Rm 2503
Dr. Dekai WU, Rm 3539, 2358-6989, dekai@cs.ust.hk
Announcements<- Important
Always check www.cs.ust.hk/~dekai/171 for up-to-the-minute announcements.
Policies

TEXTBOOK

Thomas H. CORMEN, Charles E. LEISERSON, Ronald L. RIVEST, and Clifford STEIN. Introduction to Algorithms, Second Edition. MIT Press, 2001.

TAS

WONG Ka Wah (cs_wkw@stu.ust.hk), Ken LEE Wing Kuen (cswkl@ust.hk), SHEN Yihai (shenyh@ust.hk)

OFFICE HOURS

You are welcome to knock on the doors of the instructor any time. The TAs' office hours are M 14:30-15:30, Rm 4211 for WONG Ka Wah, and Th 12:30-13:30, Rm 4208 for Ken LEE Wing Kuen.

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 two midterms and one final exam.  Each exam is worth 250 points.

HOMEWORK

All programming assignments must be submitted at the beginning of lecture on the due date. Programming assignments must be in C++ on Unix and will be collected electronically under an arrangement to be announced later. Unless prior approval is granted by the instructor, late homeworks will be penalized 1 point per minute during lecture (after lecture ends there is no guarantee that you can deliver the homework). Sorry, in the interest of fairness, exceptions cannot be made.

Written assignments are not graded. Many exam questions will be similar to written assignment questions, so it is to your own benefit to do them.

Programming assignments will account for a total of 250 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
Schedule Wk Event Reading Assignments
2002.09.04 1 Lecture: Intro Ch1
2002.09.06 1 Lecture: Analysis of algorithms: Binary search vs linear search Ch2
2002.09.09 2 Lecture: Analysis of algorithms: Time complexity: asymptotic notations, growth rate Ch3
2002.09.11 2 Lecture: Analysis of algorithms: Upper and lower bounds Ch3
2002.09.13 2 Lecture: Sorting: Insertion sort Ch2
2 Tutorial: Templates in C++, Supplement, C++ examples (swap, pair, vector)
2002.09.16 3 Lecture: Sorting: Insertion sort analysis Ch2
2002.09.18 3 Lecture: Sorting: Mergesort Ch2
2002.09.20 3 Lecture: Sorting: Mergesort: recurrence, analyzing recursive programs Ch2
3 Tutorial: Asymtotic notation review & selection sort
2002.09.23 4 Lecture: Sorting: Quicksort Ch7 a0
2002.09.25 4 Lecture: Sorting: Quicksort variations (Lewis & Denenberg and Weiss versions) Ch7 a0 due
2002.09.27 4 Lecture: Sorting: Quicksort partition analysis Ch7 wa1
4 Tutorial: Mergesort & quicksort review, Supplement
2002.09.30 5 Lecture: Sorting: Quicksort analysis, pivot selection, cutoffs Ch7
2002.10.02 5 Lecture: Sorting: Binary trees (heapsort preliminaries) Ch6
2002.10.04 5 Lecture: Sorting: Heapsort (priority queue) Ch6
5 Tutorial: In-class exercise to practice analysis review, Model answer
2002.10.07 6 Lecture: Sorting: Heapsort variations Ch6
2002.10.09 6 Lecture: Sorting: Lower bound based on the decision tree model Ch8 a1
2002.10.11 6 Lecture: Sorting: Radix sort as an application of linked list and queue Ch8
6 Tutorial: In-lab exercise on the CS Unix environment (Rm 4213), Heapsort
2002.10.14 7 Public Holiday
2002.10.16 7 Lecture: Review
2002.10.18 7 Midterm 1 (covers up to & including Radix Sort)
7 Tutorial: Extra office hours: Ka Wah (W 16:00-18:00, Rm 4211), Ken (Th 17:00-19:00, Rm 4208)
2002.10.21 8 Lecture: Dictionaries: Binary search tree, definitions Ch12
2002.10.23 8 Lecture: Dictionaries: Binary search tree, traversals Ch12
2002.10.25 8 Lecture: Dictionaries: Binary search tree, lookup, insertion Ch12
8 Tutorial: Midterm 1 solutions
2002.10.28 9 Lecture: Dictionaries: Binary search tree, deletion Ch12
2002.10.30 9 Lecture: Dictionaries: Red-black tree, insertion Ch13 a1 due
2002.11.01 9 Lecture: Dictionaries: Red-black tree, insertion Ch13
9 Tutorial: Binary search tree review
2002.11.04 10 Lecture: Dictionaries: Red-black tree, deletion Ch13
2002.11.06 10 Lecture: Dictionaries: Red-black tree, deletion Ch13
2002.11.08 10 Lecture: Dictionaries: 23-tree, insertion none
10 Tutorial: Red-black tree review
2002.11.11 11 Lecture: Dictionaries: 23-tree, deletion none
2002.11.13 11 Lecture: Dictionaries: B-tree, insertion Ch18 a2
2002.11.15 11 Lecture: Dictionaries: B-tree, deletion Ch18
11 Tutorial: More red-black tree review; C++ template examples (List.hpp, List.cpp)
2002.11.18 12 Lecture: Dictionaries: B-tree, issues, 234-tree Ch18
2002.11.20 12 Lecture: Hashing: Digital data, Hash tables and functions Ch11 a2 due
2002.11.22 12 Lecture: Hashing: Collision resolution: separate chaining Ch11 wa1 solutions
12 Tutorial: B-tree review; extra; questions for Midterm 2
2002.11.25 13 Midterm 2
2002.11.27 13 Lecture: Hashing: Collision resolution: linear probing Ch11
2002.11.29 13 Lecture: Hashing: Collision resolution: double hashing, hashing functions Ch11
13 Tutorial: Midterm 2 solutions
2002.12.02 14 Lecture: Tries, Patricia trees, De la Briandias trees, variants -
2002.12.04 14 Lecture: Tries: digital search trees; Graphs: Definition, representation Ch22
2002.12.06 14 Lecture: Graphs: Depth-first search, breadth-first search, topological sort Ch22
14 Tutorial: Hash table, trie review
2002.12.13 15 Midterm 3 (Final, 12:30-15:30, LG1)

dekai@cs.ust.hk
Last update: 2002.12.04