| CPSC 327 | Data Structures and Algorithms | Spring 2024 |
Follow the 16-step development process discussed in class — your writeup should contain each step, not just the final algorithm. The goal of this material is to be familiar with and able to apply a process that can help you figure out an algorithm and which covers the necessary elements of making sure it is correct, and so while you still want to come up with a correct algorithm, the most important part of the homework problems is the process rather than the resulting algorithm.
Actually do the steps rather than just describing what they are about or what should be done for them. See the "complete" writeups (rather than the in-progress ones) for the examples discussed in class.
For both the specifications and the generalized problem / subproblem definition, be sure to explicitly identify what the input is, what the output is, and what constitutes a valid solution. The output is what is returned (e.g. a tiling of the board) while a valid solution is what is required for that tiling to be acceptable (e.g. all of the board squares are covered except for the black square, and no tiles overlap).
Be sure to cover all of the input — there's an n×n board, but that's not everything... The subproblems need the same input (plus possibly additional parameters to define the "sub" or generalized part e.g. the section of the original input that is being considered). Make sure the main case deals with determining any input that goes to the friends' problems — sometimes that might be simple, like computing the middle index of an array, and sometimes there might be more involved.
Correctness for the base case is often pretty trivial to show, but it still needs to be stated and justified.