I need some help checking my algorithm and data structures homework. I'm going to give you the homework assignment and then my solutions. Only tell me things that you would change.

Assignment:
Dynamic Programming Solution Template
In each of the Problems 2 through 4, we ask you to present dynamic programming algorithms.
Dynamic programming can be very tricky and this template will help guide you through solving
new problems. For any problem asking you to give a dynamic programming algorithm, we
urge you to get in the habit of going through the list below and filling everything out step by
step. The percentage in parenthesis for each item is the weight that we allocate for the item. To
receive full credit, all of the items below should be correctly provided.
1. (20%) An English description of:
(a) the set of subproblems you define,
(b) the recurrence you write, and
(c) the logic behind your recurrence.
2. (30%) The actual recurrence (including base cases).
3. (5%) The final value your algorithm needs to return.
4. (25%) The algorithm you use to solve the recurrence, written in pseudocode. You may use
either a top-down or bottom-up approach.
5. (20%) An analysis of your algorithm’s running time.

Problem 1. (3 + 5 = 8 points) Weighted Interval Scheduling Recap (Don't worry too much about this one because you can't see the picture)
This problem will test your understanding of dynamic programming by having you run
through the algorithm for interval scheduling that we saw in class. Consider the following input
for the interval scheduling problem:
(a) Recall that for any interval i, we defined pi
to be the largest j < i such that interval j
finishes before interval i starts. List the values for pi
for 3 ≤ i ≤ 7.
(b) Fill out the dynamic programming table. That is, for each value of i = 0,1,...,7, determine
both the value of OPT(i) and whether or not the optimal schedule Oi
includes interval i.
Finally, write the optimal schedule O7 and its value

Problem 2. (10 + 5 = 15 Points) Bookstore
You have a budget of B dollars and want to buy as many books as possible from a bookstore.
The bookstore offers n different types of books, each priced at p1, p2,..., pn dollars. You may
assume all the costs are positive so pi > 0 for every i.
(a) Using the template laid out at the beginning of this document, describe a dynamic programming algorithm that determines the maximum number of books you can purchase
while spending all of your money. If it is not possible to spend all of the B dollars, the
algorithm should return “Impossible”.
For example, if there are two types of books priced p1 = 2 and p2 = 5, and you have a
budget of B = 9 dollars, you can buy a maximum of three books, one of the second type
and two of the first type. If, on the other hand, B = 3, your algorithm should return
“Impossible”.
(b) Give an algorithm to recover the actual optimal solution (if it exists), i.e., the number
of books of each type that you buy so as to maximize the total number of books while
spending all of your money. Your answer should include both pseudocode and a brief
description in English. Analyze and derive the asymptotic running time of your algorithm.

Problem 3. (15 Points) Alternating Subsequence
We call a sequence P [1 : m] alternating if both the following two conditions hold for every
2 ≤ i ≤ m − 1:
• if P [i] < P [i − 1] then P [i] < P [i + 1],
• if P [i] > P [i − 1] then P [i] > P [i + 1].
Using the template laid out at the beginning of this document, describe a dynamic programming algorithm, which takes as input an array A[1 : n] of distinct positive integers, and
computes the length of the longest alternating subsequence of A.
For example, if
A = [10,22,9,33,49,50,31,60]
the longest alternating subsequence is
[10,22,9,33,31,60]
so we should return 6.
Hint: It would help to maintain two arrays increase[1 : n] and decrease[1 : n], where
increase[i] (resp., decrease[i]) represents the length of the longest alternating subsequence
ending at index i where the last two elements are in increasing (resp., decreasing) order.

