5.1 Sequences and Strings

Basic Skills

1. Define a sequence and give an example of a numeric sequence used in computing.
2. What is the difference between a sequence and a string? Provide an example of each.
3. Consider the sequence defined by the rule [latex]a_{n} = 2n + 1[/latex]. Write the first five terms of this sequence.
4. A string is defined as a finite sequence of characters. How many characters are in the string "Data123!"? List their positions.
5. Identify whether each of the following is a valid sequence or not. Justify your answer:

1. 1. [latex]3, 6, 9, 12, \dots[/latex]
   2. “It’s a me, Mario!”
   3. [latex]\{x \in \mathbb{R} | x^{2} = -1 \}[/latex]

Applications

6. A software application logs user activity timestamps as a sequence of integers representing seconds since login. If the timestamps are recorded as [latex]5, 10, 15, 20, \dots[/latex], write a general formula for the [latex]n[/latex]th term and explain how this sequence helps in analyzing user behaviour.
7. A string compression algorithm replaces repeated characters with a count and the character (e.g., "aaabb" becomes "3a2b"). Given the string "hhhhheeeellllppp", describe the sequence of character counts and how it can be used to reconstruct the original string.
8. A network monitoring tool records the number of packets received every second as a sequence: [latex]100, 98, 96, 94, \dots[/latex]. Determine whether this sequence is arithmetic or geometric, and explain how identifying the pattern helps in detecting anomalies.
9. In a game, a player earns points according to the sequence [latex]2^{n}[/latex], where [latex]n[/latex] is the level number. Calculate the total points earned after completing the first [latex]5[/latex] levels and explain how this exponential sequence models increasing difficulty.
10. A DNA sequence is represented as a string of characters from the set {A, T, C, G}. Given the string "ATCGATCG", identify the length of the sequence, the number of unique characters, and explain how such strings are used in bioinformatics.

Challenge Problems

11. A sequence is defined recursively by [latex]a_{1} = 2[/latex] and [latex]a_{n} = a_{n-1} + 3[/latex] for [latex]n > 1[/latex]. Prove by mathematical induction that the closed-form expression for the sequence is [latex]a_{n} = 3n - 1[/latex].
12. Consider the string "ABABABAB". Describe a method to represent this string as a repeating sequence and determine the minimal repeating unit. How could this be used in data compression?
13. A sequence of characters is generated by alternating vowels and consonants from the English alphabet. If the sequence starts with "A, B, E, D, I, F, O, G, U, H", describe the pattern and predict the next five characters.
14. Define a sequence where each term is the number of characters in the English word for the corresponding natural number (e.g., "one" has 3 letters, "two" has 3 letters, "three" has 5 letters). Write the first 10 terms of this sequence and analyze its behaviour.
15. A binary string of length [latex]n[/latex] is defined as a sequence of 0s and 1s. How many distinct binary strings of length 8 contain exactly four 1s? Explain your reasoning using combinatorics.

5.2 Notation and Solving Recurrence Relations

Basic Skills

16. Define a recurrence relation and explain how it differs from a closed-form expression.
17. Given the recurrence relation [latex]a_{n} = a_{n-1} + 2[/latex] with [latex]a_{1} = 3[/latex], write the first five terms of the sequence.
18. Identify whether the following recurrence relation is homogeneous or non-homogeneous: [latex]a_{n} = 2a_{n-1} + 5[/latex]
19. Solve the recurrence relation [latex]a_{n} = a_{n-1}[/latex] with [latex]a_{0} = 7[/latex]. What is the general form of the sequence?
20. Write the characteristic equation for the recurrence relation [latex]a_{n} = 3a_{n-1} - 4a_{n-2}[/latex].

Applications

21. A recursive function in a program has a time complexity defined by the recurrence relation [latex]t_{n} = t_{n-1} + 5[/latex] with [latex]t_{1} = 10[/latex]. Find a closed-form expression for [latex]t_{n}[/latex] and explain what it represents in terms of program performance.
22. A savings account earns interest such that the balance each month is given by [latex]B_{n} = 1.02B_{n-1}[/latex], where [latex]B_{0} = 1000[/latex]. Write the recurrence relation and find the balance after 3 months.
23. A robot moves forward in steps, where the distance covered at step [latex]n[/latex] is defined by [latex]d_{n} = 2d_{n-1}[/latex], with [latex]d_{1} = 1[/latex]. Write the first five terms of the sequence and describe how this models exponential growth in movement.
24. A company’s customer base grows according to the recurrence relation [latex]c_{n} = c_{n-1} + c_{n-2}[/latex], with [latex]c_{0} = 1[/latex] and [latex]c_{1} = 2[/latex]. Identify the type of recurrence relation and explain how it models viral growth.
25. A recursive algorithm for computing factorials is defined by [latex]f_{n} = n f_{n-1}[/latex], with [latex]f_{0} = 1[/latex]. Write the recurrence relation and explain how it reflects the structure of the recursive function.

