CPSC 411: Quiz 6
October 2, 2008

Printed Name:________________________________________

"On my honor, as an Aggie, I have neither given nor received unauthorized aid on this academic work. In particular, I certify that I have not received or given any assistance that is contrary to the letter or the spirit of the collaboration guidelines for this assignment."

Signature:___________________________________________

  1. (2 pts) Consider the linked list representation using weighted union for the disjoint sets data type. Which of the 3 operations (Make-Set, Find-Set, Union) is the most time-consuming?





  2. (2 pts) Consider the forest of trees representation for the disjoint sets data type without weighted union or path compression. Which of the 3 operations (Make-Set, Find-Set, Union) is the most time-consuming?





  3. (1 pt) Consider the forest of trees representation for the disjoint sets data type with weighted union and path compression. Which of the 3 operations (Make-Set, Find-Set, Union) is the most time-consuming?