TAILIEUCHUNG - Lecture Data Structures: Lesson 34

Lecture Data Structures: Lesson 34 provide students with knowledge about equivalence relations; electrical connectivity, where all connections are by metal wires, is an equivalence relation; the disjoint sets view; dynamic equivalence problem; discuss a solution to the union/find problem that for any sequence; . | Equivalence Relations A binary relation over a set S is called an equivalence relation if it has following properties 1. Reflexivity for all element x S x x 2. Symmetry for all elements x and y x y if and only if y x 3. Transitivity for all elements x y and z if x y and y z then x z The relation is related to is an equivalence relation over the set of people Lecture Data Structure Dr. Sohail Aslam Equivalence Relations The relationship is not an equivalence relation. It is reflexive since x x and transitive since x y and y z implies x z it is not symmetric since x y does not imply y x. Equivalence Relations Electrical connectivity where all connections are by metal wires is an equivalence relation. It is clearly reflexive since any component is connected to itself. It is symmetric because if component a is connected to component b then b must be electrically connected to a. It is transitive since if component a is connected to component b and b is connected to c then a is connected to c. The Disjoint Sets View An equivalence relation over a set S can be viewed as a partitioning of S into disjoint sets. Each set of the partition is called an equivalence class of all elements that are related . The Disjoint Sets View Every member of S appears in exactly one equivalence class. To decide if a b we need only to check whether a and b are in the same equivalence class. This provides a strategy to solve the equivalence problem. Dynamic Equivalence Problem If the relation is stored as a two-dimensional array of booleans then of course this can be done in constant time. The problem is that the relation is usually not explicitly defined but rather implicitly defined. Ahmed Haaris Qasim Omar Asim Saad Haaris T T T Saad T T Ahmed T Omar T Asim T T Qasim T Dynamic Equivalence Problem As an example suppose the equivalence relation is defined over the five-element set a1 a2 a3 a4 a5 . There are 25 pairs of elements each of which is related or not. 30 pairs 5 self- pairs 25

• Cơ sở dữ liệu
• Lecture Data Structures
• Bài giảng Cấu trúc dữ liệu
• Data structures
• Equivalence relations
• The disjoint sets view
• Dynamic equivalence problem
• Lecture ECE 250
• Lecture Algorithms and data structures
• Algorithm analysis
• Graph algorithms
• Memory allocation
• Programming assignments
• Data structures organize data
• Resource constraints
• Abstract data types
• Tree data structure
• Lecture Data structures and algorithms
• Data structures and algorithms
• Cấu trúc dữ liệu và giải thuật
• Abstract data type
• Bài giảng Cấu trúc dữ liệu và thuật toán
• Fundamental data structures
• Computational complexity
• Complexity of algorithms
• Data structure
• Pointers to structures
• Pointers to classes
• Josephus problem
• List data structures
• Doubly linked list
• Circularly linked list
• Code for simulation
• Priority queue
• Tree data structures
• Computer science
• Design of data structures
• Algorithms in Java
• AVL trees
• Binary search trees
• Red black trees
• Splay trees
• Dynamic programming