15-112
Fall-19

Home

Syllabus

Schedule

Gallery

Staff

Piazza

Autolab

OH Queue

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):
  • Download all of these to that folder:
  • Edit hw10.py
  • When you have completed and fully tested hw10, submit hw10.py to Autolab. For this hw, you may submit up to 5 times, but only your last submission counts.
    • A few more notes:
    1. 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.

    2. 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.

    3. Recursion-Only onlyEvenDigits(L) [10] 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.

    4. 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.

    5. 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.

      For example, 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.

    6. 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([4]) == 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!!!!