CSCI5610 Advanced Data Structures


Course code CSCI5610
Course title Advanced Data Structures
Course description This course introduces advanced techniques for designing data structures with strong theoretical guarantees. Topics to be covered include (i) generic methods such as partial persistence, logarithmic rebuilding, weight balancing, filtering, independent sampling, bit twiddling, tabulating, etc., and (ii) specific structures such as the interval tree, the priority search tree, cuckoo hashing, the van Emde Boas structure, range min structures, locality sensitive hashing, the suffix tree, the count-min sketch, etc.
本科旨在介紹用以設計具有優秀理論保證的數據結構的高級技術。要討論的主題包括(i)一系列通用的方法,如partial persistence,logarithmic rebuilding, 權重平衡,過濾,獨立採樣,bit twiddling,打表等,以及(ii)一系列具體的結構,如區間樹,優先搜索樹,cuckoo結構, van Emde Boas結構,局部敏感哈希,後綴樹,count-min sketch等。
Unit(s) 3
Course level Postgraduate
Pre-requisites CSCI2100 or ESTR2102 (for UG students)
Semester 1 or 2
Grading basis Graded
Grade Descriptors A/A-:  EXCELLENT – exceptionally good performance and far exceeding expectation in all or most of the course learning outcomes; demonstration of superior understanding of the subject matter, the ability to analyze problems and apply extensive knowledge, and skillful use of concepts and materials to derive proper solutions.
B+/B/B-:  GOOD – good performance in all course learning outcomes and exceeding expectation in some of them; demonstration of good understanding of the subject matter and the ability to use proper concepts and materials to solve most of the problems encountered.
C+/C/C-: FAIR – adequate performance and meeting expectation in all course learning outcomes; demonstration of adequate understanding of the subject matter and the ability to solve simple problems.
D+/D: MARGINAL – performance barely meets the expectation in the essential course learning outcomes; demonstration of partial understanding of the subject matter and the ability to solve simple problems.
F: FAILURE – performance does not meet the expectation in the essential course learning outcomes; demonstration of serious deficiencies and the need to retake the course.
Learning outcomes At the end of the course of studies, students will have acquired the ability to
1. Understand the theory behind the techniques covered;
2. Utilize those techniques to design new data structures for solving other related problems.
(for reference only)
Essay test or exam: 75%
Homework or assignment: 25%
Recommended Reading List [1] Peter Brass: Advanced Data Structures. Cambridge University Press, 2008, ISBN-13: 978-0521880374.
[2] Bernard Chazelle: Filtering Search: A New Approach to Query-Answering. SIAM J. Comput. 15(3): 703-724 (1986).
[3] Bernard Chazelle: A Functional Approach to Data Structures and Its Use in Multidimensional Searching. SIAM J. Comput. 17(3): 427-462 (1988).
[4] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein: Introduction to Algorithms, 3rd Edition, MIT Press, ISBN: 978-0-262-03384-8.
[5] Graham Cormode, S. Muthukrishnan: An improved data stream summary: the count-min sketch and its applications. J. Algorithms 55(1): 58-75 (2005).
[6] James R. Driscoll, Neil Sarnak, Daniel Dominic Sleator, Robert Endre Tarjan: Making Data Structures Persistent. J. Comput. Syst. Sci. 38(1): 86-124 (1989).
[7] Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48(4): 723-760 (2001).
[8] Piotr Indyk, Rajeev Motwani, Prabhakar Raghavan, Santosh Vempala:Locality-Preserving Hashing in Multidimensional Spaces. STOC 1997: 618-625.
[9] Robert Krauthgamer, James R. Lee: Navigating nets: simple algorithms for proximity search. SODA 2004: 798-807.
Jürg Nievergelt, Edward M. Reingold: Binary Search Trees of Bounded Balance. SIAM J. Comput. 2(1): 33-43 (1973).
[10] Mark H. Overmars: The Design of Dynamic Data Structures. Lecture Notes in Computer Science 156, Springer 1983, ISBN 3-540-12330-X.
[11] Rasmus Pagh, Flemming Friche Rodler: Cuckoo hashing. J. Algorithms 51(2): 122-144 (2004).


CSCIN programme learning outcomes Course mapping
Upon completion of their studies, students will be able to:  
1. identify, formulate, and solve computer science problems (K/S);
2. design, implement, test, and evaluate a computer system, component, or algorithm to meet desired needs (K/S);
3. receive the broad education necessary to understand the impact of computer science solutions in a global and societal context (K/V);
4. communicate effectively (S/V);
5. succeed in research or industry related to computer science (K/S/V);
6. have solid knowledge in computer science and engineering, including programming and languages, algorithms, theory, databases, etc. (K/S);
7. integrate well into and contribute to the local society and the global community related to computer science (K/S/V);
8. practise high standard of professional ethics (V);
9. draw on and integrate knowledge from many related areas (K/S/V);
Remarks: K = Knowledge outcomes; S = Skills outcomes; V = Values and attitude outcomes; T = Teach; P = Practice; M = Measured