ADA Unit-2 Notes

https://drive.google.com/file/d/18MITjoUO14gHrb7OWiqnVLjOGDNnx814/view?usp=sharing

The document titled UNIT-2 focuses on two primary computer science topics: Disjoint Sets and Backtracking algorithms.

1. Disjoint Sets

A disjoint set is a collection of sets where no element exists in more than one set.

• Tree Representation: Sets are represented as trees where each element is a node and sets are identified by the root of their respective trees.
• Core Operations:
  • Find(i): Determines which set contains element $i$ by identifying the root of its tree.
  • Union(i, j): Combines two disjoint sets by making one tree a subtree of the other.
• Performance Improvements:
  • Weighting Rule: To avoid tall, "degenerate" trees, the smaller tree is always made a subtree of the larger one during a union.
  • Collapsing Rule: During a Find operation, all nodes on the path to the root are flattened to point directly to the root, speeding up future operations.
• Algorithms: The document provides specific algorithms for SimpleUnion, SimpleFind, WeightedUnion, and CollapsingFind.

2. Backtracking

Backtracking is a systematic search method for finding solutions to problems that satisfy specific criteria, often visualized as a modified depth-first search of a state space tree.

• Key Constraints:
  • Explicit Constraints: Rules that restrict each variable to a specific set of values.
  • Implicit Constraints: Rules determining how variables must relate to each other to satisfy the problem's goal.
• Terminology:
  • Problem State: Each node in the search tree.
  • E-node: The "expansion" node currently being explored.
  • Dead Node: A node that cannot lead to a solution and is no longer explored.

3. Problems Solved via Backtracking

The document details several classic problems and their backtracking implementations:

• N-Queens Problem: Placing $N$ queens on an $N \times N$ chessboard so no two queens attack each other (same row, column, or diagonal).
• Sum of Subsets: Finding all subsets of a given set of positive numbers that sum to a specific target value 'm'.
• Graph Coloring: Assigning colors to graph vertices such that no two adjacent vertices share the same color, using at most 'm' colors.
• Hamiltonian Cycles: Finding a path in a graph that visits every vertex exactly once and returns to the starting vertex.

For each problem, the document provides detailed logic, constraints, complexity analysis, and recursive algorithms.