Homework 10 - Part B

Due Tuesday 11-Apr, at 10:00pm

To start

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

You will notice that the skeleton file only includes testcases for some of the functions you are writing. You should write testcases for the others. (You can find some nice ways to test in the write-up below, but you will need to translate those to actual testcases.)

Problems


  1. Big-O Calculation (Manually graded) [25 pts]
    In a triple-quoted string at the top of your file (just below your name), include solutions to this exercise. For each of the following functions:

    1. State in just a few words what it does in general.
    2. Write the Big-O time or number of loops for each line of the program, then state the resulting Big-O of the whole program.
    3. Provide an equivalent Python function that is more than a constant-factor faster (so its worst-case Big-O runtime is in a different function family). The better your solution's Big-O runtime, the more points you get!
    4. Write the Big-O time or number of loops for each line of the new program, then state the resulting Big-O of the whole program.

    def slow1(lst): # N is the length of the list lst assert(len(lst) >= 2) a = lst.pop() b = lst.pop(0) lst.insert(0, a) lst.append(b) def slow2(lst): # N is the length of the list lst counter = 0 for i in range(len(lst)): if lst[i] not in lst[:i]: counter += 1 return counter import string def slow3(s): # N is the length of the string s maxLetter = "" maxCount = 0 for c in s: for letter in string.ascii_lowercase: if c == letter: if s.count(c) > maxCount or \ s.count(c) == maxCount and c < maxLetter: maxCount = s.count(c) maxLetter = c return maxLetter def slow4(a, b): # a and b are lists with the same length N n = len(a) assert(n == len(b)) result = abs(a[0] - b[0]) for c in a: for d in b: delta = abs(c - d) if (delta > result): result = delta return result