ANONYMOUS wrote:
> Hello,
>
> If part of my answer to an exam question asking for me to come up with an algorithm is to "use dfs" and "use bfs" or any other algorithm previously discussed in the unit, do I have to provide an explanation of these algorithms within my own explanation of my algorithm?
>
> E.g.
>
> Is it acceptable to:
>
> (insert algorithm explanation here)
> "then use dfs to... blah blah" - short sentence, doesn't explain dfs
> "then use bellman-ford to... blah blah" - short sentence, doesn't explain bellman ford
> (insert rest of algorithm)
>
> Or are we expected to:
>
> (insert algorithm explanation here)
> "then use dfs to... blah blah. DFS is when.. explanation of DFS here"
> "then use bellman-ford to... blah blah. Bellman Ford algorithm is... explanation of bellman ford here"
> (insert rest of algorithm)
>
> Please let me know, thanks!
In certain cases this depends on context, but in general if you are using a named algorithm we covered in lectures for a purpose we investigated in lectures, then you can assume the marker is familiar with it. This is the same sort of standard I am referring to when I, in the mid-sem, said your explanations should be "sufficient to convince a fellow student". You may assume familiarity with the formal material of the unit.
If you are using DFS or another algorithm for a particular purpose, you may need to justify why it works for that. So I can use it as an example, please pretend that we had not covered the concept of reachability in class. In this case, if you were given a problem that required you to compute reachability and you used a DFS for it, you would have to justify why DFS solves reachability. In reality where we did cover reachability, you could simply say that you are using DFS to find what vertices are reachable from some starting point.
Your task is to solve a problem and communicate your solution. For anyone involved in this unit, communicating something as simple as an explanation of DFS (which could just be copied from the slides) is a waste of time and just bad communication.
So even though the exam instructions do not explicitly ask for it, I think a good rule of thumb for you to work from is "your explanation should be sufficient to convince a fellow student of the correctness/complexity/whatever of your algorithm". You do not need to teach them something that has already been covered in class, but if your explanation is poor enough that they could doubt your argument and point to a leap in logic you have made or similar, then you were plainly not convincing.
I will also take the opportunity to reiterate my common advice: When asked to justify the correctness of an algorithm, merely narrating the steps it takes is not a justification. You could just as readily narrate the steps of a completely incorrect algorithm. You need to provide an argument for why it always gives the correct answer.
Cheers,
Gozz