Problem 4. (10+2+10=22 Points) Jumping Koji
On weekends, Koji enjoys visiting a popular trampoline arena. One of the main attractions
is a track with trampolines placed at different spots. Upon reaching a trampoline on the track,
there are two choices. Either sidestep it and continue running forward, or jump forward from
that trampoline. Choosing to jump propels you into the air, allowing you to land at a distance
further down the track. While exhilarating, it might result in skipping other trampolines, and
Koji isn’t allowed to run backwards on the track.
As a challenge, Koji wants to maximize the total distance traveled in the air. Your task is to
assist her in achieving this goal. Formally, you are provided with an array T [1 : n] representing
the distance of the ith trampoline from the track’s beginning, and another array D[1 : n] that
indicates the distance you travel in the air when jumping on the ith trampoline. You may assume
T [1] < T [2] < ··· < T [n]. Specifically, if Koji jumps on trampoline i, she travels D[i] in the air and
then lands at T [i] + D[i], and can continue moving forward from there.
(a) Using the template laid out at the beginning of this document, describe a dynamic programming algorithm that determines the maximum time Koji can spend in the air.
(b) If the running time of your algorithm in part (a) is slower than O(nlogn), then describe
how you can use preprocessing similar to that in Weighted Interval Scheduling to improve
the running time to O(nlogn).
(c) After consistently using the optimal jumping sequence, the arena’s management gets
concerned about Koji’s safety. They then decide to restrict Koji to at most k jumps per
run. Using the template laid out at the beginning of this document, describe a dynamic
programming algorithm that determines the maximum airtime distance when jumping on
a maximum of k trampolines.

My answers:

1)
p_3=1, p_4=0, p_5=2, p_6=5, p_7=3



i
V_i
P_i
OPT
Included
1
3
0
3
Yes
2
7
1
10
Yes
3
9
1
12
Yes
4
13
0
13
Yes
5
4
2
14
Yes
6
7
5
21
Yes
7
8
3
21
No



2)
a)
English Description:

Subproblem: Define an array maxBooks[0 … budget] where maxBooks[x] represents the maximum number of books that can be bought with a total cost of exactly x. Each subproblem corresponds to finding the maximum number of books that can be purchased for each possible total cost up to the budget.

Recurrence:

For each total cost from 1 to the budget:
Consider each type of book:
If the price of the current book does not exceed the current total cost and the remaining total cost is achievable (i.e., a solution exists for maxBooks[totalCost - price[bookIndex]]), then update the maximum number of books for the current total cost.

Logic Behind Recurrence: For each total cost up to the budget, we iterate through each book type. If we can afford the current book (totalCost >= price[bookIndex]) and it's possible to reach the remaining cost after buying it (maxBooks[totalCost - price[bookIndex]] != -1), we consider buying it. We then update maxBooks[totalCost] with the maximum between its current value and maxBooks[totalCost - price[bookIndex]] + 1, where the +1 represents adding the current book to the solution.

Recurrence and Base Case:

Base Case: maxBooks[0] = 0 (we can buy 0 books with $0).

Recurrence Relation:

For totalCost from 1 to budget:
maxBooks[totalCost] = -1 (initialize as impossible)

For totalCost from 1 to budget:
For bookIndex from 1 to n:
If ( totalCost >= price[bookIndex] & maxBooks[totalCost - price[bookIndex]] != -1):
maxBooks[totalCost] = max(maxBooks[totalCost], maxBooks[totalCost - price[bookIndex]] + 1)

Final Value to Return:

If maxBooks[budget] != -1: return maxBooks[budget] (return the maximum number of books if a solution exists for the given budget)
Else: return “Impossible” (return "Impossible" if it's not possible to reach the exact budget with the given book prices)

Pseudocode:

maxBooks(budget, price[1, …, n]):

// Initialize maxBooks to -1

For totalCost from 0 to budget:
	maxBooks[totalCost] = -1
maxBooks[0] = 0 // base case
		
For totalCost from 1 to budget:
	For bookIndex from 1 to n:
		If totalCost >= price[bookIndex] & maxBooks[totalCost - price[bookIndex]] != -1:
					
			maxBooks[totalCost] = max(maxBooks[totalCost], maxBooks[totalCost - price[bookIndex]] + 1)


If maxBooks[budget] != -1:
	Return maxBooks[budget]
Else:
	Return “Impossible”
Algorithm Runtime Analysis:

Outer loop (totalCost): O(budget)
Inner loop (bookIndex): O(n)
Therefore overall = O(budget * n) = O(n * budget) 


2)
b)

Extending from part a), which used maxBooks to store the maximum number of books for each cost, now we have a chosenBook array to remember the last book we added to reach that maximum.

English explanation:

