Get premium membership and access questions with answers, video lessons as well as revision papers.
Dovetailing, in algorithm design, is a technique that interweaves different computations, performing them essentially simultaneously. Algorithms that use dovetailing are sometimes referred to as dovetailers.
Consider a tree that potentially contains a path of infinite length: if a depth-first search is performed in this environment, the search may move down an infinite path and never return, potentially leaving part of the tree unexplored. However, if a breadth-first search is used, the existence of an infinite path is no longer a problem: each node is visited in a branching manner according to its distance from the root, so an infinite path will only impact the part of the search travelling down that path.
We can regard this tree as analogous to a collection of programs; in this case, the depth-first approach corresponds to running one program at a time, moving to the next only when the current program has finished running. In the case where one of the programs runs for an infinite amount of time, this transition will never happen. The breadth-first approach of visiting each child on the same level of the tree corresponds to dovetailing, where a single step is performed for every program before moving to the next. Thus, progress is made in each program, regardless of the potential existence of a program of infinite runtime.
In the case of an infinite number of programs, all potentially infinitely long, neither the breadth-first nor depth-first would be sufficient to ensure progress on all programs. Instead, the following technique can be used: perform the first step of the first program; next, perform the first step of the second program and the second step of the first program; next, perform the first step of the third program, the second step of the second program, and the third step of the first program; and so on.
ksm254 answered the question on October 10, 2018 at 20:08
- Discuss the role of the school as socializing agent in the moral development of the adolescent(Solved)
Discuss the role of the school as socializing agent in the moral development of the adolescent.
Date posted: May 21, 2018. Answers (1)
- Give two reasons for airing articles after ironing(Solved)
Give 2 reasons for airing articles after ironing
Date posted: April 24, 2018. Answers (1)
- Outline factors to consider when buying a house(Solved)
Outline factors to consider when buying a house.
Date posted: April 12, 2018. Answers (1)
- Outline factors to consider when building a house(Solved)
Outline factors to consider when building a house.
Date posted: April 12, 2018. Answers (1)
- What is a bruise? (Solved)
What is a bruise?
Date posted: April 12, 2018. Answers (1)
- Name various parts of the dermis(Solved)
Name various parts of the dermis.
Date posted: April 12, 2018. Answers (1)
- Outline ways in which one can enhance their personal appearance(Solved)
Outline ways in which one can enhance their personal appearance.
Date posted: April 12, 2018. Answers (1)
- Outline the management of fractures(Solved)
Outline the management of fractures.
Date posted: April 6, 2018. Answers (1)
- What is a sprain?(Solved)
What is a sprain?
Date posted: April 6, 2018. Answers (1)
- Explain why Home Science is an applied and an integrated science?(Solved)
Explain why Home Science is an applied and an integrated science?
Date posted: April 6, 2018. Answers (1)
- Describe the importance of natural resource management in kenya(Solved)
Describe the importance of natural resource management in kenya
Date posted: March 5, 2018. Answers (1)
- Preventative measures to be taken to prevent the spread of water-borne diseases(Solved)
Preventative measures to be taken to prevent the spread of water-borne diseases.
Date posted: March 1, 2018. Answers (1)
- Advantages of using leftover food(rechauffe cookery) to produce a family meal(Solved)
Advantages of using leftover food(rechauffe cookery) to produce a family meal.
Date posted: March 1, 2018. Answers (1)
- Factors that affect individual nutritional requirements in meal planning. (Solved)
Factors that affect individual nutritional requirements in meal planning.
Date posted: March 1, 2018. Answers (1)
- Disadvantages of renting a house(Solved)
Disadvantages of renting a house.
Date posted: March 1, 2018. Answers (1)
- Factors that affect normal foetal development. (Solved)
Factors that affect normal foetal development.
Date posted: March 1, 2018. Answers (1)
- Reasons for coating food before deep frying(Solved)
Reasons for coating food before deep frying.
Date posted: March 1, 2018. Answers (1)
- Three methods of finishing darts(Solved)
Three methods of finishing darts
Date posted: March 1, 2018. Answers (1)
- Advantages of home based care of the sick(Solved)
Advantages of home based care of the sick
Date posted: March 1, 2018. Answers (1)
- Functions of an opening in a garment(Solved)
function of an opening in a garment.
Date posted: March 1, 2018. Answers (1)