| CS
840 - Winter 2013 Topics in Data Structures: Time and Space Efficiency in Data Structures Instructor: I. Munro |
Class Time: Wednesdays and Fridays 10:30 - 11:50 in DC 2586
Office:
DC2343
Phone: ext 34433
email: 
- priority queues under various models of computation
- succinct data structures
- structures for external memory, including cache oblivious structures
- persistent data structures
- techniques on search trees such as splay trees
- and a variety of other issues depending on interests of the class.
Prerequisites: Solid undergraduate knowledge of basic data structures required (like CS 240). An "algorithms course" like CS 666 is helpful, but is not completely necessary.
Organization:
First part of each segment - lectures primarily by the instructor.
Later classes in each segment - discussion of papers led by members of the class. (to the extent this is possible depending on class size)
Last couple of weeks - project presentations
Requirements for Credit: Three or four problem sets/paper reviews (45% of marks) and a course project (55%, including particpation in presentations of others).
Project: Read several recent papers, attempt to improve or apply results, and report in class and written report. Projects can involve implementations.
Text etc: There is no formal text; most of the material covered will come from the recent literature, most notably through several survey articles that will be made available. A standard advanced level text such as Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein will, however, be a useful reference.
Assignments
Assignment 1 Due Friday, February 1 Assignment 2 Due Friday, March 8Class Notes, Papers Relating to Specific Classes and Powerpoint Presentations
Unit 1: Introduction and van Emde Boas P.
van Emde
Boas et
al: Design and Implementation of an Efficient Priority Queue. Math
Systems
Theory, 10:99-127 (1977).
Unit 2: Self Organizing Linear Search
D.
D. Sleator
and R. E. Tarjan:
Amortized efficiency of list update and paging rules.
Communications of the ACM, 28(2):202-208, 1985. J.I. Munro: On the Competitiveness of Linear
Search.
Self Organizing Linear Search: Powerpoint
Unit 5: Self Organizing Binary Search Trees
D.
D. Sleator
and R. E. Tarjan:
Self-adjusting binary search trees. Journal of the ACM,
32:652-686, 1985.Unit 6: Persistent Data Structures
H. Kaplan, Persistent Data StructuresSome Other References:
D.
Gusfield,
Algorithms on Strings, Trees, and Sequences, Cambridge
University Press, 1997.
G. Franceschini, R. Grossi, L. Pagli and J.I.
Munro: Imlicit B-Trees: New Results for the Dictionary Problem.
FOCS
2002.
E.D. Demaine, A. Lopez-Ortiz and J.I. Munro
:Adaptive Set Intersections, Unions, and Differences
A.
Borodin and R. ElYaniv:
Online Computation and Competitive Analysis, Cambridge University
Press, 1998.
Ching Law, Charles E. Leiserson: A New
Competitive Analysis of Randomized Caching. ISAAC 2000: 35-46