My best pastime is completing crossword puzzles. Backtracking, the game's recursive feature, can be compared to a selective tree navigation method. Backtracking enables people to deal with circumstances where other approaches would produce an impossible amount of options. In a crossword puzzle, the player can go back and try an alternative after reversing the most recent decision in order to continue looking for potential word entries. When a player runs out of choices, the decision that brought about that result is retracted, and a new option is attempted at that node. It is noteworthy that, if the game ends up at the root without further options, then there are no possible combinations for the puzzle.
Recursive Elements
Ideally, backtracking gradually develops the candidates to the solution and ignores each partial candidate once it determines that C cannot form the correct solution. Consider the following recursive elements as an illustration of this concept.
If no more Choices Then Stop
Else
Make an alternative C
Consider the remaining alternatives
If necessary, unmake alternative C
Fibonacci’s rabbits
Recursion has also found extensive application in the Fibonacci sequence. The sequence is named after Leonardo Fibonacci, an ancient mathematician who related the sequence with a pair of fictional pair of rabbits which reproduce another pair after every month. If the pattern continues, the number of rabbits in each month would be the total number of bunnies and rabbits in the previous month. Assuming Rn and Tn are the number of adults and the total number of pairs in the nth month respectively,
This rule expands my process calculation to a general rule that after every 12 months there would be 144 pairs of rabbits.
Well-Ordering Theorem
According to the Well-ordering theorem, every set of positive integers contains a least element (Rosen, 2014). The principle is equivalent to the Axiom of Choice, which maintains that if a set exists without a rule governing the sets, then a new set can be formed by selecting an item from each set. For instance, if there are infinite pigeonholes with each containing at least a pigeon, then at least one hole must contain more than one pigeon.
Word of the day
In this chapter, I learned about the following key concepts
Recursion
Recursive Algorithms
The binary search algorithm
The Big-O notation
In week three discussion, the algorithm is the word of the day. An algorithm is a finite set of instructions for solving different problems such as sorting a list or searching an element in a set. An example is the binary search algorithm which locates the position of a target value in a sorted array. Similarly to the recursive definition, the binary search compares the target value to the middle element of the set and if unequal, the half which does not contain the target is eliminated; the search recurs until it is successful.
Further, the number of operations that algorithms use can be estimated using the Big-O notation. With this notation, it is possible to determine whether it is realistic to use a particular algorithm to solve an issue as the number of input increases. Additionally, the notation can be used to compare algorithms in order to determine the most efficient as the data size grows. For example, using the Big-O notation, it can be seen that the algorithm 100n2+18n+4 uses fewer operations when n is large than in n3. The advantage of using the big-O notation is that the growth of a function can be estimated without the issue of constant multipliers or small order terms.
References
Rosen, K. (2014). Discrete Mathematics and Its Applications (7th Ed.). : McGraw - Hill Education.
