1305 Assignments
(class meets TR, each assignment due in 1 week)
A1: Access the Information Technology Report [http://www.ualr.edu/%7Eitreport/ or use the link on the Homepage]and submit a paragraph that describes what that document has to say about problem solving
A2: Find a job in Arkansas advertised on the web that you would be interested in taking. List the employer, the job description, and the minimum qualifications that are required.
A3: Write out your answers to question 2, p. 24, [Translate the following roman numerals into Arabic numerals: D, VII, LIX, and MCMXCIV. Now describe a procedure that explains, in general, how to translate roman numerals consisting of the letters M, D, C, L, X, V, and I in the standard manner, and test your procedure by applying it to each of these specific input values] question 1, p. 32, [Exactly how many substitution patterns are there for a letter arithmetic puzzle using eight letters?] and question 2, p. 41 [List some other problem-solving tools (we have considered only those most relevant to computer applications). Determine whether these tools all can be classified as either conceptual (evoking images or ideas, thinking (categorizing, structuring), or manipulative (relationship building and modifying)).
A4: 1. three missionaries and 3 cannibals are traveling together when they come to a wide river. A boat is there that will hold two men. the missionaries know that if the cannibals outnumber the missionaries on either side of the river, they will try to eat them, so the missionaries suggest the pattern by which the boat will be rowed back and forth across the river and result in everyone getting safely to the other side. Display the sequence of M's and C's that will be present on the near side of the river when the boat is midstream. 2. Write the base 2 representation of 12, 17, 23, 30, and 36 and show which weights (that are powers of two) are used to weigh objects of that weight using one pan for the object and one pan for the weights. Write the base 3 representation of those same numbers and show what combination of weights (that are powers of 3) can be used to weight those objects when weights can be added to either pan.
A5: Write out and submit your answers to Mitchell, p. 58,#1 [Assume you must give instructions to a three-year-old over the phone on how to tie a shoelace. Write down the instructions you would use.],5 [Write an algorithm for adding several positive integers (multidigit) that could be executed by a second grader who knew how to add pairs of multidigit integers. Note that the desire is to break each column of integers into many different addition problems (add the first two digits in the column, add the third digit to this sum, add the fourth to that sum, etc.) Your column addition algorithm should contain two levels of looping, similar to the sorting algorithm, since you must do something repeatedly in order to find out what value to carry to the next column ], and Mitchell, p. 63, #3 [Loops are hard to focus on in English because we use verbs which gloss over the repetiton. For example, to balance your checkbook at the end of the month, the bank statement recommends that you verify each check recorded on the statement against your checkbook entry, add up the uncleared checks, subtract the sum from the staement balance, and compare the difference with your checkbook balance. Rewrite these instructions to highlight the loops and what controls their repetition].
A6: Mitchell, p.73, #2 [Besides BOX and PEAK it might be nice to have other simple instructions in the drawing language, such as CIRCLE. How can the machine be commanded to draw circles?](note that the smallest square is to move 1 and turn 90 degrees repeatedly. The smallest diamond is to move 2 at 45 degrees, then turn 90 degrees repeatedly. A circle is in between a square and a diamond, but unless it has a substantial circumference, it won t look much like a circle. Can you get better than an octagon?) Find and fix the error in the program on p. 69 so that it will actually draw Figure 5.2
A7: (A) Do problem 3 on Mitchell p.82 [Trace the actions of the third Turing machine (extended decimal addition) for the tape ..**7+5**… If your trace becomes alarmingly long, don’t be concerned, since a Turing machine will actually operate quite quickly, and besides, it has nothing else to do so is not concerned with the number of steps that it must execute to process a tape] and (B)problem 4 on Mitchell p. 88 [Trace the action of the binary addition Turing machine of this section for the tape ..**10011+11001**…] but change the problem to 101+101. To balance the boredom of behaving like a simple machine, (C) write the program to for a Turing machine to add two decimal digits the way we added binary numbers, by counting down and counting up.
A8: I believe, based on the logs and the lack of questions, that most had difficulty with the programming of the Turing machine for decimal addition (A7.C). I am therefore continuing that assignment (if you did it you can turn it in again). Also do exercise 5 on p. 98 [Write a table for the Turing machine that will scan a tape containing ones and zeros starting at its right end, and change the first blank to a one if it has seen the sequence 1101011 and to a zero otherwise. All you know about the tape is that it contains only ones and zeros and no intermingled blanks. Test your table with the tapes ..**1**.., ..**00**.., and ..**10100011**.. among others (the results should be respectively, ..**01**.., ..**000**.., and ..**010100011**..) ].
A9: Do Exercise 4 on p. 97 [A state table is given in Table 7.4 that determines if an input table contains more zeros than ones. It does thisno matter how many zeros and ones appear on the tape. The answer is signaled by changing the first blank to the left of the zeroes and ones (we assume that there are no spaces among the ones and zeros) to a zero if zeros predominate, and a one otherwise. Analyze each of the twelve states and describe (in English) what logic it implements. Your result will look like the strategy descriptions given for the decimal/binary conversions. It should not describe in English the individual instructions given to the Turing machine since these have been described by the triple notation and are only suitable for instructing Turing machines. The strategy you express in English is what a person would do if posed with this task, assuming that the tape is too olng to simply count the symbols]. Your answer is a list of 12 sentences. Also do exercise 6 on p. 98 [Write a Turing machine that accepts a tape with a binary number and outputs the tape with the additive inverse (negative) of that binary number. To test for correctness, add the two numbers together and see if they produce all zeros except for a final one that is carried. In a computer there are only so many wirs, so numbers cannot be arbitrarily large. When there is a binary representation of the largest number the computer can hold, and one is added to it, the sume is zero since the carry is lost—there is no wire to which it can move. Thus, all the possible different binary patterns of a given length (on some computers the length is 16, on others it is 32 or 64) are divided in half and those that have a one in the farthest left position are said to be negative. They are the negatives, or additive inverses of the binary numbers that start with zero. For example, on a four-wire computer,0101 represents 5 and 1011 represents –5 because the least significant four columns of their sum all contain zero.].
A10: P. 134: #2 [Translate the flowchart in Figure 10.1 into an NS diagram.]& 4[You want to have a friend, child, clerk, mancine (choose one) be able to translate roman numerals less than 4000 into Arabic. It would also be nice if after reading your instructions, he/she/it/you would be confident that they always worked—i.e., you have described an algorithm. You may used any of the four methods developed in this section to accomplish this task. Once your algorithm is described,you are to indentify all the variables used in it and give a complete trace for each of these roman numerals: I, IX, MCMCDXLIV.].
A11: Build a decision tree that shows all of the solutions of #3b [ADAPT+SHAPE=IDEAS] on p. 48 of Mitchell (refer to the tree on p. 27 [decision tree shown for WIRE+MORE=MONEY])
A12: Do an assessment of your problem-solving style in terms of the recommendations you have read in Mitchell (Polya, Wicklegreen, and Adams) and Ackoff as a follow-up to the question that I asked on strategies on the first exam. This will be accomplished by writing a response to each of the following steps: (1) For each author, what observation(s) or recommendation(s) do you find most appropriate in helping you improve as a problem-solver? (2) What limitations or weaknesses have you recognized in yourself as a problem-solver after appreciating the authors presentations? (3)State one of the previously assigned homework problems that you did not solve correctly and describe your approach. (a) List any advice by any author that pertains to this problem. (b) Categorize the problem and list similar problems and facts that might have been relevant in the solution. (c) State what seems to you to have been the difficulty that had be overcome in order to have a solution.
A13: Explain why when you have a collection of 52 different positive integers, you can ALWAYS find a pair whose sum is a multiple of 100 or whose difference is a multiple of 100
A14: A bowl has both white and black marbles and there are more than three of them. Player A is given the choice of playing two games with player B. The first game is that player A draws a random marble from the bowl (held head-high by player B) and if it is white, he wins. The second game is that player draws a random marble from the bowl and gives it to B without looking at it. B then removes a black marble from the bowl. A now draws a second marble from the bowl and if it is white he wins. Which game should A play if he wants the best chance of winning (and why)?
Projects (done in 3 person teams over three weeks and presented with PowerPoint)
P1: You are given a bag of coins. The denominations of the coins are 1, 2, 3, 4, ...,k, and the higher the value of the coin, the more it weighs: 1, sqrt(2), sqrt(3), 2, sqrt(5),....sqrt(k). Devise a method for splitting the coins in the bag into two piles of equal weight (or as close to equal as is possible). Show that there is no better solution.
P2: An explorer has a jeep and he wants to travel into the desert. There is a gas station at the edge of the desert but it will only allocate 10 fillups to an individual (strange, but true). The jeep will travel x miles on a fillup (it doesn't matter, but suppose a fillup means y gallons). It should be obvious that the jeep could drive x/2 miles out, turn around, and make it back to gas station (and that it could do this 10 times). Devise a strategy by which the jeep can get the greatest distance from the gas station assuming that there is no other source of fuel AND that there is no need to come back (if he can make it far enough out there, someone can meet him from the other side with fuel). Another way to look at the problem is to determine how wide the desert could be if there were two jeeps traveling to meet each other from two gas stations on opposite sides of the desert. The answer would be at least 3x/2 miles since the first jeep could travel x miles and the second jeep meet it at x/2 mile from the opposite side and it would have exactly enough gas to get back with both drivers. How much wider could the desert be than 3x/2?
P3: Five women steal a bag of diamonds and while waiting in a hotel for the cops to leave one of the women decides to take her share (1/5) before the group does the split. When she divides the diamonds she has one left over, which she gives to the maid. She hides her share and puts the rest back in the bag. Later on a second woman has the same idea and sneaks her 1/5 share out of the bag, having one diamond left, which she gives to the maid, and replacing the other 4 shares in the bag. Each of the remaining women do the same, each time finding an excess diamond when the bag is split into five equal groups, and each gives a diamond to the maid. When the heat is off the women meet and divide the bag among them evenly, and once again there is a leftover diamond that is given to the maid. What is the fewest number of diamonds that could have been in the bag initially?