Cse 100 Advance Data Struct Notes

Cse 100 Advance Data Struct Notes

  • Submitted By: azntom08
  • Date Submitted: 06/30/2010 11:07 PM
  • Category: Technology
  • Words: 22180
  • Page: 89
  • Views: 724

ADVANCED DATA STRUCTURES

Walt Burkhard
Computer Science and Engineering 100

Spring 2010

Soft Reserves

Student Center A Room 122

Table of Contents –
1. Abstract Data Types 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.

14. 15. Floyd-Williams Priority Queue Implementation 16. Binomial Queue Implementation . . . . . . 17. Union Find aka Disjoint Subsets . . . . . . 18. 19. 20. 21. 22. 23. Traveling Salesman Problem . . . . . . . Trees . . . . . . . . . . . . . . . . Treaps Dictionary Data Type Implementation AVL Dictionary Data Type Implementation .

. . . . Move To The Front List Maintenance . Array Structures . . . . . . . . . . Table Data Type . . . . . . . . . Open Addressing – Double Hashing . . Brent & Ordered Hashing . . . . . . Binary Tree Hashing . . . . . . . . Pass Bits & Double Hashing . . . . . Approximate Set Membership . . . . Priority Queue Data Type . . . . . . Binary tree structured Priority Queues .

. . . List Data Type . . . . . Algorithm Performance . . Topological Sorting . . .

. . . .

. . . .

. . . .

. . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . Modified Skip Lists . . . . . . . . . . . B & B+Trees . . . . . . . . . . . . . .
i

. . . . . . . . . . . . . . . . . . . . . . .

. .1 . .3 . .8 . 11 . 15 . 18 . 23 . 30 . 35 . 40 . 45 . 52 . 56 . 58 . 64 . 66 . 72 . 80 . 83 . 92 . 98 . 111 . 114

Design Choices for Data Type Implementation II STORAGE SYSTEM ARCHITECTURES storage space or memory manipulation done by the “client program” or “data type program?” The client program creates a data instance to store. The client program allocates and manages storage space; this tends to clutter the client program algorithmic structure. However, the data type program need only store a reference pointer to the object; sometimes metadata is stored. The data type program allocates and manages storage space for the data. Pertinent facts such as size must be...

Similar Essays