Challenge Problems

26. Solve the recurrence relation [latex]a_{n} = 4a_{n-1} - 4a_{n-2}[/latex] with initial conditions [latex]a_{0} = 1[/latex] and [latex]a_{1} = 4[/latex]. Show all steps, including the characteristic equation and general solution.
27. Let [latex]m_{n}[/latex] represent the minimum number of moves required to solve [latex]n[/latex] layers of a Rubik’s cube. We define [latex]m_{n} = m_{n-1} + 4n + 4[/latex] where [latex]m_{n-1}[/latex] is the number of moves to solve the first [latex]n - 1[/latex] layers and [latex]4n + 4[/latex] is the number of moves required to solve layer [latex]n[/latex]. The initial condition is [latex]m_{1} = 8[/latex]. Find a closed-form expression for [latex]m_{n}[/latex] using the method of iteration.
28. Prove that the solution to the recurrence relation [latex]a_{n} = 5a_{n-1}[/latex], with [latex]a_{0} = 2[/latex], is [latex]a_{n} = 2(5^{n})[/latex] using mathematical induction.
29. Consider the recurrence relation of the Fibonacci sequence [latex]f_{n} = f_{n-1} + f_{n-2}[/latex], with [latex]f_{0} = 0[/latex] and [latex]f_{1} = 1[/latex]. Prove that [latex]f_{n} < 2^{n}[/latex] for all [latex]n \geq 1[/latex].
30. The recursion tree method is a visual and analytical technique used to solve recurrence relations, especially those arising from divide-and-conquer algorithms. It helps estimate the time complexity of recursive algorithms by modelling how the problem breaks down at each level of recursion. Given a recurrence relation like [latex]t_{n} = at_{\frac{n}{b}} + f(n)[/latex], the recursion tree method involves (1) drawing the tree: each node represents a recursive call. The root is the original problem [latex]t_{n}[/latex], and its children represent the subproblems [latex]t_{\frac{n}{b}}[/latex], and so on; (2) calculating work per level: At each level of the tree, you compute the total cost of all nodes at that level; and (3) summing across levels: Add up the work done at each level to estimate the total work. A recursive algorithm has a time complexity defined by [latex]t_{n} = 2t_{\frac{n}{2}} + n[/latex], with [latex]t_{1} = 1[/latex]. Use the recursion tree method to find the closed-form solution of [latex]t_{n}[/latex].

5.3 Algorithms

Basic Skills

31. Define an algorithm and explain how it differs from a general procedure or set of instructions.
32. What is a recursive algorithm? Provide a simple example using pseudocode.
33. Identify whether the following is a recursive or iterative algorithm:

function factorial(n):

if n == 0:

return 1

else:

return n * factorial(n - 1)

34. Describe the purpose of analyzing the time complexity of an algorithm.
35. Match each algorithm type with its typical use case:

Applications

36. A recursive algorithm is used to compute the [latex]n[/latex]th Fibonacci number. Describe how the recurrence relation [latex]f_{n} = f_{n-1} + f_{n-2}[/latex] models the algorithm’s behaviour and explain the impact on time complexity.
37. A sorting algorithm processes a list of [latex]8[/latex] elements in [latex]n \text{ log } n[/latex] time. Estimate the number of operations required and explain how this compares to a quadratic-time algorithm.
38. A binary search algorithm is applied to a sorted list of [latex]1024[/latex] elements. How many comparisons are required in the worst case? Explain how this relates to logarithms.
39. A recursive function is defined as follows:

function mystery(n):

if n <= 1:

return 1

else:

return 2 * mystery(n - 1)

What does this function compute? Write the recurrence relation and solve it.

40. A divide-and-conquer algorithm splits a problem of size [latex]n[/latex] into two subproblems of size [latex]n/2[/latex], and combines the results in linear time. Write the recurrence relation for the time complexity.

Challenge Problems

