Forward-Backward (Bidirectional) Search :

a) Eloise claims to be a descendant of Benjamin Franklin. Which would be the easier way to verify Eloise's claim: By showing that Franklin is one of Eloise's ancestors or by showing that Eloise is one of Franklin's descendants? Why? Estimate the branching factor for each direction of the search.

b) In a simplified version of Eloise's claim, suppose you are interested in purchasing a racehorse that is said to be in the "first or second lineage" of an outstanding female racehorse (filly), that is, each of its ancestors is the first or second offspring of its parent. In short, whether searching forward or backward, there will be two successors of each node. Assume you are using Backtrack to search the tree - estimate the total number of probes needed to find a node that is 10 levels deep in the tree if you do a strictly forward search or strictly backward search.Estimate the total work if you work from both directions simultaneously and search for a common point in the middle.