COMP171 Data Structures and Algorithm Section L2, Fall 2005 Lectures: Tuesday & Thursday 16:30 每 17:50 Rm 4334 Office Hours: Tuesday & Thursday 14:00 每 16:00 Rm 3508 Huamin Qu (Email: huamin@cs.ust.hk. Office: Rm 3508. Phone: 23586985 )  Syllabus 
Schedule
& Notes  Assignments
& Exams Newsgroup  Links &
Applets  





Name 
Email 
Room 
Office Hour 
Professor 
Huamin QU 

3508 
Tuesday & Thursday 14:00 每 16:00 
TA 
Ming Yuen CHAN 

4204 

TA 
Yihai SHEN 
shenyh@cs.ust.hk 


Section 
Day 
Time 
Room 
TA 
2A 
Monday 
12:00 每 13:50 
1511 
Ming Yuen CHAN 
2B 
Wednesday 
12:00 每 13:50 
1511 
Ming Yuen CHAN 
2C 
Friday 
12:00 每 13:50 
1511 
Yihai SHEN 
From the unveristy course catalog:
Asymptotic notations. Performance measurement. Sorting and searching: algorithms and lower bound. Abstract data types and classes. Data structures: heaps, search trees, tries, and hashing. Graphs: representation, depthfirstsearch, and breadthfirstsearch.
References:
Late Policy: For written assignments, 20% will be deducted for one day
late submissions. Assignments later than 1 day will not be accepted. For
programming assignments, you are allowed to submit ONE assignment late (up to
1 week) among the three assignments. Use this credit wisely  when you have
several assignments due at the same time; you are advised not to use it for
the first programming assignment.
Illness: If you have a medical reason for handing in your
assignment late or for missing an examination, you should let us know as soon
as possible.
Midterm and Final: No makeups 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.
Collaboration: You
are encouraged to collaborate in study groups. However, you must write up
solutions on your own for written assignments, and write your own programs
for programming assignments. You must also acknowledge your collaborators in
your submitted assignment for each problem, whether or not they are
classmates. Other cases will be dealt with as plagiarism.
Plagiarism: If you cheat on an assignment, both you and the person
who helped you will receive a lower grade or the fail grade F. Please refer
to the class notes for details.
Lecture 
Date 
Topic 
Slides 

Other 
01 
Sep. 1 
Introduction & C++ (1) 
Weiss 1 


02 
Sep. 6 
C++ (2) 
Weiss 1.5 

03 
Sep. 8 
Basic Math and Recursion 
Weiss 1.1 1.2 


04 
Sep. 13 
Linked List 
Weiss 3 

05 
Sep. 15 
Linked Lists (2) 
Weiss 3 


06 
Sep. 20 
Stack and Queue 
Weiss 3.3 3.4 
HW1 out 

07 
Sep. 22 
Algorithm and Analysis 
Weiss 2 


08 
Sep. 27 
Algorithm and Analysis(2) 
Weiss 2 


08 
Sep. 29 
Insertion Sort, Merge Sort 
Weiss 7.1 7.2 7.6 


10 
Oct. 4 
Quick Sort 
Weiss 7.7 
HW2 out 

11 
Oct. 6 
Heap and Heap Sort 
Weiss 7.5 


12 
Oct. 13 
Heapsort 2 
Weiss 7.5 


13 
Oct. 18 
Lower Bound of Sorting and Radix Sort 
Weiss 7.9 
HW2 due 

14 
Oct. 20 
Binary Search Tree 
Weiss 4.3 but 4.3.6 is optional 


15 
Oct. 25 
AVL Tree 
Weiss 4.4 


16 
Oct. 27 
AVL Tree 



17 
Nov. 1 
AVL Tree 



18 
Nov. 3 
B+ Tree 
Weiss 4.7 


19 
Nov. 8 
B+ Tree 2 
Weiss 4.7 


20 
Nov. 10 
Graph 
Weiss 9.1 9.3 


21 
Nov. 15 
Breadthfirst search 

Weiss 9.3.1 

22 
Nov. 17 
Depthfirst search 



23 
Nov. 22 
Connected Component 



24 
Nov. 24 
Topological Sort 



25 
Nov. 29 
Hashing 
Weiss 5.1 每 5.4 


26 
Dec. 1 
String Matching (not in exam syllabus) 



27 
Dec. 6 
String Matching 2 (not in exam syllabus) 


Assignments will be collected at the beginning of the class. We will use CASS  Course Assignmen Submission System.

Distributed 
Due Date 
Solution 
Sep. 20 
Oct. 4 


Oct. 4 
Oct. 18 


Oct. 29 
Nov. 13 


Nov. 11 
Nov. 29 


Lab Assignment 3 
Nov. 15 
Nov. 29 