41. A recursive algorithm for computing the [latex]n[/latex]th term of a sequence is defined by the recurrence relation [latex]t_{n} = t_{n-1} + t_{n-2}[/latex], with [latex]t_{1} = t_{2} = 1[/latex]. Solve the recurrence and explain why it is inefficient for large n. Suggest an optimized approach.
42. Consider the following pseudocode:

function mystery(n):

if n <= 1:

return 1

else:

return mystery(n - 1) + mystery(n - 1)

1. 1.  Write the recurrence relation for the number of calls made by mystery(n).
   2.  Solve the recurrence relation.

43. A divide-and-conquer algorithm splits a problem of size [latex]n[/latex] into three subproblems of size [latex]\frac{n}{2}[/latex], and combines the results in linear time. Write the recurrence relation and solve it.
44. Solve the recurrence relation of the Fibonacci recursive algorithm to obtain a formula that gives the [latex]n[/latex]th Fibonacci number directly without recursion.
45. A recursive algorithm is defined as follows:

function compute(n):

if n == 1:

return 1

else:

return compute(n - 1) + log(n)

Write the recurrence relation for the time complexity of compute(n) and solve it using iteration or bounding techniques.

5.4 Recursive Algorithms and Algorithm Analysis

Basic Skills

46. Define a recursive algorithm and explain how it differs from an iterative algorithm.
47. What is the base case in a recursive algorithm, and why is it essential?
48. Consider the recursive function

function sum(n):

if n == 0:

return 0

else:

return n + sum(n - 1)

Write the recurrence relation that models its behaviour.

49. What does Big O notation represent in the context of algorithm analysis?
50. Match each complexity class with its growth rate:
    

    Complexity Class	Growth Rate
    Constant time	[latex]O(n^{2})[/latex]
    Linear time	[latex]O(1)[/latex]
    Quadratic time	[latex]O(2^{n})[/latex]
    Logarithmic time	[latex]O(n)[/latex]
    Exponential time	[latex]O(\text{log } n)[/latex]

Applications

51. A recursive function is defined as follows:

function power(base, exponent):

if exponent == 0:

return 1

else:

return base * power(base, exponent - 1)

Write the recurrence relation for this function and determine its time complexity.

52. A recursive algorithm for computing the sum of an array of [latex]n[/latex] elements splits the array in half at each step and combines the results in constant time. Write the recurrence relation and determine the time complexity.
53. A recursive function for computing the [latex]n[/latex]th Fibonacci number has exponential time complexity. Explain how memoization (speeds up recursive algorithms by storing the result of expensive function calls and reusing them) or dynamic programming can reduce the time complexity and describe the trade-offs involved.
54. A divide-and-conquer algorithm solves a problem of size [latex]n[/latex] by recursively solving two subproblems of size [latex]\frac{n}{2}[/latex] and combining the results in [latex]O(n)[/latex] time. Write the recurrence relation and explain how it leads to [latex]O(n \text{ log } n)[/latex] complexity.
55. A recursive function is defined as:

function mystery(n):

if n <= 1:

return n

else:

return mystery(n - 1) + mystery(n - 2)
+ mystery(n - 3)

Write the recurrence relation and discuss the implications for time complexity and performance.

Challenge Problems

56. A recursive function is defined as:

function compute(n):

if n == 0:

return 0

else:

return compute(n - 1) + n^2

1. 1. Write the recurrence relation for this function.
   2. Solve it to find a closed-form expression for the total number of operations.

57. A recursive algorithm divides a problem of size [latex]n[/latex] into four subproblems of size [latex]\frac{n}{2}[/latex], and combines the results in [latex]O(n^{2})[/latex] time.
    1.  Write the recurrence relation for the time complexity.
    2.  Determine the Big O complexity.
58. Prove that the recursive function for computing the sum of the first [latex]n[/latex] natural numbers

function sum(n):

if n == 0:

return 0

else:

return n + sum(n - 1)

has time complexity [latex]O(n)[/latex] using a recurrence relation and iteration.

59. A recursive function is defined as:

function mystery(n):

if n <= 1:

return 1

else:

return mystery(n - 1) + mystery(n - 2)

1. 1.  Write the recurrence relation for the number of function calls.
   2.  Prove that the number of calls grows exponentially with [latex]n[/latex].

60. A recursive algorithm processes a list of size [latex]n[/latex] by making three recursive calls on inputs of size [latex]\frac{n}{3}[/latex], and combines the results in [latex]O(n)[/latex] time.

1. 1.  Write the recurrence relation.
   2.  Use the recursion tree method (see Exercise 30) to estimate the total work and determine the time complexity.