This question is designed to emphasize and reward the use of relationships in designing recursive func- tions. It's stra

[answerhappygod]

This Question Is Designed To Emphasize And Reward The Use Of Relationships In Designing Recursive Func Tions It S Stra 1 (132.36 KiB) Viewed 45 times

This question is designed to emphasize and reward the use of relationships in designing recursive func- tions. It's straight-forward if you look at it from a certain point of view, but difficult if you insist that staring at a computer is a good way to solve problems. The function that answers this problem can be written in 5-8 lines of Python code (not counting the doc-string interface). The entire problem is figuring out what the relationships are. And the code is absolutely trivial once you have the relationship right. You will know you have the relationships right because they make sense as relationships, not as Python code. A small part of your grade for this question is the actual code, but much more weight is given to whether or not you can explain the relationship that the function makes use of. Problem: The problem starts with a room. The room will always be rectangular (a square is a special kind of rect- angle, so they're allowed), but we will vary the dimensions. The room will be subdivided into an integer number of squares of equal size. Think of the squares as "tiles.' In general, the room will be a tiles wide, and b tiles long. Furthermore, a and b are integers, and always positive (a > 0 and b > 0). Mothra is in the room, trying to get from one corner of the room to the other. They will always start on the tile in the lower left corner of the room, and will always have to get to the tile in the top right corner of the room. Mothra's movement is constrained by the rule that they cannot move diagonally from one tile to another. Mothra can only move to an adjacent tile on the same row, or on the same column, but not diagonally. And of course, Mothra cannot go outside the room. Mothra wants to follow a path that is as short as possible, counting tiles as distance. A path is a sequence of tiles that Mothra can move to. The shortest path has a +b - 1 tiles on it, including the starting tile and the ending tile. Furthermore, and this is where the fun begins, there are possibly several paths that are all equally short, with the same number of tiles. These paths all share the same property: on a shortest path, Mothra can move to an adjacent tile, and can only move up one tile (up or 'north"), or to the right one tile (right, or 'east"). If Mothra moves ("south"), or left ('west"), they cannot be on a shortest path. Note: Unlike the previous question, the room is not a maze, but simply a big open room.

In the diagram below, we show a 3 x 4 room, and two valid shortest paths that Mothra could take. 12 a b The question is, in a room of a x b tiles, how many different shortest paths could Mothra take (obeying the movement constraints above)? We want to count paths that are different, and we want to count all the paths. Some paths have a number of tiles in common. For example, two paths can start the same way. but then at some tile, they split. Likewise, two paths that start separately might join up and end the same way (see the red an blue paths above). These would all be separate paths. The only reason to give these examples is to clarify what a path is. (a) Design and implement a recursive function called MothraCount() that is given a and b (the size of the room, in tiles), and returns the total number of shortest paths Mothra could take to get from the bottom left to the top right of the room. (b) Use your recursive function to calculate the number of paths for each of the following cases: • 3x3 4x4 . 10 x 12 This can be done in your script. (c) For each base case in your function, briefly explain (a sentence or two) what the base case represents, and why the answer (which should be simple) is correct. It's okay if your function has several base cases, or only one. (d) For each recursive case in your function, briefly explain (2-5 sentences should do) how the problem size is made smaller, and how you build up the solution using the answer from a smaller problem size. It's okay if your function has several recursive cases, or only one.

Hints • When you're thinking about this problem. it's natural to try to count the paths by finding all of them. That's fine, as you're trying to look for patterns, and for small values of a and b. But your recursive function should not try to build any paths: counting them is much simpler than finding them all. • Use the recursion template (Chapter 19.2). What to Hand In 1. A file called a8q5.py containing: Your recursive MothraCount() function and the code for the three examples listed part (b). 2. A file called a8q5.txt containing: Rour explanations for parts (c) and (d). Be sure to include your name, NSID. student number, course number and laboratory section at the top of all documents. Evaluation • (4 marks) MothraCount() function is recursive, and correctly counts the number of paths. • (3 marks) Explanation of the base case(s) conveys that you understood what the code is doing. . (3 marks) Explanation of the recursive case(s) conveys that you understood what the code is doing. For Fun (Optional, Not Worth Marks) 1. There is a simple recursive program that solves the problem, which will get you full marks, but it's very slow when a and b get bigger. Give an argument for the time complexity of the simple program. Can you establish the space complexity, i.e., how much space it uses? 2. Find a way to make the simple program fast. In other words, find an algorithm whose worst case time complexity is much better than the simple program. Establish the time and space complexity of the improved algorithm. 3. Solve the problem without recursion.