COMP171 Data Structures and Algorithm

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: 2358-6985 )

Announcements:

Marks for the final exam have been sent to you by email.
Marks for all assignments and midterm are released (Dec. 20). Two checking sessions for PA2 and PA3 will be arranged on Dec. 21 and Dec. 22. The time and location has been sent to you by email.
Updated Marks with WA2 is released.
The due date for Programming Assignment 3 is postponed to December 6 (Tuesday), 23:59.
Programming Assignment 3 is released. Due December 4, 23:59.
Written Assignment 2 is released. Due November 29 (in class).
Updated scores for Programming Assignement 1, Written Assignment1, and Midterm
Marks for Midterm and Written Assignment 1 is released.
Programming Assignment 2 is released. The due date is November 13, 23:59.
Solution to written assignment 1 is released.
The midterm is postponed to Saturday, Oct 29, 6-8pm. The venue for L2 students is LT B.
Written Assignment 1 is released. The due date is Oct. 18, 2005.
How to submit your assignment?
Sample code, Input and output for assignment 1 is now available
Programming assignment 1 is posted
Add links to Applets (Sep. 8, 2005)
Add slides of Tutorials in “Schedule & Notes” (Sep. 8, 2005)
There will be no tutorial session this week (Sep. 1, 2005)

Contacts:

	Name	Email	Room	Office Hour
Professor	Huamin QU	huamin@cs.ust.hk	3508	Tuesday & Thursday 14:00 – 16:00
TA	Ming Yuen CHAN	pazuchan@ust.hk	4204
TA	Yihai SHEN	shenyh@cs.ust.hk

Tutorials:

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

Course Description:

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, depth-first-search, and breadth-first-search.

Textbook (available at the HKUST bookstore and on reserve in the library):

Data Structures and Algorithm Analysis in C++, Mark Allen Weiss (Addison Wesley) [ Errata] [Source Code] [HKUST library record]

References:

Data Structures, Algorithms, and Applications in C++, Sahni (McGraw-Hill)
Data Structures and Algorithms in C++, Goodrich, Tamassia, and Mount (John Wiley & Sons)
Data Structures and the Standard Template Library, Collins (McGraw-Hill)
Introduction to Algorithms, Thomas H. Cormen, Charles Leiserson, Ronald Rivest (McGraw-Hill)
Thinking in C++ 2nd Edition by Bruce Eckel

Tentative Syllabus:

Review of C++: pointers, recursion, advanced C++ features
Review of abstract data types: linked list, queue, and stack.

(polynomial manipulation?) as an application of linked list
(radix sort?) as an application of queue.
(infix to postfix conversion?) as an application of stack.

Introduction to algorithm and its analysis.

Binary search versus linear search.
Time complexity: asymptotic notations, growth rate.
Upper and lower bounds.

Sorting

Insertion sort
Mergesort: recurrence, analyzing recursive programs.
Quicksort
Heapsort (priority queue).
Lower bound based on the decision tree model.
Radix sort.

Dictionary as an abstract data type.

Trees and searching.
Binary search trees, lower bound, tree traversals, insertion and deletion.
AVL tree.
B+ tree.

Graphs

Definition, representation, modeling tool.
Depth-first search, breadth-first search.

Hashing.

Hash tables and functions.
Collision resolution: separate chaining.
Collision resolution: linear probing and double hashing.

Grading Scheme:

Two Written Assignments 8% (4% each)
Three Lab Assignments 27% (9% each)
Midterm Exam 25%
Final Exam 40%

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 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.

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.

University Policy:

Tentative Class Schedule:

Lecture	Date	Topic	Slides	Readings	Other
01	Sep. 1	Introduction & C++ (1)	intro.ppt C++.ppt	Weiss 1
02	Sep. 6	C++ (2)	pointers.ppt	Weiss 1.5	Tutorial_1.ppt
03	Sep. 8	Basic Math and Recursion	recursion.ppt	Weiss 1.1 1.2
04	Sep. 13	Linked List	Linked List.ppt	Weiss 3	Tutorial_2.ppt
05	Sep. 15	Linked Lists (2)	list_stl.ppt	Weiss 3
06	Sep. 20	Stack and Queue	stack-queue.ppt	Weiss 3.3 3.4	HW1 out
07	Sep. 22	Algorithm and Analysis	algo.ppt	Weiss 2
08	Sep. 27	Algorithm and Analysis(2)	algo_2.ppt	Weiss 2
08	Sep. 29	Insertion Sort, Merge Sort	isort-msort.ppt	Weiss 7.1 7.2 7.6
10	Oct. 4	Quick Sort	qsort.ppt	Weiss 7.7	HW2 out
11	Oct. 6	Heap and Heap Sort	heapsort_1.ppt	Weiss 7.5
12	Oct. 13	Heapsort 2	heapsort_2.ppt	Weiss 7.5
13	Oct. 18	Lower Bound of Sorting and Radix Sort	radixsort.ppt	Weiss 7.9	HW2 due
14	Oct. 20	Binary Search Tree	bst.ppt	Weiss 4.3 but 4.3.6 is optional
15	Oct. 25	AVL Tree	avl-tree.ppt	Weiss 4.4
16	Oct. 27	AVL Tree
17	Nov. 1	AVL Tree	avl-tree2.ppt
18	Nov. 3	B+ Tree	btree1.ppt	Weiss 4.7
19	Nov. 8	B+ Tree 2	btree2.ppt	Weiss 4.7
20	Nov. 10	Graph	graph_bfs.ppt	Weiss 9.1 9.3
21	Nov. 15	Breadth-first search		Weiss 9.3.1
22	Nov. 17	Depth-first search	dfs.ppt
23	Nov. 22	Connected Component	directed_graph.ppt
24	Nov. 24	Topological Sort
25	Nov. 29	Hashing	hashing.ppt	Weiss 5.1 – 5.4
26	Dec. 1	String Matching (not in exam syllabus)	string_matching.ppt
27	Dec. 6	String Matching 2 (not in exam syllabus)	string_matching2.ppt

Assignment Schedule:

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

	Distributed	Due Date	Solution
Programming Assignment 1	Sep. 20	Oct. 4
Written Assignment 1	Oct. 4	Oct. 18
Programming Assignment 2	Oct. 29	Nov. 13
Written Assignment 2	Nov. 11	Nov. 29
Lab Assignment 3	Nov. 15	Nov. 29

Exam Schedule:

Midterm Exam: Oct. 22
Final Exam: TBA

Applets:

Java Applets by R. Mukundan
Sorting algorithms (app1 (with recursive mergesort), app2 (with iterative mergesort))
Radix sort applet
Heap sort applet [ click (1) start, (2) no, (3) ok, and (4) start]
Binary tree
AVL animation
AVL tree applet
B+ tree animation
B+ tree Applet
Hash applet
Depth-first search
Breadth-first search
Many other applets