Solve using greedy algorithm

1. a precise description of the algorithm and, if helpful, pseudocode,

2. a proof of correctness,

3. an analysis of running time and space.

Consider this logic puzzle: If Mr. Smith has a dog, then Mrs. Brown has a cat. If Mr. Jones has a dog, then he has a cat too If Mr. Smith has a dog and Mr. Jones has a cat, then Mrs. Peacock has a dog. If Mrs. Brown and Mr. Jones share a pet of the same species, then Mr. Smith has a cat All the men have dogs What can we say about who has what kind of pet? We can encode the problem as Boolean variables. We write s, j. b, p for Boolean variables that are true if Smith, Jones, Brown, or Peacock respectively have a dog, and s, 3, B, P for Boolean variables that are true if they have a cat. The puzzle can then be exressed as the following ogical formula: (s) A A formula that is a conjunction of implications in which no variable is complemented is called a Horn formula. To solve the puzzle, we need to find a satisfying truth assignment for the variables in the formula. While the problem of Boolean Satisfability (SAT) is in general intractable, Boolean satisfiability for Horn clauses - HornSAT-can be solved in linear time using a greedy algorithm Consider this logic puzzle: If Mr. Smith has a dog, then Mrs. Brown has a cat. If Mr. Jones has a dog, then he has a cat too If Mr. Smith has a dog and Mr. Jones has a cat, then Mrs. Peacock has a dog. If Mrs. Brown and Mr. Jones share a pet of the same species, then Mr. Smith has a cat All the men have dogs What can we say about who has what kind of pet? We can encode the problem as Boolean variables. We write s, j. b, p for Boolean variables that are true if Smith, Jones, Brown, or Peacock respectively have a dog, and s, 3, B, P for Boolean variables that are true if they have a cat. The puzzle can then be exressed as the following ogical formula: (s) A A formula that is a conjunction of implications in which no variable is complemented is called a Horn formula. To solve the puzzle, we need to find a satisfying truth assignment for the variables in the formula. While the problem of Boolean Satisfability (SAT) is in general intractable, Boolean satisfiability for Horn clauses - HornSAT-can be solved in linear time using a greedy algorithm