Out of a score of 100, how confident are you that AI wrote this entire assignment? How confident are you that AI assisted in this assignment?

Assignment:
Haiden Busick-Warner Algo HW 3
Collaborators: Marcus Yi, Liam Kosar
1)
a) p_3=1, p_4=0, p_5=2, p_6=5, p_7=3
b)
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
Runtime analysis:
Outer loop: loop over totalCost from 1 to B: O(B)
Inner loop: loop over i from 1 to n: O(n)
Total runtime: O(B) * O(n) = O(b*n) = O(n)
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).