Introduction to Algorithms, Page 1 of 4
Back
Introduction to Algorithms
Q:Why did we start with payoff tables and decision trees?
A:They are the most basic tools for decision making.
D:Every decision, ultimately, comes down to comparing alternatives. You can do that in combination with what will come after (decision tree) or focusing entirely on the immediate problem (payoff table), but at some point, all the data collection, computer runs and analysis have to stop – and you must decide. This is a class about decision making, so that is why I start with trees and tables.
Q:Are trees and tables “computer models?”
A:There is nothing inherently computer-oriented about trees and tables. Sure, you can use a spreadsheet to do the calculations, and there are even add-ons (such as Tree Plan) that make it easier, but you can set up a table or tree while doodling on a piece of paper.
Q:How do trees and tables relate to the rest of the class?
A:For the rest of the class we will talk about computer models that, in effect, create the payoffs you consider in a decision tree or payoff table.
Q:What kind of computer models?
A:To begin with, algorithms.
Q:What is an algorithm?
A:A set of mathematical steps that you repeat.
D:“Algo” should remind you of the word algebra. They are both based on the same root, and simply refer to one sort of mathematics. “Rithm” is the same as rhythm, a pattern, something that repeats. That means an algorithm is a math pattern, a set of calculations that repeat. Many computer programs are algorithms, which is why we are going to try very hard to understand algorithms. The odds are very good that someday you will be using a computer system and will be asked to explain the results that the computer is generating. If you understand algorithms, that explanation will be a lot easier.
If you are interested in a historical note on the word “algorithm,” which is a lot more interesting than this stuff, then switch to that lecture. Otherwise, continue below.
Q:What do algorithms do for us?
A:Solve problems that we cannot solve directly.
D:When you first began with algebra, you got very simple problems, such as:
3X = 15.
You learned to solve for the value of X. Now (hopefully) you can solve that one immediately (X = 5). Later, you got more complex problems, such as:
3X + 4Y = 180
5X + 3Y = 212
For this, you learned a process, a series of steps that lead you directly to the solution (X = 28, Y = 24). Many of your Operations, Finance and Accounting problems fall into this category. Most problems, though, are too complex for direct solution, such as:
6X1 + 4X2 + 12X3 150
2X1 + 9X2 + 18X3 247
8X1 + 1X2 + 14X3 101
We can’t solve it by inspection, and there isn’t a simple process that will lead us directly to a solution. Something new is needed – an algorithm.
Q:How is an algorithm different from a “simple solution process?”
A:An algorithm takes a “simple solution process” and applies it to more complex problems, by repeating it.
D:The big difference between algorithms and simple processes is how we think about the word “solution.”
Q:What is a “solution?”
A:The answer to a problem.
Q:Can a math problem have more than one solution?
A:Yes.
D:The simple problems have a single solution; this is the kind you are used to working with. More complex problems have any number of solutions (often an infinite number). When this is true we need something to help us figure out which solution we want.
Q:How do we pick one solution out of an infinite number of them?
A:We need a goal, or to use a different word, an objective.
Q:Aren’t goals and objectives the same thing?
A:Not really.
D:A goal, technically, is measured qualitatively (without numbers), while an objective is measured quantitatively (with numbers). So, in this class, we work with objectives.
Q:Are decision trees and payoff tables considered to be algorithms?
A:No.
D:Trees and tables show solutions, but are not, themselves, solution processes. The analysis process I have taught you could be considered an algorithm, because it does repeat even though it is not particularly mathematical. Further, I would classify the analysis process as a goal-driven algorithm (rather than an objective-driven algorithm) because determining the “best” solution was based on your assessment of the relative risks and rewards, rather than some literal calculation.
Q:When do we use trees and tables, and when do we use algorithms?
A:It depends on the type of problem you are facing.
D:When using Decision Trees and Payoff Tables we were doing straightforward decision-making. We had all the solutions in front of us (remember the assumption of exhaustiveness), but the best one was lost in all the others that had been presented. We didn’t have to search for the preferred solution, it was right there in front of us. We did have to sort through all of the possible solutions – each of which was correct – to find the one we liked.
The algorithms we are going to use now will begin with a different setup. Instead of having solutions to a problem, we have information – data – about the problem. The problem situation is too complex to move directly from organizing the data to finding our preferred solution and we cannot list out all the solutions because there are too many of them. We will have an objective, though, so if we ever have two solutions, we will know (based on a calculation, not out judgment) which one is better. That means we need a way to search for different solutions.
Q:Does an algorithm help us search for solutions?
A:A search algorithm does.
D:Let’s go back to the point I made earlier, that the type of problem we are dealing with has many solutions and we use an objective to decide which one is the best (by the way, the technical term for a best solution is “optimal”). Since we don’t start off with an exhaustive set of solutions in front of us, we develop a process to show us solutions, one at a time.
Q:Does the process show us all the solutions?
A:No.
Q:Then how can we be sure we have checked the right solutions?
A:We will design the search process so that each solution is a little better than the previous one.
D:If we satisfy the above condition, then we have a series of continually improving solutions, and when no further improvements can be found, then we must have the optimal (best) solution. This process is called “implicit enumeration.”
Q:What does “implicit enumeration” mean?
A:“Enumeration” means “listing everything out,” so the Course Offering is an enumerated list of all courses you can take in a given semester. “Implicit” means “implied,” so while we didn’t actually do something, what we did accomplishes the same goal. Thus, implicit enumeration means we didn’t actually list out every solution, but by being careful, we know that the solutions we didn’t show are worse than the solutions we did show, particularly the last (optimal) one.
Q:What are the steps to a search algorithm?
A:They are shown in the following list:
1)gather and organize your data,
2)develop an initial solution,
3)identify search directions,
4)evaluate search directions,
5)using the best search direction, generate an improved solution,
6)repeat from step 3 until no further improvements are possible.
D:To help you understand how a search algorithm works, we are going to use the Transportation Problem, a widely used model that is simple and will serve as a good introduction to the Linear Programming algorithm later on (in other words, pay attention now and your life will be easier later).
Back