Homework 9

Due Tuesday 5-Nov, at 9:00pm

To start

1. Create a folder named hw9
2. Create a new file hw9.py in that folder
3. Edit hw9.py and add the functions and some testcases as required
4. When you have completed and fully tested hw9, submit hw9.py to Gradescope. For this hw, you may submit up to 15 times, but only your last submission counts.

While you may submit to Gradescope as often as you like for this assignment, some questions are not autograded, so you will be responsible for testing your code and making sure it meets the problem requirements.

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 for autograded problems. 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. We are not giving you any starter code this week. That means you need to create your file from scratch and include your own testcases. For writing testcases, follow the style of testcases uses in the previous homeworks.
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.

A Note About Style Grading

Like in the previous assignments, 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 already started, so please use good style from now on!

A few notes on recursion

• 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 or methods if they run in O(1). So in particular, among many other builtins you may not use this week, you may not use upper, lower, 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).

More important notes

• You may not create large extraneous lists or otherwise store more information than what you need to solve the problem. For example, in maxEven(L) you cannot call evensOnly(L) and then take the max of that list, since that gratuitously creates an extraneous list (and, to be technical, uses O(N) space instead of O(1) space as the problem requires). Instead, directly compute maxEven(L) with recursion. In fact, that’s the main point of asking you to solve both evensOnly(L) and maxEven(L): to encourage you to think about the structural differences in these problems and how that affects your recursive logic.
• You may not destructively modify arguments unless the problem explicitly says you should.
• Your functions may not be extremely slow. You do not need to find the absolute best algorithm in most cases, but it must run reasonably quickly (i.e. if your code takes ten seconds to pass our test cases, there is likely another approach you should consider).

Problems

1. Recursion-Only evenCount(L) [10 pts]
   Without using iteration, write the recursive function evenCount(L) which given a possibly-empty list L of integers, returns the number of even integers in L. So: evenCount([5,8,23,42]) returns 2.


2. Recursion-Only evenSum(L) [10 pts]
   Without using iteration, write the recursive function evenSum(L) which given a possibly-empty list L of integers, returns the sum of the even integers in L. Do not create a new list. You cannot use the builtin function sum of lists. Return 0 if the list has no even integers in it. So, evenSum([5,8,23,42]) returns 50.


3. Recursion-Only evensOnly(L) [10 pts]
   Without using iteration, write the recursive function evensOnly(L) which given a possibly-empty list L of integers, returns a new list containing only the even integers in L in the same order they appear in L. So, evensOnly([5,8,23,42]) returns [8, 42].


4. Recursion-Only maxEven(L) [15 pts]
   Without using iteration, write the recursive function maxEven(L) which given a possibly-empty list L of integers, returns the largest even integer in L, or None if L does not contain any even integers. So, maxEven([5,8,23,42]) returns 42.


5. Recursion-Only onlyEvenDigits(L) [15 pts]
   Without using iteration and without using strings, write the recursive function onlyEvenDigits(L), that takes a list L of non-negative integers (you may assume that), and returns a new list of the same numbers only without their odd digits (if that leaves no digits, then replace the number with 0). So: onlyEvenDigits([43, 23265, 17, 58344]) returns [4, 226, 0, 844]. Also the function returns the empty list if the original list is empty. Remember to not use strings. You may not use loops/iteration in this problem.
   
   Hint: We wrote a recursive helper function onlyEvens(n) that takes an integer n and returns the same integer but with all the odd digits removed. So onlyEvens(1234) returns 24.


6. Recursion-Only generateCharacterString(s) [10 pts]
   Write the function generateCharacterString(s) that takes a two-character string and returns a new string that contains the all of the characters (in ascii order) between the first character and the second character. For example, generateCharacterString("ko") would return "klmno". This should also work backwards, so generateCharacterString("ME") would return "MLKJIHGFE". If the initial provided string is not two characters long, return the empty string; if the provided string contains two identical characters (for example, "22"), return that character ("2").


7. Recursion-Only isPalindrome(word) [10 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.


8. Recursion-Only digitCountMapInRange(lo, hi) [20 pts]
   

   Write the recursive function digitCountMapInRange(lo, hi) that takes integers lo and hi, and returns a map of the counts of all the digits that occur in the numbers between lo and hi inclusively.

   For example, for digitCountMapInRange(9, 12), we consider the numbers in the range from 9 to 12. That is: 9, 10, 11, 12. These numbers include one 0, four 1's, one 2, and one 9, so: assert(digitCountMapInRange(9, 12) == { 0:1, 1:4, 2:1, 9:1 }).

   Be sure to handle negative numbers and 0 correctly. For example, for digitCountMapInRange(-1, 3), we consider the numbers in the range from -1 to 3. That is: -1, 0, 1, 2, 3. These numbers include one 0, two 1's, one 2, and one 3, so: assert(digitCountMapInRange(-1, 3) == { 0:1, 1:2, 2:1, 3:1 })