We have seen two search algorithms on lists — linear search and binary search. Both algorithms find the index of a given target value in a list. But they make different assumptions about the data in the list: linear search works on any list, whereas binary search only works if the list is in order.
Before attempting these exercises, you should read the posts on specifying problems, problem-solving and algorithmic “plans”.
Before attempting these exercises, you should read the posts on specifying problems, problem-solving and algorithmic “plans”.
We want to write algorithms, because algorithms solve computational problems. Before writing an algorithm, we need to make the problem specific enough — we need to understand exactly what our algorithm is required to do.
A computer programmer is somebody who converts computational problems into computational solutions. This is a “meta-problem”:
A computer can’t do this — writing programs requires insight and ingenuity.(1) But there are some systematic processes we can follow when writing programs, so most of the time we don’t have to hope for a “eureka!” moment.
Graphs and networks are useful because they’re very general — graphs show up almost everywhere. Given that there are so many different examples of graph structures, then, it’s perhaps surprising that there aren’t actually very many different kinds of problems involving graphs.
That is, there are many computing problems which graphs can help with, but not many kinds of problem. Usually, after translating from the problem domain into the language of graphs, the problem turns out to be one of a relatively small number of “classical graph problems”.