|
|
A course in data structures requires extensive problem solving. You are no longer learning the syntax of a language. You are expected to use a programming language to solve ever more complex problems. Early man had to solve problems just to survive--how to get food, how to stay warm, how to travel from one place to another. We may not have to solve problems to survive (though sometimes we must) but we must solve problems to succeed. Problem solving skills, more than intelligence or hard work, will help you attain a successful career in computing. In this laboratory assignment we will consider the following aspects of problem solving:
A. What is a problem?
B. What is a solution to a problem?
C. How does one solve a problem?
Lastly, as a review, we will:
D. Analyze a problem and design a solution.
E. Solve a problem using the computer.
A problem exists when the current state is different from the desired state. We have hungry people in the world and we don't want anyone to be hungry. We have five classes and we want to earn an "A" in each. We have a set of names and we want a computer to put them in alphabetical order. A famous problem in logic is the Missionaries and Cannibals Problem which is described below:
Three missionaries and three cannibals are on the west side of a river. They have a small row boat that can hold up to two people. The problem is to get all six to the east side of the river. If the cannibals outnumber the missionaries on either side of the river, the cannibals will eat the missionaries.
This problem certainly does not require a computer solution. Other problems such as the "four-color problem" may never have been solved without the use of a computer. Problems solved on a computer are often divided into categories such as mathematical, sorting, searching, string processing, and graph problems. A typical mathematical problem might be to generate a random real number between 0.0 and 1.0.
Donald Knuth's book [ 1 ], The Art of Computer Programming Volume 2, is the primary reference for random number generation techniques and related issues. Many introductory programming texts provide one or more algorithms for generating random numbers. Check your text to see if it contains an algorithm. We will do more with random number generation later in this lab.
Jon Bentley's book Programming Pearls [ 2 ] contains an interesting sorting problem.
Problem: A file contains at most 27,000 4 byte integers in the range 1 to 27,000. No integer occurs more than once and no other data is associated with an integer. At most, 1,000 32-bit words of main memory are available for the code and the data. How can a sorted list of integers be produced within a few minutes (of run time)?
Another problem from Bentley's column illustrates "searching."
Problem: Given a dictionary of English words, find all sets of anagrams. For instance "pots", "stop" and "tops" are all anagrams of each other because each can be formed by permuting the letters of the others.
The inference engine of an expert system, a compiler program, and a program that encrypts/decrypts text all provide examples of "string processing" problems. A typical "graph" problem is to find the shortest path through a directed weighted graph.
The Traveling Salesman Problem is a famous graph problem for which no polynomial (runs in a reasonable amount of) time algorithm has been found but for which there exists heuristic computer algorithms that have worked (in the examples tried so far) in polynomial time. The Traveling Salesman Problem is explained as follows: given a set of cities and distances between pairs of cities, find a tour of all cities whose total distance is minimal.
There are many problems--more than any of us can solve. The successful
person must decide which problems can be solved and which problems are
important enough to merit his/her attention. Choosing the "correct"
problem is a very real problem as every Ph.D. student readily knows.
Many people become famous or rich for a simple idea that any of us could
have come up with but we did not select the correct problem. J. P.
Guilford said, "To live is to have problems and to solve problems is to
grow intellectually."
A solution is a set of steps that will transform the current state
into the desired state. In the sciences, we usually must choose a
symbolic representation of the problem before we can write down the solution
steps. In other disciplines, the representation is often English
text.
A. M & C go to East side, M brings boat back (1C on E)
B. 2 Cs go to East side, C brings boat back (2C on E)
C. 2 Ms go to East side, M & C bring boat back (1M, 1C on E)
D. ______________________________________________________
E. ______________________________________________________
F. ______________________________________________________
The following is a description of Bentley's solution to the sorting problem stated in the previous section. Since no integer can appear more than once in the file, we use a bit array (with at least 27,000 bits) to mark whether an integer is in the file.
1. Initialize the 27,000 bit array B[1..27000] to all 0's.
2. While not end of file
a. Read next integer from file into variable i
b. Set B[i] = True
3. Print the sorted list of integers.
The short answer is "anyway you can." The mathematician George Polya wrote a book in 1957 called How to Solve It [ 3 ] in which he explains techniques for solving mathematical problems. Most of what he says can be applied directly to computing. His suggestions are as follows:
1. Understand the problem
2. Devise a plan
3. Carry out the plan
4. Look back.
Usually to understand a problem you must ask questions, think, and research.
First you should ask yourself questions. If you do this out
loud, you might get strange looks. It is better to be in a quiet
place-someplace free of distractions. If the answers are not forthcoming
after some thought, then plant (fix) the question in your mind and go do
something else. Take a break. Relax. Think about the
problem but not exclusively. Let your subconscious mind work on the
problem. This is called "incubation." It works, but you have
to learn how to make it work for you.
King Hiero suspected his goldsmith had used some silver instead of all gold to make his royal crown. He asked Archimedes to determine if this were true. Archimedes struggled with the problem a long time and then, while taking a bath, he suddenly noticed his body caused some water to spill over the edge of the tub. In an instant, he realized the solution to his problem. Whereupon he jumped out of the tub in the public baths and ran home naked, shouting as he ran: "Eureka! Eureka! I've found it! I've found it!" Try taking a shower, but, if you get the solution, put on your clothes before you run to the lab to test your idea. Creative genius comes from the subconscious. Develop this skill. As William James said, "We learn to swim in the winter and to (ice) skate in the summer."
In addition to asking yourself and others questions about the problem and thinking about it consciously and subconsciously, you should also research the problem. See what has been written on or what is related to the problem. As Louis Pasteur said, "Chance favors only the prepared mind." Look in your text book, library books, journals, and so on. Why reinvent the wheel? Of course you should use integrity and reference any book or journal you use. Don't plagiarize anyone's work.
Often you cannot solve the problem as stated. Understanding the problem will give you enough information to restate the problem so that it is easier to find a solution. Try to generalize the question. If the problem is to invent a new mouse trap, try to understand the requirements of the problem. If one requirement is to keep mice out of your home, then generalize the problem to: How can we best keep mice out of our home? Maybe the answer is not a better mouse trap but better placement of the existing mouse trap (or a hungry cat).
Try to divide the problem into smaller subproblems. This is called divide-and-conquer. It works! Is there a binary search routine described in your text book ? The list to be searched is sorted into ascending order and the element being searched for is compared to the middle element of the list. If they are equal, the search is completed. Otherwise determine which half of the array should be searched next and continue the search. One comparison divides the search space into half of what it was originally. This division into halves continues until the element is found or until the array is exhausted.
Restate a problem several different ways. Open your mind to divergent, non-traditional solutions. Think of foolish solutions and try to see some merit or value in them. A creative idea is more apt to come to a person who has a large number of ideas. Generate several potential solutions before you try to implement one. One may be much easier than the others like Bentley's bit-array solution to the sorting problem. Once you have several ideas, you must select the approach that you will follow to solve the problem. That is, identify the "best" solution.
Finally, you must transform the potential solution you have selected
into a useful result. This process is essentially a repeat of what
you have done to get to this point. In his book entitled The Art of
Creative Thinking [ 4 ], Robert Olson suggests the "DO
IT" (Design a solution, Open yourself to many solution ideas,
Identify the "best" solution, and Transform your solution into
results) approach to problem solving. It works!
The process of problem solving involved in the complete development of a program is called the software life cycle. The first two phases of this process are called analysis and design. Analysis is the "What" and design is the "How." In the analysis phase of problem solving, we try to understand the problem and decide what (not how) must be done to solve it. In the analysis phase, we must understand the "requirements" of the problem. Requirements are often divided into two groups--functional and non-functional requirements. A functional requirement is a function or feature the software solution to the problem must possess. For example, in Bentley's sorting problem, the software must produce a sorted list of the integers in the file. A non-functional requirement is a property or constraint the software must satisfy. In a solution to the sorting problem, the code and data could not use more than 1,000 32-bit words of main memory, the file could not contain duplicate integers, and the run-time of the solution could not exceed "several minutes". These are non-functional requirements. Usually the problem statement contains the requirements which need to be carefully reviewed and discussed. Ideally, requirements should be clear, unambiguous, and consistent.
In the design phase you actually describe how you will solve the problem. In software development we often use stepwise-refinement expressed in either pseudo-code or a flowchart or both to solve a problem. High-level pseudo-code for Bentley's sorting problem was given earlier. Steps 1 and 3 need to be refined before the design is translated into a programming language. Refinement of the previous solution follows:
1. for j=1 to 27000One way to express the design is to use a flowchart. Note the following partial flowchart.
Set B[j] = False
2. while not end of file
a. Read next integer from file into variable i
b. Set B[i] = True
3. for j=1 to 27000
If B[j] = True then print j on a new line
In earlier versions of the C-language and C++ there was no boolean type and some extra work had to be done by the programmer to manage an array of 27000 bits. Of course, the programmer could just declare an array of 27000 integers, initialize them all to 0 and mark each index in the array with a 1 if the integer is found to exist in the file. Because an integer usually occupies a word (possibly up to 32 bits) of memory, this would be a very costly waste of storage space. In older versions of C++ we would have set up a character array (a character array requires 8 bits to store each character) and then we allow each subscript in the array to represent 8 different integers. With ANSI C++'s bool type we can avoid all this hassle and just declare an array of 27000 places of type bool.
By using the bit-wise operators supplied in C++, the bit array can then be manipulated to set the appropriate bits in the array. Now, it is a straightforward task to translate this design into the corresponding C++ code provided in the file inlab1.cc.
1. Knuth, Donald. The Art of Computer Programming, Volume 2, Addison-Wesley. 1969.
2. Bentley, Jon. Programming Pearls, Addison-Wesley, Reading, MA, 1985.
3. Polya, George. How to Solve It: A New Aspect of Mathematics 2nd ed., Princeton, NJ, Princeton University Press. 1973.
4. Olson, Robert. The Art of Creative Thinking, Barnes & Noble, New York, 1980.