Initialize maxBooks and chosenBook arrays to size budget B
Initialize counts array to all 0s
maxBooks[0] = 0
All other indices of maxBooks = -1


For each possible cost (from 1 to B):
For each book type:
If you can afford the book (cost >= book price) AND there's a valid solution for the remaining cost (maxBooks[cost - book price] != -1):

Calculate the total number of books if you buy this book: newBooks = maxBooks[cost - book price] + 1.

If this new total (newBooks) is greater than the current maximum for this cost (maxBooks[cost]):

Update maxBooks[cost] with the new maximum (newBooks).
Store the index of the current book type in chosenBook[cost] to remember the choice made.

If maxBooks[B] = -1:
	Return “Impossible”
Else:
	totalCost = B;
	While totalCost is greater than 0:
		Look up the last book added in chosenBook[totalCost]
		Increase the count for that book type in counts
		Reduce totalCost by the price of that book

Return counts

Pseudocode:

Algorithm RecoverOptimalSolution(B, price[1..n]):

    maxBooks[0..B] = [-1, -1, ..., -1]
    chosenBook[0..B] = [-1, -1, ..., -1]
    counts[1..n] = [0, 0, ..., 0]
    
    maxBooks[0] = 0  // Base case: 0 books can be bought with $0

    for totalCost from 1 to B:
        for i from 1 to n:
            if totalCost >= price[i]:
                remainingCost = totalCost - price[i]
                if maxBooks[remainingCost] != -1:
                    newBooks = maxBooks[remainingCost] + 1
                    if newBooks > maxBooks[totalCost]:
                        maxBooks[totalCost] = newBooks
                        chosenBook[totalCost] = i

    // Check if it's possible to spend all the budget
    if maxBooks[B] == -1:
        return "Impossible"
    else:
        totalCost = B
        while totalCost > 0:
            bookIndex = chosenBook[totalCost]
            counts[bookIndex] += 1
            totalCost = totalCost - price[bookIndex]

        return counts


3)
English Description:

Subproblem: Define two arrays, Increase[1, …, n] and Decrease[1, …, n], where n is the length of the input array A.
- Increase[i]: stores the length of the longest alternating subsequence ending at index i, where the last two elements are in increasing order.
- Decrease[i]: stores the length of the longest alternating subsequence ending at index i, where the last two elements are in decreasing order.

Recurrence: For each pair of indices (j, i) such that 1 <= j < i <= n, we update Increase[i] and Decrease[i] based on the following recurrence relations:
- If a[i] > a[j]:
Increase[i] = max(Increase[i], Decrease[j] + 1)
- Else if a[i] < a[j]:
Decrease[i] = max(Decrease[i], Increase[j] + 1)

Logic Behind Recurrence:

When a[i] > a[j]:
We aim to form an increasing pair at the end of the subsequence. We can extend any alternating subsequence ending at index j with a decreasing pair by adding a[i].

When a[i] < a[j]:
We aim to form a decreasing pair at the end of the subsequence. We can extend any alternating subsequence ending at index j with an increasing pair by adding a[i].

Recurrence and Base Case:

Base Case:
For i from 1 to n:
Increase[i] = 1
Decrease[i] = 1
(Each individual element can be considered as an alternating subsequence of length 1).

Recurrence Relation:
For i from 1 to n:
For j from 1 to i-1:
If a[i] > a[j]:
Increase[i] = max(Increase[i], Decrease[j] + 1)
Else if a[i] < a[j]:
Decrease[i] = max(Decrease[i], Increase[j] + 1)

Final Value to Return:

maxLength = 0
For i from 1 to n:
maxLength = max(maxLength, Increase[i], Decrease[i])
Return maxLength
(The final result is the maximum length found among all Increase[i] and Decrease[i] values).

Pseudocode:

LongestAltSubsequence(a[1…n]):
For i from 1 to n:
Increase[i] = 1
Decrease[i] = 1

For i from 1 to n:
	For j from 1 to i-1:
		If a[i] > a[j]:
			Increase[i] = max(Increase[i], Decrease[j] + 1)
		Else if a[i] < a[j]:
			Decrease[i] = max(Decrease[i], Increase[j] + 1)

