COP 5536 / AD 711R

Advanced Data Structures

University of Florida

Course Syllabus

The specific topics and associated readings are:

1.     Amortized complexity (Web)

2.     External sorting & tournament trees (Sections 7.10.1, 7.10.2, and 5.8)

3.     Buffering (Section 7.10.3)

4.     Run generation & optimal merge patterns (Huffman trees) (Sections 7.10.4 and 7.10.5)

5.     Priority queues and merging (Section 5.6)

6.     Double ended priority queues (Sections 9.1 and 9.2, Web)

7.     Leftist trees, Binomial heaps and Fibonacci heaps (Sections 9.3, 9.4, and 9.5)

8.     Pairing heaps (Web)

9.     Static and dynamic weighted binary search trees (Section 10.1)

10. AVL-trees (Section 10.2)

11. 2-3 and 2-3-4 trees (Sections 10.3 and 10.4)

12. Red-black trees (Section 10.5)

13. B-trees (Section 10.6)

14. Splay trees (Section 10.7)

15. Tries and digital search trees (Sections 10.8 and 10.9)

16. Suffix trees (readings)

17. Bloom filters (Section 10.10)

18. Segment trees (readings)

19. Priority search trees (readings)

20. k-d trees (readings)

21. Quad and oct trees (readings)



A more detailed outline of each of the lectures given last year is given below. We will follow at approximately the same rate this semester. For this semester's exam dates, see Exam Dates & Exam Syllabus.

Lecture

Content

Reading

1

Amortized complexity.

Web resource.

2

Amortized Complexity.

Web resource.

3

Introduction to external sorting.

Section 7.10.1.

4

Introduction to external sorting.

Section 7.10.1.

5

Tournament trees & k-way merging.

Sections 5.8 and 7.10.2.

6

Run generation.

Section 7.10.4.

7

Optimal merging of runs.

Section 7.10.5.

8

Buffering.

Sections 7.10.3.

9

Double-ended priority queues. General methods.

Sections 9.1, 9.2, and Web resource..

10

Double-ended priority queues. Min-max heaps, deaps, interval heaps.

Sections 9.1, 9.2, and Web resource..

11

Leftist trees.

Section 9.3.

12

Binomial heaps.

Section 9.4.

13

Binomial heaps.

Section 9.4.

14

Fibonacci heaps.

Section 9.5.

15

Fibonacci heaps.

Section 9.5.

--

Exam 1.

 

16

Pairing heaps.

Web resource.

17

Binary Search Trees.

Section 5.7.

18

Optimal binary search trees.

Section 10.1.

19

AVL trees.

Section 10.2.

20

AVL trees

Section 10.2.

21

2-3 trees.

Section 10.3.

22

2-3-4 trees.

Section 10.4.

23

Red-black trees.

Section 10.5.

24

Red-black trees.

Section 10.5.

25

Red-black trees.

Section 10.5.

26

B-Trees.

Section 10.6

27

B-trees.

Section 10.6.

--

Exam 2.

 

28

Splay Trees.

Section 10.7.

29

Splay Trees.

Section 10.7.

30

Binary Tries.

Section 10.8.

31

Compressed Binary Tries.

Section 10.8.

32

Patricia.

Section 10.8.

33

High-order tries.

Sections 10.9 and Web Resource.

34

Suffix Trees.

Web Resource.

35

Bloom Filters.

Section 10.10.

36

Segment Trees.

 

37

Priority Search Trees.

References.

38

Priority Search Trees.

References.

39

Multidimensional Search Trees.

References.

40

Quad Trees.

References.

 

Instructional Material

The text for the course is:
Fundamentals of data structures in C++, by E. Horowitz, S. Sahni, and D. Mehta, W. H. Freeman, 1995.



Some of the lectures rely on the following Web material:

1.     Amortized Complexity

2.     Pairing Heaps

3.     Double Ended Priority Queues

4.     Tries

5.     Suffix Trees



For the remaining lectures, you will need the following papers:

1.     F.P. Preparata and M.I. Shamos, "The Segment Tree" , Computational Geometry, Springer-Verlag, pp. 13-15, 1985.

2.     E. McCreight, "Priority Search Trees", SIAM J. Computing, Vol. 14-2, pp. 257-276, 1985.

3.     J. Bentley, "Data Structures for Range Searching", ACM Computing Surveys, Vol. 11-4, pp. 397-409, 1979.

4.     Hanan Samet, "The Quadtree and Related Hierarchical Data Structures", ACM Computing Surveys, Vol. 16-2, pp. 187-229, 1986.



A fairly exhaustive reference on the subject of data structures is:

Handbook of data structures and applications. Dinesh Mehta and Sartaj Sahni, Editors. Chapman and Hall/CRC, 2005.

 

Exam Dates & Syllabus



All exams are CLOSED BOOK

First Exam ... June 8

Amortized complexity, external sorting, double-ended priority queues, leftist trees, binomial heaps.

Second Exam ... July 6.

Fibonacci heaps, pairing heaps, binary search trees, AVL trees, 2-3 trees, 2-3-4 trees, and red-black trees.

Final Exam ... Aug. 5.


Everything else.

 

Instructor

Professor Sartaj Sahni

Office Hours: None.

Location: E301B Computer Science & Engineering Building

Telephone: 352 392 1527

Fax: 352 392 1220

sahni@cise.ufl.edu