Discrete Structure · Unit 5
Recurrence Relations and Recursion
Exam-focused notes for Recurrence Relations and Recursion (Discrete Structure, BIT152): what the TU syllabus asks and how it has actually been tested, with 6 solved past questions from this unit.
What this unit covers
- Recursively defined functions
- Linear homogeneous recurrence relations
- Linear nonhomogeneous recurrence relations
- Solving recurrence relations with initial conditions
- Characteristic equations
- Fibonacci sequence
Solving recurrence relations with initial conditions
Solve the recurrence relation $a_n = a_{n-1} + a_{n-2}$ with initial conditions $a_0 = 0$ and $a_1 = 1$. [5]
- Recurrence: $an = a{n-1} + a{n-2}$ - Initial conditions: $a0 = 0$, $a1 = 1$ --- This is a linear homogeneous recurrence with constant coefficients. Assume $an = r^n$: $$r^n = r^{n-1} + r^{n-2}$$ Divide by $r^{n-2}$: $$r^2 = r + 1 \implies r^2 - r - 1 = 0$...
Full solved answer →What are the uses of randomized algorithm? Find the solution to the recurrence relation $a_n = 6a_{n-1} - 11a_{n-2} + 6a_{n-3}$ with the initial conditions $a_0 = 2$, $a_1 = 5$ and $a_2 = 15$. [2+8]
A randomized algorithm uses random choices during its execution to influence its behavior. Common uses include: 1. Primality Testing - Fast probabilistic tests such as Miller-Rabin and Solovay-Strassen for very large numbers. 2. Randomized Quicksort - Rando...
Full solved answer →Define randomized algorithm with an example. Solve the recurrence relation $a_n = -4a_{n-1} - 4a_{n-2}$ for $n \ge 2$, with initial condition $a_0 = 0$ and $a_1 = 1$. [3+7]
- Recurrence: $an = -4a{n-1} - 4a{n-2}$ for $n \geq 2$ - Initial conditions: $a0 = 0$, $a1 = 1$ All required data present. --- A randomized algorithm is an algorithm that makes one or more of its decisions based on random numbers generated during execution....
Full solved answer →Recursively defined functions
What is recursively defined function? Suppose that f is defined recursively by f(0) = 3, f(n + 1) = 2f (n) +3. Find f(1), f(2), f(3), and f(4). [5]
- Base case: $f(0) = 3$ - Recursive step: $f(n+1) = 2f(n) + 3$ - Required: $f(1), f(2), f(3), f(4)$ A recursively defined function is a function defined in terms of itself, using two components: 1. Base case: the value of the function at a starting argument...
Full solved answer →Linear nonhomogeneous recurrence relations
What is linear nonhomogeneous recurrence relation of degree k with constant coefficients? Find all the solutions of the recurrence relation a, 4a+n. Also find the solution of the relation with initial condition a, 1.[10]
- Recurrence (interpreted): $an = 4a{n-1} + n$ - Initial condition: $a1 = 1$ Note: the question text is garbled ("a, 4a+n" and "a, 1"). The standard textbook reading is $an = 4a{n-1} + n$ with $a1 = 1$, which is used here. --- A linear nonhomogeneous recurr...
Full solved answer →Linear homogeneous recurrence relations
Define recurrence relation. What do you mean by linear homogeneous recurrence of degree $k$ with constant coefficients? What is the solution of the recurrence relation $a_n = a_{n-1} + a_{n-2}$ with initial conditions $a_0 = 0$ and $a_1 = 1$? [10]
- Recurrence: $an = a{n-1} + a{n-2}$ - Initial conditions: $a0 = 0$, $a1 = 1$ --- A recurrence relation for a sequence $\{an\}$ is an equation that expresses each term $an$ in terms of one or more of the preceding terms $a{n-1}, a{n-2}, \ldots, a{n-k}$, val...
Full solved answer →Make Unit 5 stick
Practice BIT152 with flashcards & quizzes