maxLength = 1
For i from 1 to n:
	maxLength = max(maxLength, Increase[i], Decrease[i])

return maxLength
Algorithm Runtime Analysis:

Outer loop (i): iterates n times.

Inner loop (j): iterates up to i-1 times in each iteration of the outer loop.
Therefore, the total runtime complexity is O(n^2).


4) 

a)
English Description:

Subproblem: Define an array maxAirTime[0 … n] where maxAirTime[i] represents the maximum total airtime Koji can achieve by considering all jumps that land at or before trampoline i. Each subproblem corresponds to finding the best airtime when considering trampolines from 1 to i.

Define another array lastCompatibleTrampoline[1 ... n] where lastCompatibleTrampoline[i] is the index of the last trampoline before trampoline i that Koji can jump from before reaching trampoline i. If no trampoline exists, lastCompatibleTrampoline[i] = 0, indicating that Koji starts from the beginning.

Recurrence: The value of maxAirTime[i] depends on two choices:

Skip trampoline i: Koji does not jump from trampoline i, so the maximum airtime remains the same as maxAirTime[i-1].
Jump to trampoline i: If Koji jumps to trampoline i, then the airtime includes the jump distance at trampoline i (D[i]) plus the best airtime up to the last compatible trampoline (maxAirTime[lastCompatibleTrampoline[i]]).
Logic Behind Recurrence: To determine the maximum airtime up to trampoline i, we take the better of:

Not using trampoline i, in which case maxAirTime[i] = maxAirTime[i-1].
Using trampoline i, which adds D[i] to the best airtime that ends at a trampoline before i, giving jumpDistance[i] + maxAirTime[lastCompatibleTrampoline[i]].
Therefore, the recurrence relation is: maxAirTime[i] = max(maxAirTime[i - 1], D[i] + maxAirTime[lastCompatibleTrampoline[i]])

Recurrence and Base Case:

Base Case: maxAirTime[0] = 0 (since there are no trampolines before index 1, Koji cannot gain any airtime).

Compute lastCompatibleTrampoline[i] for each trampoline: For i from 1 to n:

lastCompatibleTrampoline[i] is the largest index j such that j < i and T[j] + D[j] is less than or equal to T[i].
If no such j exists, set lastCompatibleTrampoline[i] = 0.
Recurrence Relation:
for i from 1 to n:
    maxAirTime[i] = max(maxAirTime[i - 1], D[i] + maxAirTime[lastCompatibleTrampoline[i]])


Final Value to Return:

maxAirTime[n], which represents the maximum total airtime Koji can achieve by considering all n trampolines.

Pseudocode:

findMaxAirTime(trampolinePosition[1…n], jumpDistance[1…n]):
    n = length of trampolinePosition

// I hope this is okay, I just got lazy and didn’t want to do more for loops
    Initialize maxAirTime[0...n] to 0 

    Preprocess lastCompatibleTrampoline[1...n] using Binary Search:
        For i from 1 to n:
            lastCompatibleTrampoline[i] = BinarySearchLastCompatible(trampolinePosition, jumpDistance, i)

    For i from 1 to n:
        maxAirTime[i] = max(maxAirTime[i - 1], jumpDistance[i] + maxAirTime[lastCompatibleTrampoline[i]])

    Return maxAirTime[n]

BinarySearchLastCompatible(trampolinePosition, jumpDistance, i):
    left = 1
    right = i - 1
    result = 0
    While left ≤ right:
        mid = floor((left + right) / 2)
        // Check if trampoline at mid is compatible for landing before i
        If trampolinePosition[mid] + jumpDistance[mid] ≤ trampolinePosition[i]:
            result = mid
            left = mid + 1
        Else:
            right = mid - 1
    Return result

Algorithm Runtime Analysis:

Preprocessing: For each i, binary search over trampolinePosition[1, …, i-1] to find lastCompatibleTrampoline[i]. Since i ranges from 1 to n, and each binary search takes O(log n) time, preprocessing takes O(n log n).

Computing maxAirTime: Single pass through i from 1 to n, each taking O(1) time to compute maxAirTime[i], therefore O(n).

Overall Time Complexity: O(n log n) vs O(n) = O(n log n).

