Exercises: Searching Trees
Apr 092018Before attempting these exercises, you should read the posts on depth-first search (DFS) and breadth-first search (BFS).
Exercises: Searching Lists
Apr 092018Before attempting these exercises, you should read the post on linear and binary search.
Breadth-First Search
Apr 092018Depth-first search (DFS) is a fundamental algorithm for working with trees, because it gives us a way to “visit” every node in the tree, once each.(1) That’s important, because visiting every node is a subproblem of many other problems on trees.
DFS explores the full depth of one subtree before moving onto the next one. If that’s the order we want to visit the nodes in, or the order doesn’t matter, then DFS is fine; otherwise, we need a different algorithm. We’ll see one in this post.
Depth-First Search
Apr 092018Search problems vary in two ways: what do we want to search for, and what type of collection are we searching in?(1)
When we need a search algorithm, the data structure we want to search is more important than what we want to find. We could even say that linear search and binary search work on different data structures: linear search uses a list, and binary search uses a list which must be kept in order.(2)
Search Algorithms
Apr 092018Search problems are problems which ask us to find something, given a description of it. Typical search problems are like these:
- Given a list, find the index of a target value.
- Given a list of numbers, find the first negative number.
- Find the first non-empty line in a text file.
- Find all rows in an SQL database table matching a given WHERE clause.
- Given a tree, find a node which holds a target value.
- Given an HTML document, find the first
<h1>tag. - Find all tags in an HTML document matching a given CSS selector.
- Starting at a given node in a graph, find all nodes reachable via edges.
A search algorithm is one which solves a search problem. In this post, we’ll see two algorithms which solve search problems on lists.(1)
Exercises: Problem-Solving with “Plans”
Mar 192018Before attempting these exercises, you should read the posts on specifying problems, problem-solving and algorithmic “plans”.
Exercises: Recognising “Plans”
Mar 192018Before attempting these exercises, you should read the posts on specifying problems, problem-solving and algorithmic “plans”.
Algorithmic “Plans”
Mar 192018“Plans” are the basic “blueprints” or “building blocks” for algorithms — they are canned solutions to common programming problems which are simple but appear in many variations. Thinking about plans makes it easier to understand code, because we can see the intentions rather than thinking about one line at a time. Each plan usually only solves part of a problem, so a given piece of code may use many plans, and some plans always use other plans.
A Problem-Solving Process
Mar 192018A computer programmer is somebody who converts computational problems into computational solutions. This is a “meta-problem”:
- Given a problem, write a computer program which solves it.
- Input: a problem statement.
- Output: a computer program.
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.
Specifying Problems
Mar 192018We 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.