Homework 6

Due Tuesday 19-Oct, at 10:00pm

To start

1. Create a folder named ‘hw6’
2. Download hw6.py to that folder
3. Edit hw6.py and modify the functions as required
4. When you have completed and fully tested hw6, submit hw6.py to Gradescope. For this hw, you may submit up to 15 times, but only your last submission counts.

Some important notes

1. This homework is solo. You may not collaborate or discuss it with anyone outside of the course, and your options for discussing with other students currently taking the course are limited. See the academic honesty policy for more details.
2. After you submit to Gradescope, make sure you check your score. If you aren’t sure how to do this, then ask a CA or Professor.
3. There is no partial credit on Gradescope testcases. Your Gradescope score is your Gradescope score.
4. Read the last bullet point again. Seriously, we won’t go back later and increase your Gradescope score for any reason. Even if you worked really hard and it was only a minor error…
5. Do not hardcode the test cases in your solutions.
6. The starter hw6.py file includes test functions to help you test on your own before you submit to Gradescope. When you run your file, problems will be tested in order. If you wish to temporarily bypass specific tests (say, because you have not yet completed some functions), you can comment out individual test function calls at the bottom of your file in main(). However, be sure to uncomment and test everything together before you submit! Ask a CA if you need help with this.
7. Remember the course’s academic integrity policy. Solving the homework yourself is your best preparation for exams and quizzes; cheating or short-cutting your learning process in order to improve your homework score will actually hurt your course grade long-term.

Limitations

Do not use try/except or classes recursion this week. The autograder (or a manual CA review later) will reject your submission entirely if you do.

A Note About Style Grading

Like in the previous assignment, we will be grading your code based on whether it follows the 15-112 style guide. We may deduct up to 10 points from your overall grade for style errors. We highly recommend that you try to write clean code with good style all along, rather than fixing your style issues at the end. Good style helps you code faster and with fewer bugs. It is totally worth it. In any case, style grading starts this week, so please use good style from now on!

A Note About Testing

You will notice that the skeleton file does not include testcases. We advise you to write test cases. (You can find some nice ways to test in the write-up below, but you will need to translate those to actual testcases.)

A few notes on the problems marked recursive:

• You may (and in fact must) finally use recursion this week.
• The recursive problems require that you use recursion meaningfully in order to receive the points.
• You also may not use loops -- no for loops or while on the problems marked recursive.
• You may use helper functions, so long as they are not iterative.
• You may use wrapper functions -- that is, your solution function may itself be a non-recursive (but also non-iterative) wrapper around a recursive helper function.
• You may only use builtin functions if they don't iterate over something. So in particular, among many other builtins you may not use this week, you may not use sum, sort, sorted, min, or max this week (you can write your own recursive versions of these if you wish, though that is not required, and we did not do that for our sample solutions).

1. Midsemester Survey [5 pts]
   Take the midsemester survey linked from Piazza. Be sure to also fill out the second survey (linked at the end of the first) so that you get the points. The survey is due Sunday, October 17 at 5:00pm.


2. invertDictionary(d) [30 pts]
   Write the function invertDictionary(d) that takes a dictionary d that maps keys to values and returns a dictionary of its inverse, that maps the original values back to their keys. One complication: there can be duplicate values in the original dictionary. That is, there can be keys k1 and k2 such that (d[k1] == v) and (d[k2] == v) for the same value v. For this reason, we will in fact map values back to the set of keys that originally mapped to them. So, for example:
   assert(invertDictionary({1:2, 2:3, 3:4, 5:3}) == {2:set([1]),3:set([2,5]), 4:set([3])})
   Also, you may assume that the values in the original dictionary are all immutable, so that they are legal keys in the resulting inverted dictionary.


3. destinationCity(paths) [20 pts]
   You are given a dictionary paths, where paths[cityA] = cityB means there exists a direct path going from cityA to cityB. Return the destination city, that is, the city without any path outgoing to another city. It is guaranteed that the paths form a line without any loop, therefore, there will be exactly one destination city. Consider the following examples:
   paths = { 'London': 'New York', 'New York': 'Lima', 'Lima': 'Sao Paulo' }
   The destination city is "Sao Paulo". Starting at any city you will reach "Sao Paulo" city which is the destination city. For instance, starting at "London" city, our trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".
   paths = { 'B': 'C', 'D','B', 'C':'A'} }
   All possible trips are:
   "D" -> "B" -> "C" -> "A". "B" -> "C" -> "A". "C" -> "A". "A".
   Clearly the destination city is "A".


4. groupAnagrams(S) [20 pts]
   Given a list of strings S, group the anagrams together. Two strings are anagrams if each can be reordered into the other. Treat "a" and "A" as the same letters (so "Aba" and "BAA" are anagrams). The function should return a list of groups, in any order. Each group is a set of strings where all the strings are anagrams of each other. Some examples:
   S = ["eat","tea","tan","ate","nat","bat"]
   groupAnagrams(S) will group the strings in the following way:

   [{"bat"},{"nat","tan"},{"ate","eat","tea"}]
   

   S = ["own", "read", "dare", "eat", "now", "stop", "now", "spot", "15112", "tea"]
   groupAnagrams(S) will group the strings in the following way:

   [{"own", "now"}, {"read","dare"}, {"eat","tea"}, {"stop", "spot"}, {"15112"}]
   

   The order of the groups in the returned list is not important. The size of S will be large, therefore you should avoid using lists operations as much as possible, otherwise your solution will be too slow and will timeout. We expect that your code processes an input of 30K words in less than a minute.


5. recursive isPalindrome(word) [15 pts]
   A string is a palindrome if it is exactly the same forwards and backwards. Write a recursive function that takes a string and returns True if the string is palindrome, False otherwise. For example,
   assert(isPalindrome("abcba")==True) assert(isPalindrome("accba")==False) assert(isPalindrome("a")==True)
   Your solution should not use any loops; you must solve the problem using recursion.


6. recursive capitalizeWords(wordList) [10 pts]
   Write a recursive function that takes a list of words and returns a list that contains all the words capitalized. For example,
   assert(capitalizeWords(['foo', 'bar', 'world', 'hello']) == ['FOO', 'BAR', 'WORLD', 'HELLO'])
   Your solution should not use any loops; you must solve the problem using recursion.