代做CS 330, Spring 2025, Homework 8调试数据库编程

CS 330, Spring 2025, Homework 8

Due Wednesday, April 16th, 11:59 pm EST, via Gradescope

Homework Guidelines

Collaboration policy    You  must  write  up  each problem  solution  by  yourself without  assistance, even if you  collaborate with  others to solve the problem.  You must also identify your collaborators. If you did not work with anyone, you should write ”Collaborators:  none.” It is a violation of this policy to submit a problem solution that you cannot orally explain to an instructor or TA.

Typesetting   Solutions should be typed and submitted as a PDF file on Gradescope.  You may use any program you like to type your solutions.  LATEX, or “Latex”, is commonly used for technical writing (overleaf .com is a free web-based platform for writing in Latex) since it handles math very well. Word, Google Docs, Markdown or other software are also fine.

Content of the Solution.   When a problem asks you to design an algorithm, a complete (a.k.a. full credit) solution always  consists of a description of the algorithm using pseudocode  (thus not actual code) with well-chosen comments, preferable some short and high level description in English so that the reader has an idea of what the code does, a proof of the correctness of the algorithm and a running time analysis.

Here are some guidelines specific to the solution of DP problems:   Any solution should cover 4 main parts:

1.  Clearly state what the subproblems and variables are.  e.g.  WIS: OPT(j) is the max value solution on jobs 1, . . . j if sorted by earliest finish time. Knapsack:  OPT(i,w) is the max value solution on items 1 . . . i with capacity w.

2. write the recursive formula (including base cases!)  and a detailed explanation while the parts of the formula correctly compute the objective. You can omit the induction proof that would apply it to each index.

3. write the pseudocode for your algorithm (bottom-up or top-down are both fine) and analyze its running time.  The explanation of the recursive formula serves as proof of correctness, you don’t need to write anything in addition here.

4.  (*) write the backtracking algorithm and analyze its running time.  No proof needed as the algorithm is mostly reverse-engineering of the recursive formula.  However, it will be graded both on  correctness  and  efficiency.   (*) You  can  either  write backtracking  as  a  separate algorithm to be run after the DP algorithm or you can incorporate the backtracking steps in your DP algorithm, both are acceptable. Make sure to include clear comments in your code.

1.  Frog Jumps

You have a row of n lily pads, labeled from 0 to n - 1.  A frog starts on lily pad 0 and wants to reach lily pad n - 1.  Each lily pad i has a number B[i] that tells you how far the frog can jump from that pad. Specifically, if B[i] = k, then the frog can jump forward any number of steps between 1 and k. The frog can only jump forward, never backward. Your goal is to determine the minimum number of jumps needed for the frog to get from lily pad 0 to lily pad n - 1.

The input is an array B, where B[i] is the number on lily pad i. Write a dynamic programming solution to find the minimum number of jumps needed for the frog to reach lily pad n - 1.