ADA Unit-2 Notes

on
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.

Comments

Post a Comment