Homework 4

Due Tuesday 21-Sep, at 10:00pm

To start

  1. Create a folder named ‘hw4’
  2. Download hw4.py to that folder
  3. Edit hw4.py and modify the functions as required
  4. When you have completed and fully tested hw4, submit hw4.py to Gradescope. For this hw, you may submit up to 15 times, but only your last submission counts.

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. 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. The starter hw4.py file includes test functions to help you test on your own before you submit to Gradescope. When you run your file, problems will be tested in order. If you wish to temporarily bypass specific tests (say, because you have not yet completed some functions), you can comment out individual test function calls at the bottom of your file in main(). However, be sure to uncomment and test everything together before you submit! Ask a CA if you need help with this.
  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.

Limitations

Do not use sets, dictionaries, try/except, classes, or recursion this week. The autograder (or a manual CA review later) will reject your submission entirely if you do.

A Note About Style Grading

Like in the previous assignment, 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 starts this week, 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.)

  1. vowelCount(s) [10 pts]
    Write the function vowelCount(s), that takes a string s, and returns the number of vowels in s, ignoring case, so "A" and "a" are both vowels. The vowels are "a", "e", "i", "o", and "u". So, for example:
    assert(vowelCount("Abc def!!! a? yzyzyz!") == 3) # two a's and one e

  2. rotateStringLeft(s, n) [10 pts]
    Note: To receive credit, do not use loops on this problem.
    Write the function rotateStringLeft(s, n) that takes a string s and a possibly-negative integer n. If n is non-negative, the function returns the string s rotated n places to the left. If n is negative, the function returns the string s rotated |n| places to the right. So, for example:
    assert(rotateStringLeft('abcd', 1) == 'bcda') assert(rotateStringLeft('abcd', -1) == 'dabc')

  3. isRotation(s, t) [10 pts]
    Write the function isRotation(s, t) that takes two possibly-empty strings and returns True if one is a rotation of the other. Note that a string is not considered a rotation of itself.
    Hint: rotateStringLeft may be helpful here.

  4. nondestructiveRotateList(L, n) [10 pts]
    Write the function nondestructiveRotateList(a, n) which takes a list L and an integer n, and nondestructively modifies the list so that each element is shifted to the right by n indices (including wraparound). The function should then return this new list. For example: 
    nondestructiveRotateList([1,2,3,4], 1) -> [4,1,2,3]
nondestructiveRotateList([4,3,2,6,5], 2) -> [6, 5, 4, 3, 2]
nondestructiveRotateList([1,2,3], 0) -> [1,2,3]
nondestructiveRotateList([1, 2, 3], -1) -> [2, 3, 1]

  5. destructiveRotateList(L, n) [10 pts]
    This function works the same as the previous function, only here it is destructive. That is, it directly changes the list L, so after the call, that exact list is rotated n indices to the right with wraparound, and a new list is not created. As usual for destructive functions, this function returns None. Also: you may not call the nondestructive version here, and in fact, you may not even create a new list (or tuple or other similar data structure). You must modify the original list in place (list methods are your friends!).

  6. mostFrequentSubstring(text, n) [20 pts]
    Given a string text your task is to find the most frequently occuring substring of a given length. In the event of a tie between two substrings, follow alphabetic order. Consider the following example in which the length is three (n = 3) and the text is just baababacb. The most frequent substring would then be aba because this is the substring with size 3 that appears most often in the whole text (it appears twice) while the other six different substrings appear only once (baa ; aab ; bab ; bac ; acb). You can assume length >= 0. Here are more examples:
    assert(mostFrequentSubstring("baababacb", 3) == "aba") assert(mostFrequentSubstring("thequickbrownfoxjumpsoverthelazydog", 1) == "o") assert(mostFrequentSubstring("testingthecodetofindtheerrortestandtestagain", 4) == "test")

  7. getEvalSteps(expr)[30 pts]
    Write the function getEvalSteps(expr), that takes a string containing a simple arithmetic expression, and returns a multi-line string containing the step-by-step (one operator at a time) evaluation of that expression. For example, this call: 
    getEvalSteps("2+3*4-8**3%3")
    produces this result (which is a single multi-line string): 
    2+3*4-8**3%3 = 2+3*4-512%3
             = 2+12-512%3
             = 2+12-2
             = 14-2
             = 12
    Here are some considerations and hints:
    • You are only responsible for legal input as described below. Numbers are limited to non-negative integers.
    • Operators are limited to +, -, *, //, %, and **.
    • All operators are binary, so they take two operands. So there are no unary operators, meaning "-5" is not a legal input. For that, you'd need "0-5".
    • In fact, the previous restriction is even stronger: no intermediate value of expr can be negative! So "1-2+3" is not legal, since it would be converted first into "-1+3" which is not legal. So you can safely ignore all such cases.
    • There are no parentheses.
    • Operators must be evaluated by precedence (** first, then *,//,%, then +,-).
    • Equal-precedence operators are evaluated left-to-right.
    • Evaluation proceeds until a single integer with no operators remains after the equals sign.
    • The equal signs must all be stacked directly over each other.
    • You may write this however you wish, though you may want to write a helper function that finds the next operator to be applied, and another helper function that just applies a single operator. Something like that. In any case, top-down design is crucial here. And don't forget to thoroughly test your helper functions before using them!
    • In our sample solution, we used very few string methods, just "find" and "isdigit". You may use others, but you should not spin your wheels trying to find that awesome string method that will make this problem remarkably easier, as that method does not exist.
    • For this function, as any other function, you may not use the eval function, so you will have to write your own equivalent just for the kinds of simple expressions you will deal with here. Eval is dangerous and should be avoided, as it can lead to serious bugs or security holes.