一、課程說明 (Course Description)



This course introduces some classical and smart methods to store the data 

so that we can answer questions about the data efficiently. As an example,

let us imagine that we have the exam scores of all students, and from 

time to time different student would ask how many other students

get a higher score than him/her. In order to speed up the query, one

may store the scores in a sorted order rather than in a random order.

[In fact, an even better scheme exists!]



Our focus will be on both the theoretical performance and the practical

implementation of the data structures. 





二、指定用書 (Text Book)  

    Introduction to Algorithms, 3rd edition, the MIT press, 2009

    by T. Cormen, C. E. Leiserson, and R. L. Rivest 



三、參考書籍 (References)   

    1. Algorithms in C++, (or Algorithms in Java), by R. Sedgewick

    2. Fundamentals of Data Structures in C++, by Horowitz and others

    3. The Art of Computer Programming, by D. E. Knuth



四、教學方式 (Teaching Method)  

    Lectures and Tutorials (Lectures in English)



五、教學進度 (Syllabus)



Tentative topics to be covered:



 1. Growth of Functions



 2. Basic Data Structures

    [Arrays:  Prefix Sum, Range Min Query ]



 3. Traversals

    Graph: [BFS, DFS : Reachability, Connected Components (queue/stack) ] 

    Tree:  [Pre-order, Post-order :  Expression Conversion ]



 4. Heaps

    [Priority Queues : Ordering Jobs in a Server ]



 5. Searching Set Data

    (a) Hashing            (Chaining, Open Addressing)

    (b) Binary Search Tree (BST)   

    (c) Balanced BST       (RB tree, AVL tree)

    (d) B-tree



 6. Advanced Topics :



    I.  Specific Queries for Set Data

    (a) Perfect Hashing

    (b) Rank

    (c) Y-fast Trie



    II. Data Structures for String Data

    (a) Digital Trie

    (b) Suffix Tree, Suffix Arrays



    III. Data Structures for Geometric Data

    (a) Priority Search Tree        (3-sided range query)

    (b) Interval Tree, Segment Tree (stabbing query)



六、成績考核 (Evaluation)   

    To be announced