1. For all algorithms that you are asked to \give” or \design”, you should
• Describe your algorithm clearly in English.
• Give pseudocode.
• Argue correctness; you may provide a formal proof or a convincing argument.
• Provide, with an explanation, the best (smallest) upper bound that you can for the running time.
All bounds should be worst-case bounds, unless explicitly stated otherwise.
You are also encouraged to analyze the space required by your algorithm. We will not remove marks
if you don’t, unless the problem explicitly asks you to analyze space complexity.
2. If you give a Dynamic Programming algorithm, the above requirements are modified as
(a) Clearly define the subproblems in English.
(b) Explain the recurrence in English. (This counts as a proof of correctness; feel free to give an
inductive proof of correctness too for practice but points will not be deducted if you don’t.) Then
give the recurrence in symbols.
(c) State boundary conditions.
(d) Analyze time.
(e) Analyze space.
(f) If you’re filling in a matrix, explain the order to fill in subproblems in English.
(g) Give pseudocode.
3. Full credit will be given to the fastest correct solution. For example, an algorithm that solves
the problem but runs in time O(n2) will not receive full marks if there is another algorithm that solves
the problem and runs in O(n) (possibly at the expense of some additional space).
4. You should not use any external resources for this homework. Failure to follow this instruction
will have a negative impact on your performance in the exams and in interviews. For the same reason,
you should avoid collaborating with your classmates, at least when working on problems 1-2 and
4-5. I encourage you to work on problems 1 and 2 immediately, then on recommended exercise 1, then
on problem 3. Once we introduce Dynamic Programming in class, work on recommended exercises
2-4, then on problems 4-5. Finally, work on recommended exercises 5-6.
5. You should submit this assignment as a pdf file to Gradescope. Other file formats will not be graded,
and will automatically receive a score of 0.
6. I recommend you type your solutions using LaTeX. For every assignment, you will earn 5 extra credit
points if you type your solutions using LaTeX or other software that prints equations and algorithms
neatly. If you do not type your solutions, make sure that your handwriting is very clear and that your
scan is high quality.