|
COMP171 Data Structures and Algorithm
Section L2, L3 Spring 2009
|
|
Schedule and Notes:
|
Week
|
Date
|
Topic
|
Slides
|
Readings
|
Assignment
Schedule
|
|
1
|
Feb 2
|
Programming paradigms,
|
intro.ppt,
procedural.ppt
oop.ppt
generic.ppt
|
Weiss 1
|
|
|
|
dynamic objects in C++, linked lists
|
pointerDynamic.ppt
listLinkedList.ppt
|
|
|
|
2
|
Feb 9
|
Class,
|
|
Weiss 1.5
|
|
|
|
Abstract Data Type,
|
abstractDataType.ppt
and summary
ADT.ppt
|
Weiss 1.1 1.2
|
|
|
3
|
Feb 16
|
(Templates).
|
dynamicClass.ppt
|
Weiss 3
|
|
|
|
Linear structures:
List, Stack, and Queue
Induction and
recursion (brief review)
|
stackQueue.ppt
mathRecursion.ppt
|
Weiss 3
Weiss 2
|
|
|
|
Algorithm Analysis
and Asymptotic Notations
|
analysis.ppt
|
Weiss 2
|
|
|
4
|
Feb 23
|
|
|
|
|
|
|
Sorting Analysis :
Merge sort, insertion
sort
|
insertionMergesort.ppt
|
Chapter 7.2,
7.2.3Chapter 7.6
|
|
|
5
|
Mar 2
|
quick
sort
|
quicksort.ppt
|
Weiss 7.7
|
|
|
|
radix
sort
|
radixsort.ppt
|
Weiss 7.5
|
|
|
6
|
Mar 9
|
Trees and Binary
Search Trees
|
bst.ppt
|
Weiss 4.3 but 4.3.6
is optional
|
|
|
|
Heaps and heap sort.
|
heapsort.ppt
|
Weiss 7.5
|
|
|
7
|
Mar 16
|
AVL Trees
|
avl1.ppt
|
Weiss 4.4,
Weiss 4.7
|
|
|
|
|
avl2.ppt
|
Weiss 4.7
Some Practice
|
|
|
8
|
Mar
23
|
B+ Trees
|
btree1.ppt
|
|
|
|
|
|
btree2.ppt
|
|
|
|
9
|
Mar 30
|
Midterm Review
|
Past
Exam Sample pdf
Past
Exam Sample Solution pdf
Midterm Review Slides
|
|
|
|
|
Midterm exam: April 12, 7-9h
pm, LTA and B.
|
|
|
|
|
10
|
Apr 5,
|
Graph, Breadth-first
search
|
graphBfs1.ppt ,
bfs2
|
Weiss 9.1 9.3
|
|
|
|
|
|
Weiss 9.3.1
|
|
|
11
|
Apr 20
|
Depth-first search
|
dfs.ppt
|
|
|
|
|
Connected Components
|
Connectivity-directed_graph.ppt
|
|
|
|
12
|
Apr 27
|
|
|
|
|
|
|
Topological Sort
|
|
|
|
|
13
|
May 4
|
Hashing
|
hashging.ppt
|
Weiss 5.1 – 5.4
|
|
|
|
|
|
|
|
|
14
|
May 11
|
Review for Final Exam
|
Review
checklist
A
sample final exam with solutions
|
|
|
|
|
|
|
|
|
|
|
Course Description: (From
the HKUST 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):
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
|
Grading Scheme:
- Two (2) Written
Assignments 8% (4% each)
- Three (3) Lab
Assignments 27% (9% each)
- Midterm Exam 25%
- Final Exam 40%
(schedule: to be announced)
Assignments will be collected at the beginning of the class. We will use CASS
- Course Assignment Submission System.
|