b) Preprocessing was already done in part a. Runtime is O(n log n).

c) 
English Description:

Subproblem: Define maxAirTime[i][j] as the maximum airtime that Koji can achieve by considering the first i trampolines and making at most j jumps, where j ranges from 0 to k.

Define another array lastCompatibleTrampoline[1 ... n] where lastCompatibleTrampoline[i] is the index of the last trampoline before trampoline i that Koji can jump from before reaching trampoline i. If no trampoline exists, lastCompatibleTrampoline[i] = 0, indicating that Koji starts from the beginning.

Recurrence: The value of maxAirTime[i][j] depends on two choices:

Skip trampoline i: Koji does not jump from trampoline i, so the maximum airtime remains the same as maxAirTime[i-1][j].
Jump to trampoline i: If Koji jumps to trampoline i and this is counted as a jump, the airtime includes the jump distance at trampoline i (D[i]) plus the best airtime up to the last compatible trampoline with j-1 jumps (maxAirTime[lastCompatibleTrampoline[i]][j-1]).
Logic Behind Recurrence: To determine the maximum airtime up to trampoline i with at most j jumps, we take the better of:

Not using trampoline i, in which case maxAirTime[i][j] = maxAirTime[i-1][j].
Using trampoline i, which adds D[i] to the best airtime that ends at a trampoline before i with j-1 jumps, giving: maxAirTime[i][j] = max(maxAirTime[i-1][j], D[i] + maxAirTime[lastCompatibleTrampoline[i]][j-1])

Recurrence and Base Case:

Base Case:

maxAirTime[0][j] = 0 for all j (no trampolines means no airtime).
maxAirTime[i][0] = 0 for all i (no jumps allowed means no airtime).
Compute lastCompatibleTrampoline[i] for each trampoline: For i from 1 to n:

lastCompatibleTrampoline[i] is the largest index j such that j < i and T[j] + D[j] is less than or equal to T[i].
If no such j exists, set lastCompatibleTrampoline[i] = 0.
Recurrence Relation:

for i from 1 to n:
    for j from 1 to k:
        maxAirTime[i][j] = max(maxAirTime[i - 1][j], D[i] + maxAirTime[lastCompatibleTrampoline[i]][j - 1])

Final Value to Return:

The final value returned is maxAirTime[n][k], which represents the maximum total airtime Koji can achieve by considering all n trampolines with a maximum of k jumps.

Pseudocode:


MaxAirtimeWithKJumps(trampolinePosition[1...n], jumpDistance[1...n], k):
    n = length of trampolinePosition
    Initialize maxAirTime[0...n][0...k] to 0

    Preprocess lastCompatibleTrampoline[1...n] using Binary Search:
        For i from 1 to n:
            lastCompatibleTrampoline[i] = BinarySearchLastCompatible(trampolinePosition, jumpDistance, i)

    For i from 1 to n:
        For j from 1 to k:
            maxAirTime[i][j] = max(maxAirTime[i - 1][j], jumpDistance[i] + maxAirTime[lastCompatibleTrampoline[i]][j - 1])

    Return maxAirTime[n][k]

BinarySearchLastCompatible(trampolinePosition, jumpDistance, i):
    left = 1
    right = i - 1
    result = 0
    While left ≤ right:
        mid = floor((left + right) / 2)
        // Check if trampoline at mid is compatible for landing before i
        If trampolinePosition[mid] + jumpDistance[mid] ≤ trampolinePosition[i]:
            result = mid
            left = mid + 1
        Else:
            right = mid - 1
    Return result

Runtime Analysis:

Preprocessing: For each i, we binary search over trampolinePosition[1, …, i-1] to find lastCompatibleTrampoline[i]. Since i ranges from 1 to n and each binary search takes O(log n) time, preprocessing takes O(n log n).

Computing maxAirTime: nested loops iterate over i from 1 to n and j from 1 to k. For each pair (i, j), computing maxAirTime[i][j] takes O(1) time, total time of O(n * k)

Overall Time Complexity: time complexity is dominated by the preprocessing step,O(n log n), and the dp table computation, O(n * k). Therefore, total time complexity is O(n log n + n * k).