### Problem 1

> Call a sequence X[0:n] of numbers bitonic if there is an index i with 0<i<n, such that the prefix X[0:i] is increasing and the suffix X[i:n] is decreasing. Describe an efficient algorithm to compute the length of the **longest bitonic subsequence** of an arbitrary array X of integers.

**Subproblem Definition:**

The subproblem defines `T[i] = LIS[i] + LDS[i] - 1`, where LIS is the longest increasing subsequence that *ends* at `i`, and LDS is the longest decreasing subsequence that *starts* at `i`.

The max of `T[i]` from `0 < i < n` is the longest bitonic subsequence.

**Recurrence Relation(s):**

1) `LIS[i] = 1 + max LIS[j]` where `j < i` and `X[j] < X[i]`.
2) `LDS[i] = 1 + max LDS[j]` where `j > i`, and `X[j] < X[i]`.

The recurrence between the two problem is `T[i] = LIS[i] + LDS[i] - 1`.

**Base Case:** In both relations, if no `j` exists such that it fulfills the conditions presented, `LIS[i]/LDS[i] = 1`.

**Why the recursion holds:**

The recursion equality holds because we treat `i` as the inflection point, and determine the LIS and LDS from its position. Adding the lengths of each subsequence (and subtracting 1 to account for `i`) accounts for every inflection point that might exist. Thus, the relation `max(LIS[i] + LDS[i] - 1` holds true.

### Problem 2

> Call a sequence X[0:n] of numbers oscillating if X[i]<X[i+1] for all even i, and X[i]> X [i + 1] for all odd i. Describe an efficient algorithm to compute the length of the **longest oscillating subsquence** of an arbitrary array X of integers.

**Subproblem Definition:**

The subproblem defines down[i] as the length of the LOS that ends at i, where the last value represents X[i] < X[prev], and up[i] where the last value represents X[i] > X[prev]. In sum, the subproblem is `T[i] = max(up[i], down[i])`.

**Recurrence Relation(s):**

1) `down[i] = 1 + max(up[j])` if `j < i` exists such that `X[i] < X[j]`
2) `up[i] = 1 + max(down[j])` if `j < i` such that `X[i] > X[j]`

The recurrence between the two subproblems is `T[i] = max(up[i], down[i])`.

**Why the recursion holds:**

The recursion equality holds because an oscillating sequence contains alternating directions, which require a specific order: up, down, up, down, and so on. To determine the length of the LOS ending at i, we take j < i and check it using the conditions for down[i] or up[i]. This verifies that every subsequence that ends at i remains valid (oscillates) by maintaining the correct order.