CMU 15-190 Spring 2017: Topics in Intermediate Programming
Homework 6 (Due Wednesday 8-Mar, at 11:59pm)

• This hw is optional. It is for students who want to get a bit more out of the optional/advanced talk last week, and in particular for those who may wish to get 3 units of pass/fail credit for 15-190 (for whom it is required). We hope that's quite a few of you!


• Work Solo or in Groups of 2-5 (and groups are strongly recommended) Have fun!


• We will grade the hw, but loosely, and chiefly based on effort. You should expect to invest 1-2 hours on it and you'll be fine. This is not about the grade, of course, but about the learning. So take your time, discuss issues with your groupmates, have fun, and enjoy.


• Please track when you start and stop working on this, and with whom you collaborate. You'll need that for your submission. And again, have fun.

1. 1 is Breadth-First Search, what about 42?
   First, find some reasonable way to confirm in practice that a heuristic function that always returns 1 converts A* (a-star) into good old breadth-first search. Then, see what happens with a heuristic function of 42. That's not admissible, so maybe something awful happens. Does it?


2. A worse heuristic
   In lecture, we briefly discussed a worse but still admissible heuristic: instead of adding all the distances to the target locations for each missplaced value, instead just count all the misplaced values. This still works, but it's not as good. Here, you will verify that. Compare the two heuristics on the same examples, and report on how much worse this simplified heuristic is in practice.


3. A faster queue (deque)
   In our breadth-first-search implementation, we used a good old list as a queue, but we noted this was inefficient -- you can add to the end of lists quickly, but popping from the start is inefficient. We mentioned that Python has a better data structure for that. Here, you explore this. First, read about the deque. Then, implement breadth-first search using a deque instead of a list. Compare the runtimes, and report on how much better a deque was in practice here.


4. Fixing our ridiculous __lt__ method
   First, discuss amongst yourselves why we had to implement the __lt__ method to allow the heap to compare two State instances using <. Since it really didn't matter to us which way the result turned out, we just had __lt__ return False always, which is bogus, but worked here. Sigh. Here, we will fix that. First, add a field, totalCost, to each state, and when the state is created, compute its total A* cost (distance of the path to that state plus the admissible heuristic distance to a goal state). Second, change the __lt__ method so that (s1 < s2) is True if s1's totalCost is < s2's totalCost. Now, since State instances are comparable in this way, instead of adding (totalCost, state) to the heap, just add the state itself. That should work just fine, and is a much cleaner way to design things here.


5. What to Submit
   Each member of the group should submit their own PDF file, 15-190-hw4.pdf, containing this information:
   1. Your name and andrew id
   2. The names and andrew id's of your groupmates
   3. The start/stop times you worked, and the total time you worked.
   4. Your thoughts about this exercise -- useful, interesting, etc? This will help us improve the 15-190 experience as we go.
   5. The solutions from above. Note: one way to create a PDF is to first make a Word file, then export that to PDF.
   You can submit your hw to the 15-190 autolab site here.