IFSC1305                                    Midterm                    Name_________________________________________

 

1. [6%@] Teachers of problem solving train students to recognize and tabulate the “parts” of a problem.  
1. Explain what Ackoff would expect the student to tabulate:
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
2. Explain what Polya would expect the student to tablulate:
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
3. Explain what Wicklegreen would expect the student to tabulate:

 

2. [10%] What does “state of mind” or psychology have to do with problem solving?
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
3. [10%] What does language and notation have to do with problem solving?

 

4. [12%] Mitchell proposes some tools that help problem solvers describe, analyze, or explore a problem situation.  Identify three tools and explain where they are useful.
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
5. [12%] Algorithms aresolutions to problems that can be (if properly translated) executed by a machine.  Most involve repeatedly executing a small number of steps.   What characteristics must a solution strategy have if it is to stated as an algorithm (what are the defining characteristics of algorithms)?
   
6. [6%@] [Some of] you have thought about how you approach problems (mathematical or otherwise).   For each of the following strategies comment on whether you use it and how powerful (effective) it is:
1. guess (estimate what you think a reasonable answer should be and test the approximation.)
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
2. categorize and correlate (pigeon-hole the problem and connect it to another problem, solved or unsolved, which has already been explored, thus making the present problem less strange)
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
3. decompose (factor the problem into subproblems, isolating the hard and easy aspects of the problem).

 

7. [3 pts. @] The following TM  changes only *’s on the tape so all you have to do to trace its execution to see what stars it changes to what value.   Show your trace by circling the successive cells that show up in the window (I’ve circled the first one).    Trace all three tapes (there are more copies than you need)

 

State        *            0                   1                               a)         * * 1 0 1 0 1 1 0 1 * *

     1         -             L                (2,,L)                                       * * 1 0 1 0 1 1 0 1 * *                         

     2     (8,0,)     (1,,L)             (3,,L)                                       * * 1 0 1 0 1 1 0 1 * *

     3     (8,0,)     (4,,L)                 L                                          * * 1 0 1 0 1 1 0 1 * *

     4     (8,0,)     (1,,L)             (5,,L)                                       * * 1 0 1 0 1 1 0 1 * *

     5     (8,0,)     (6,,L)             (3,,L)                                       * * 1 0 1 0 1 1 0 1 * *

     6     (8,0,)     (1,,L)             (7,,L)                                       * * 1 0 1 0 1 1 0 1 * *

     7     (8,1,)         L                    L                                          * * 1 0 1 0 1 1 0 1 * *

     8     halt        halt                halt                                          * * 1 0 1 0 1 1 0 1 * *

                                                                                                * * 1 0 1 0 1 1 0 1 * *

 

b)               * * 1 0 1 1 0 * *                                         c)         * * 0 0 0 1 1 1 0 1 0 * *

* * 1 0 1 1 0 * *                                                     * * 0 0 0 1 1 1 0 1 0 * *

* * 1 0 1 1 0 * *                                                     * * 0 0 0 1 1 1 0 1 0 * *

* * 1 0 1 1 0 * *                                                     * * 0 0 0 1 1 1 0 1 0 * *

* * 1 0 1 1 0 * *                                                     * * 0 0 0 1 1 1 0 1 0 * *

* * 1 0 1 1 0 * *                                                     * * 0 0 0 1 1 1 0 1 0 * *

* * 1 0 1 1 0 * *                                                     * * 0 0 0 1 1 1 0 1 0 * *

                                                                              * * 0 0 0 1 1 1 0 1 0 * *

                                                                              * * 0 0 0 1 1 1 0 1 0 * *

                                                                              * * 0 0 0 1 1 1 0 1 0 * *

                                                                              * * 0 0 0 1 1 1 0 1 0 * *

                                                                              * * 0 0 0 1 1 1 0 1 0 * *

d)  how long does it take the TM to run (can you

            predict the number of instruction cycles the

            machine will use from the number of symbols

            on the input tape)?

 

 

 

e)  what happens when you reach state 7?

 

 

 

f)  what happens if you don’t reach state 7?

 

 

 

 

g)  what does this TM do (what problem does it solve)?