CMU 15-112: Fundamentals of Programming and Computer Science
Homework 12 (Due Wednesday 3-Aug at 8pm ET)

---

Note: Sorry, there is no bonus this week. Instead, use the extra time to get read for the final and come up with great term project ideas.

---

1. As usual, this homework is solo. You must not collaborate with anyone (besides current course TA's and faculty) in any way. See the syllabus for more details.
2. To start:
   1. Create a folder named 'hw12'
   2. Download all of these to that folder, and note that we are using cs11_n22_hw12_linter.py for this assignment:
      • hw12.py
      • cs112_n22_hw12_linter.py Note: This is not the week 5 linter!
   3. Edit hw12.py
   4. When you have completed and fully tested hw12, submit hw12.py to Autolab. For this hw, you may submit up to 5 times, but only your last submission counts.
3. Do not hardcode the test cases in your solutions.

A few more notes:

• You may (and in fact must) use recursion this week.
• Every problem this week requires that you use recursion meaningfully in order to receive the points. The assignment will be autograded, but we may manually review submissions and apply deductions to solutions that do not meaningfully use recursion or which use prohibited components.
• Unlike in hw11, you may use for loops or while loops, as long as you also use recursion meaningfully in each problem.
• You may not use any functions or methods which we have not covered in the course notes. You also many not use enums, enumerate(), eval() or similar evaluating functions/methods.

---

Homework 12 Overview:

1. evalPrefixNotation(L) [50 pts]
2. knightsTour(rows, cols) # with backtracking [50 pts]

---

1. evalPrefixNotation(L) [50 pts] [autograded]
   Background: in so-called 'prefix notation', an arithmetic expression is listed with the operator first. So instead of writing '2 + 3' we would write '+ 2 3'. Actually, for this problem, we'll represent the expression in a list, so we'd write ['+', 2, 3]. Each value can itself be another full expression, so for example we could have:

       ['+', 2, '*', 3, 4]
   

   This would be the same as (2 + (3 * 4)), or 14. Again, we could have:

       ['+', '*', 2, 3, '*', 4, 5]
   

   This would be the same as ((2 * 3) + (4 * 5)), or 26. Look at the test function in the code for a few more examples.
   
   With this in mind, write the recursive function evalPrefixNotation(L) that takes a list L that contains a legal arithmetic expression in prefix notation, as just described, and returns the value that the expression evaluates to. You may not use enums, enumerate(), eval() or similar evaluating functions/methods.
   
   Your function only needs to work for '+', '-', and '*'. If you see any other operators, raise an exception as such:

       raise Exception('Unknown operator: ' + operator)
   

   
   Hints:
   1. After removing the first element, if it is an operator, you should use evalPrefixNotation to recursively evaluate the operands for that operator.
   2. This is not a backtracking problem!
   3. Evaluate the list from left to right, and look at the test cases in the starter file!
   
   Take the time to really think about that hint! Also, for what it is worth, our sample solution used L.pop(0) to destructively remove the first element. We could then test if it was a string (and so an operator, like '+', or '-', etc) and do one thing, or if it is an int, and do something else.


2. knightsTour(rows, cols) # with backtracking [50 pts] [autograded]
   First, read about the Knight's Tour problem here. Next, write the function knightsTour(rows, cols) that takes rows and cols as non-negative ints and returns a 2d list of a knight's tour on a rows-by-cols board, or None if this does not exist. This is a slight generalization since here we will allow non-square rectangular boards.
   
   Following these instructions, knightsTour(4, 5) should return a legal 4x5 knight's tour, such as this one:

   [
    [ 1, 14,  5, 18,  7], 
    [10, 19,  8, 13,  4],
    [15,  2, 11,  6, 17],
    [20,  9, 16,  3, 12]
   ]
   

   Here we see that the tour started at 1, which is at the top-left corner. Then following the sequence 1,2,3,... to follow each move in order.
   
   Note that it is possible for some dimensions that there is a legal knight's tour, only not one starting at the top-left corner. You will have to account for that in your solution.
   
   Also: backtracking can be slow, and your solution will probably not run fast enough after 6-by-6 or so. That's ok. :-)
   
   Hint: if your solution is "correct" but takes a long time to run, you may be able to speed it up by placing the 1st number before calling your backtracker. Most (but possibly not all) boards we will consider have a solution with 1 in the top-left corner. So you can just use the usual nested for loops to place the 1 in every possible location, but first at (0,0), and then backtracking from there. That may well speed things up a bit.
   
   Optional extra challenge: speed this up even more! There are techniques that can make this work fast enough for somewhat larger boards (though they still bog down eventually). You can do some pondering of your own, or some internet sleuthing, but in any case, try to make this run faster. Or not, since it is optional.
   
   In any case, have fun!

---