By default, if a homework or exam problem asks you to describe an algorithm, you need to do several things to get full credit:
- If necessary, formally restate the problem in terms of combinatorial objects such as sets, sequences, lists, graphs, or trees. In other words, tell us what the problem is really asking for. This is often the hardest part of designing an algorithm.
- Describe the most efficient algorithm you can. The more efficient your algorithm, the more points you get. Brute force is usually not worth very much. We will not always tell you what time bound to shoot for; that's part of what you're trying to learn!
- Give a concise pseudocode description of your algorithm. But don't regurgitate! And don't turn in source code!
- Justify the correctness of your algorithm. You may not
have to do this on exams unless asked for.
- Analyze your algorithm's running time. This may be as simple as saying "There are two nested loops from 1 to n, so the running time is O(n2)." On the other hand, it may require setting up and solving a summation and/or a recurrence, in which case you'll also have to prove your answer is correct.
Some problems may deviate from these default requirements. For example, you may be asked for an algorithm that uses a particular approach, even though another approach may be more efficient. (Answer the right question!) Some problems may ask you to analyze the space used by your algorithm in addition to the running time.