Homework 10 - Part A

Due Tuesday 11-Apr, at 10:00pm

To start

1. Create a folder named hw10a
2. Create a new file hw10a.py in that folder
3. Edit hw10.py and add the functions and some testcases as required
4. When you have completed and fully tested hw10a, submit hw10a.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

• Unlike all other homeworks, this BONUS OPTIONAL homework is collaborative in teams of up to four (yourself and other three current 15-112 students).
• Collaboration is not strictly required, but is very strongly encouraged.
• You may only work with at most three other students (and they must be currently in 15-112), and you may not switch teams once you have worked with a group.
• This must be earnest collaboration, with all of you genuinely working together the whole time. It is not acceptable for one of you to do the work, or any portion of the work, and for the other to copy any portion of that work. All work must come from earnest collaboration from both of you.
• Late submissions are not allowed for this task.
• You must write at the top of the file hw10a.py your name and the name of your collaborators.

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!

1. lowerBound(L, x) [10 pts]
   Write the function lowerBound(L, x) that returns the largest element of L that is strictly less than x. You can assume that L is sorted and contains no duplicates.
   Note: Your solution must be O(logN) where N is the size of the list. The autograder (or a manual CA review later) will reject your submission entirely if your solution is not O(logN).
   Here are some test cases:
   def testLowerbound(): print("Testing lowerBound...") assert(lowerBound([4,7,9,11,12,13,15,16,17], 4) == None) assert(lowerBound([4,7,9,11,12,13,15,16,17], 5) == 4) assert(lowerBound([4,7,9,11,12,13,15,16,17], 6) == 4) assert(lowerBound([4,7,9,11,12,13,15,16,17], 7) == 4) assert(lowerBound([4,7,9,11,12,13,15,16,17], 8) == 7) assert(lowerBound([4,7,9,11,12,13,15,16,17], 20) == 17) print("Passed!")


2. countInRange(L,a,b) [15 pts]
   Write the function countInRange(L, a, b) that returns the number of elements in the open range (a,b), that is, the numbers of elements in L between a and b, both bounds exclusive.
   Note: Your solution must be O(logN) where N is the size of the list. The autograder (or a manual CA review later) will reject your submission entirely if your solution is not O(logN).
   Here are some test cases:
   def testCountInRange(): print("Testing countInRange...") L = [4,7,9,11,12,13,15,16,17] assert(countInRange(L, 4, 7) == 0) assert(countInRange(L, 4, 12) == 3) assert(countInRange(L, 4, 20) == 8) assert(countInRange(L, 1, 3) == 0) assert(countInRange(L, 12, 14) == 1) print("Passed!")