CMU 15-112: Fundamentals of Programming and Computer Science
Homework 10 (Due Saturday 2-Nov at 5pm)
(TP-Mentor Meetings Due by Monday 4-Nov)
Note: this hw is designed to give everyone time to do Hack112 this weekend. Also, this hw is due early (5pm) for the same reason. Hack112 is optional, but we hope that lots of you participate. Have fun!!!!!
Helpful forms (note: you must be authenticated to andrew.cmu.edu for these to work):
- 15-112-f19 Extension Request Form
- Note: this week's booster sessions do not have any requirements for attending, though we strongly encourage you to invest 4+ hours into the hw before attending, in order to get anything useful out of them.
- Also: even with this change, you may not take any notes or in any way record any solutions provided during the booster sessions.
A few more notes:
- You may (and in fact must) finally use recursion this week.
- Every problem this week requires that you use recursion meaningfully in order to receive the points.
- You also may not use loops -- no
whileloops this week!
- You may use helper functions, so long as they are recursive and not iterative.
- You may use wrapper functions -- that is, your solution function may itself be a non-recursive 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 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). Also, note that slicing (L[i:j]) is just fine this week.
- Do not hardcode the test cases in your solutions.
- Even though we have split writing-sessions into their own separate category, homeworks will continue to be out of 75 points instead of 100 points so that each hw is equally weighted.
- Term Project Ideation & Hw9 Meeting [10 pts] [manually graded] [due by Monday night]
This week, you will be receiving your assigned Term Project mentor. They will reach out to you regarding times to meet for 15-20 minutes between now and next Monday (4-Nov). In this meeting, you will be discussing ideas you have regarding what you hope to accomplish in your Term Project (which will be formally introduced in Week 11). After you solidify a plan of action on that front, you will then have 5 minutes (no more!) show your mentor your hw9 sidescroller game for grading purposes, where they will go through the checklist of requirements from the write-up with you and grade your submission accordingly. This grading format is similar to how your actual Term Project will be graded. Please plan your 5-minutes so you cover everything needed for grading purposes in that time.
- Recursion-Only alternatingSum(L) [10 pts] [autograded]
Write the function alternatingSum(L) that takes a possibly-empty list of numbers, and returns the alternating sum of the list, where every other value is subtracted rather than added. For example: alternatingSum([1,2,3,4,5]) returns 1-2+3-4+5 (that is, 3). If L is empty, return 0. You may not use loops/iteration in this problem.
- Recursion-Only onlyEvenDigits(L)  pts] [autograded]
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.
- Recursion-Only powersOf3ToN(n) [15 pts] [autograded]
Write the function powersOf3ToN(n) that takes a possibly-negative float or int n, and returns a list of the positive powers of 3 up to and including n. As an example, powersOf3ToN(10.5) returns [1, 3, 9]. If no such powers of 3 exist, you should return the empty list. You may not use loops/iteration in this problem.
- Recursion-Only binarySearchValues(L, item) [15 pts] [autograded]
Recall the Binary Search algorithm which we discussed earlier this semester: start with two indexes, hi and lo, with hi equal to the largest index in L (len(L)-1), and lo to the smallest (0), then set mid to the middle index ((hi+lo)//2) and check if L[mid] equals the item. If so, we're done! If not, then if L[mid] is too small, set lo to mid+1 (not to mid, since we know mid is wrong!), otherwise set hi to mid-1. Continue until we find the element or lo exceeds hi.
With this in mind, write the function binarySearchValues(L, item) that takes a sorted list and a value and returns a list of tuples, (index, value), of the values that Binary Search must check to verify whether or not the item is in the list. You may not use loops/iteration in this problem.
binarySearchValues(['a', 'c', 'f', 'g', 'm', 'q'], 'c')should return
[(2, 'f'), (0, 'a'), (1, 'c')]. On the other hand,
binarySearchValues(['a', 'c', 'f', 'g', 'm', 'q'], 'n')should return
[(2, 'f'), (4, 'm'), (5, 'q')], since 'n' cannot be found.
Hint: our sample slution did not use slicing here (though of course we did use list indexing, as in L[mid]), but rather just kept track of the lo and hi indexes as they changed.
- Recursion-Only secondLargest(L) [15 pts] [autograded]
Note: recall that you may not use sort, sorted, min, or max this week! With that in mind, write the function secondLargest(L) that takes a list of integers in any order and returns the second-largest value in the list. To be more precise, it returns the second value from the end if the list was sorted (though you do not need to sort it to solve this problem), so if the largest value occurs twice, you would return that value. Also, if there are fewer than 2 values in the list, return None. Here are some test cases:assert(secondLargest([1,2,3,4,5]) == 4) assert(secondLargest([4,3]) == 3) assert(secondLargest([4,4,3]) == 4) assert(secondLargest([-3,-4]) == -4) assert(secondLargest() == None) assert(secondLargest([ ]) == None)Again, you do not need to sort the list. We didn't sort it in our sample solution. We just tracked the two largest values as we recursively traversed the list. Also, you may not use loops/iteration in this problem.
Note: there is no bonus on this hw. Instead, we strongly encourage you to attend and participate in Hack112!!! Have fun!!!!