|
|
The Rubik’s Cube: Algorithms and Integrated Learning Most science classes you had in high school had involved learning a new formula. Then you had to use it once or twice to get an A on the material. What is different in engineering? In engineering, we have to learn how to derive our own formulas. After that, we learn relationships between variables. To become good at what we do, we integrate those new relationships into our knowledge of how to apply them to our own formulas. This is where most people start having problems in engineering. They want to keep plugging and chugging! Algorithms?!? What are they? Algorithms are a series of repeatable steps for solving a complex problem. Ex: solving the Rubik’s cube. They had books that taught you an algorithm This algorithm allows me to start at any point with the Rubik’s cube and solve it But, memorizing algorithms does not make you a good Can you apply the algorithm to new cases? An Engineer can apply the Algorithms to New Cases After I mastered the Rubik’s cube, people started buying me other shaped polygons. I can solve them all with the same algorithm (modified slightly) An engineer figures out how to apply the algorithm to new cases. How can you learn how to do this? How do we learn to apply algorithms? Sometimes by trial and error. You modify the solution steps you know and see if you get a reasonable answer out for the new case Ex: we know how to solve 2 equations with 2 unknowns, how about solving 3 equations with 3 unknowns? 2 equations with 2 unknowns y = 7 - x An algorithm I always use is to now check my answer! How about 3 eq w/3 unknowns? 2x + 3y + z = 5 Let’s try solving one equation in terms of a single variable and z = 7 - x - y So, 2x + 3y + (7 - x - y) = 5 2x - 4y -2(7 - x - y) = 10 2x + 3y + (7 - x - y) = 5 and 2x + 4y -2(7 - x - y) = 10 2x - x +3y -y = -2 and 2x + 2x -4y + 2y = 24 x + 2y = -2 and 4x - 2y = 24 2x - y = 12 x = -2 -2y 2(-2 - 2y) -y = 12 -4 -5y = 12 y = -16/5 x = -2 +16/5 = (-10+2(16))/5 = 22/5 and plug both x and y into z to get z = 29/5 (I have already plugged all these values into the three equations and found that they are correct.) Do you think you could solve 4 equations with 4 unknowns? An algorithm for solving logic problems: The “Criss-Cross Grid” A big part (1/3) of the GRE exam is solving logic problems. These are the problems where you are given a statement like: “Mary and Tom get on the bus after Susie, who is carrying a blue umbrella…Blah, blah, blah. Who is eating the peanut butter sandwich?” We will now do an example on how to use this method… The Problem Statement One week, five bachelors agreed to go out together to eat the 5 evening meals on Monday through Friday. It was understood that Eric would miss Friday’s meal because of an out-of-town wedding, but that Andy could go to all meals. Each bachelor served as the host at a restaurant of his choice on a different night. Use the clues below to determine which bachelor hosted the group each night and what food he selected: 1) Carl hosted the group on Wednesday. 2) The fellows at at a Thai restaurant on Friday. 3) Bill, who detests fish, volunteered to be the first host. 4) Dave selected a steak house for the night before one of the fellows hosted everyone at a pizza parlor. 5) Everyone loves tacos and that was had one night. Step 1: Identify all parts of the problem
Now all we need to do is match each person with a day and a food... Step 2: Make “Criss-Cross Grid”
Essentially, the grid is just going to help us keep track of the information that we know and help us figure out where we can go next from the problem statement. Let's look back at the given statements in the problem: 1) Carl hosted the group on Wednesday. 2) The fellows at at a Thai restaurant on Friday. 3) Bill, who detests fish, volunteered to be the first host. 4) Dave selected a steak house for the night before one of the fellows hosted everyone at a pizza parlor. 5) Everyone loves tacos and that was had one night. Let's put this information in the table now.
Once we know Carl hosted on Wednesday we know that no one else could have. We also know that Carl could not have hosted on any other day. This will make it possible for us to eliminate a bunch of the other squares and color them in like this:
Now let's move on to the next statement: 2) The fellows at at a Thai restaurant on Friday. We'll put an 'X' on the Thai restaurant for Friday and then eliminate the other days and foods that are then excluded. This leaves us:
The next statement is: 3) Bill, who detests fish, volunteered to be the first host. We can get two things from this: Bill did not choose fish. Bill chose Monday. Let's fill both of those in and eliminate the other possibilities that cannot happen:
Now we move on to the fourth statement: 4) Dave selected a steak house for the night before one of the fellows hosted everyone at a pizza parlor. We'll deal with the first part that Dave picked Steak...
Now that we've gotten some information filled in, let's see why the this Criss-Cross grid is such a powerful tool for solving logic problems like this one. We know that Dave chose Steak from the lower left part of the table. However, we also know that Dave did not choose Monday are Wednesday from the upper left part of the table. This then tells us that Steak was not had on Monday or Wednesday and we can fill those into the upper right part of the table like this:
Likewise, Bill went on Monday and Thai food was on Friday so Bill can't have picked Thai food and we can fill that in:
Now let's go back and pick up the last part of the statement that we are working on: 4) Dave selected a steak house for the night before one of the fellows hosted everyone at a pizza parlor. This means that Steak cannot have been on Friday (because there is no day after that for them to go out to eat). For similar reasons, pizza could not have been on Monday. Let's fill those into our table:
Actually, we already knew that Steak couldn't be on Friday from before. Now where can we go? How about looking at Bill again. He chose Monday, but pizza can't be on Monday. This means that bill did not choose pizza. When we fill that in we see that Bill must have chosen tacos (from the lower left part of the table):
Let's fill in the rest of the taco information and information about Monday to get:
Let's finish with the last of the implications from that last statement. 4) Dave selected a steak house for the night before one of the fellows hosted everyone at a pizza parlor. We know that pizza was not on Friday (because Thai food was) so steak can't have been on Thursday. When we fill that in we see that Steak must have been on Tuesday, which puts pizza on Wednesday and we get a table like this:
We see that Fish must have been on Thursday!
Looking at the table we can now rapidly fill in a bunch of other stuff. Carl and pizza was on Wednesday so Carl chose pizza. Dave chose steak, which was on Tuesday.
Finally, the original problem statement says that Eric was not on Friday so he must have been on Thursday. That means Andy was on Friday and we end up with:
Our table is completely filled in so we can now write the solution. Solution to the Logic Puzzle
How would we apply this algorithm to more complicated Make more matrices in your table. Ex: we have to find four pieces of information
We repeat two of the things on the axes. Here they two are income and place. A general rule of thumb: When you are trying to find N pieces of information, need to repeat N - 2 things on the axes. Which ones you choose may make the problem harder or easier. You may need to go back and switch which variables you chose for the axes. To return to the previous page, click here. |
© 2007 Arizona Board of Regents for The University of Arizona |