Exercise 1: Sequence Generator

The objective of this exercise is to practice generating sequences using recurrence relations.

Write a program (in pseudocode or a language of your choice) that generates the first [latex]n[/latex] terms of a sequence defined by the recurrence relation

[latex]a_{1} = 2, a_{n} = a_{n-1} + 3[/latex] for [latex]n > 1[/latex]

The program should prompt the user for the number of terms and display the sequence.

Exercise 2: Fibonacci Calculator

The objective of this exercise is to implement and compare recursive and iterative algorithms.

Write two functions to compute the [latex]n[/latex]th Fibonacci number: (1) one using a naive recursive approach and (2) one using an iterative loop.

Compare their performance for [latex]n = 30[/latex] and explain the difference in time complexity.

Exercise 3: Recurrence Solver (Iteration Method)

The objective of this exercise is to solve a recurrence relation using iteration.

Write a program that takes a recurrence relation of the form [latex]a_{n} = a_{n-1} + d[/latex] with a given initial value [latex]a_{1}[/latex] and common difference [latex]d[/latex], and computes the closed-form expression.

The program should output both the recurrence and the closed-form formula.

Exercise 4: Recursive Algorithm Analyzer

The objective of this exercise is to simulate and analyze the number of recursive calls.

Write a recursive function that models the recurrence [latex]t_{n} = 2t_{n-1} + 1[/latex], with [latex]t_{1} = 1[/latex].

Track and print the number of recursive calls made for a given [latex]n[/latex].

Use this to estimate the function's growth rate.

Exercise 5: Memoized Fibonacci

The objective of this exercise is to optimize a recursive algorithm using memoization (see Exercise 53).

Modify the recursive Fibonacci function to store previously computed values in a dictionary or array.

Compare the number of recursive calls made with and without memoization for [latex]n = 35[/latex].