IFSC1202 LAB #2
Instructions: This lab consists of two parts. Each part must be completed and emailed to ifsc1202@ualr.edu (use the “send to” option on the file menu). The Lab Report may be completed in pairs or triples but each student must submit the resulting report individually.
.
Part A. Complete this lab report
Part D. Complete this log
This lab focuses on problem solving. It asks you to solve some problem, NOT because the solutions are of any interest to anyone, but to study how problems are solved and how solutions are represented. The first problem is merely how to state in English something we would rather demonstrate. The second problem is how to generalize a situation to take advantage of symmetry to cut down on the number of cases that must be specified. An alternative would be to end up with a long list of instructions in which you would skip over most once you knew which of the many alternatives the opponent chose. The two river-crossing puzzles demonstrate how to analyze alternatives. Both can be solved by building alternative trees that keep us focused on making progress to the solution instead of getting confused by the dead ends. The solution to these problems can be easily represented by a notation that depicts the objects on one side of the river at each step, and just lists the steps. The alternative tree method handles the complexity of multiple dependent stages when there are not a lot of alternatives to consider. The letter arithmetic problem demands another approach because there are too many alternatives and so the obvious way to guess at a solution has low probability of success. We must return to the strategy used for tic-tac-toe and re-partition the problem states into a smaller number of more general alternatives. The solution to the problem gives no hint at how it was obtained, being simply the two lists that specify the substitution pattern plus a proof of the addition fact after the substitution has been made. These puzzles have little to do with computers (although their solutions can be programmed) but instead have to do with understanding productive strategies for analyzing problems that can be solved with algorithms. It is the fact that those after the first can be solved mechanically—algorithmically, that causes us to want to understand how to solve this kind of problem. This kind of problem is representative of problems whose solution can be found via calculation, thus are the kind of problems that we would expect to deal with as programmers (kind in a very abstract sense—we sometimes have difficulty distinguishing the problems that have algorithmic solutions from those that do not!).
Problem solving is the first (and most difficult) part of using the computer. Once a solution strategy is discovered, an algorithm derived, the details of expressing the algorithm in a particular programming language is very straightforward. We will not be tackling computer solutions of problems that require much analysis in this class. We will move on to looking at problems that are EASY to express in our language, visual basic, and after we have learned the language and practiced doing the easy things—in the next course—we will look again at how to analyze situations to find the algorithm for a program.
Because problem solving is hard,
and these puzzles teach a lot, we will probably need several days to work on
them. Therefore this lab will not expire until Friday at 8
am.