Announcements |

Always check www.cs.ust.hk/~dekai/171
for up-to-the-minute announcements. |

Policies |

There will be two midterms and one final exam. Each exam is worth 250 points.

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.

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