Homework 2

Due Tuesday 23-Jan, at 9:00pm

To start

  1. Create a folder named ‘hw2’
  2. Download hw2.py to that folder
  3. Edit hw2.py and modify the functions as required
  4. When you have completed and fully tested hw2, submit hw2.py to Gradescope. For this hw, you may submit up to 20 times (which is way more than you should require), 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 hw2.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.
  8. Do not use string indexing, lists, list indexing, or recursion this week. The autograder will reject your submission entirely if you do.

Problems

  1. containsOddDigits [5 pts]
    Write the function containsOddDigits(x) that takes an integer, x, and returns True if it contains any odd digits, and False otherwise.
    Hint: In this and in future problems, you'll need to get individual digits from numbers. You may want to write some helper functions, getKthDigit and numberLength, to do this.

  2. printNumberTriangle [10 pts]
    Time for something a little different! Instead of returning a value, in this function you'll be printing out results. Write the function printNumberTriangle that takes one integer, n, and prints out a number triangle based on n. For example, given the number 4, this function would print out
    1
    21
    321
    4321

    Note: the autograder for this problem is very finicky about whitespace; it expects no spaces, and only one newline after each number line. Make sure your output matches what it expects!

  3. hasConsecutiveDigits(n) [10 pts]
    Write the function hasConsecutiveDigits(n) that takes a possibly-negative int n and returns True if somewhere in n some digit occurs consecutively (so the same digit occurs twice in a row), and False otherwise. For example, these numbers have consecutive digits: 11, -543661, 1200, -1200, and these numbers do not: 1, 123, 12321, -12321.

  4. isPalindromicNumber(n) [15 pts]
    Write the function isPalindromicNumber(n) that takes a non-negative int n and returns True if that number is palindromic and False otherwise. A palindromic number is the same forwards as backwards. For example, these numbers are palindromic: 0, 1, 99, 12321, 123321, and these numbers are not: 1211, 112, 10010.

  5. longestCommonDigitStart [15 pts]
    Write the function longestCommonDigitStart(x, y) that takes two non-negative integers, x and y, and returns the digits that match between the two integers, starting from the ones digit. For examples, the pair (1234, 2134) returns 34 because two digits match from right to left, 4 with 4 and 3 with 3. The pair (2223, 23) also has two matches, and the solution is 23. If there's no common digit start, the function should return None. For example, the pair (1234,4321) has no common start, and the result should be None. Here are a few more examples:
    longestCommonDigitStart(15112, 15112) == 15112 longestCommonDigitStart(763426548, 7346548) == 6548 longestCommonDigitStart(973492739487234, 1) == None longestCommonDigitStart(10, 20) == 0
    Hint: If you want, you can reuse your helper functions, getKthDigit and numberLength, to do this.

  6. carrylessAdd(x, y) [20 pts]
    First, you may wish to read the first page (page 44) from here about Carryless Arithmetic. Or, just understand that carryless addition is what it sounds like -- regular addition, only with the carry from each column ignored. So, for example, if we carryless-ly add 8+7, we get 5 (ignore the carry). And if we add 18+27, we get 35 (still ignore the carry). With this in mind, write the function carrylessAdd(x, y) that takes two non-negative integers x and y and returns their carryless sum. As the paper demonstrates, carrylessAdd(785, 376) returns 51.

  7. nthCircularPrime [25 pts]
    A circular prime is a number with the property that any rotation of that number's digits is prime. In this case, rotation refers to cycling the digits of a number; for example, the rotations of 1234 are 1234, 2341, 3412, and 4123. You can read more about this on the Wikipedia page. Single-digit primes are all circular, of course. To find the nth circular prime, you'll need to write isPrime and three other functions:

    1. rotateNumber
      This function takes a number, x, and rotates that number's digits by one place. This would turn the number 1234 to 4123.

    2. isCircularPrime
      This function takes a number, x, and determines whether that number is a circular prime. To do this, you'll need to check whether every rotation of the number is prime.

    3. nthCircularPrime
      This function takes a number, n, and returns the nth circular prime.


  8. bonusCarrylessMultiply(x, y) [2 pts]
    Write the function bonusCarrylessMultiply(x, y), that works similarly to carrylessAdd(x, y), based on this paper on Carryless Arithmetic. This paper shows that bonusCarrylessMultiply(643, 59) returns 417. Hint: it may help if you do this differently than usual long multiplication. Instead of working by rows in the output, work by columns. So first compute all the ones digit values, and sum those mod 10. Then compute all the tens digit values, and sum those mod 10. And so on. You may assume x and y are non-negative. Hint #1: do not solve bonusCarrylessMultiply(x, y) by simply calling carrylessAdd(x, result) a total of y times. That is wrong on two levels. First, it is simply too inefficient (what if we are multiplying 20-digit numbers?). Second, it is also wrong algorithmically! Carryless multiplication is not like normal multiplication, and if we take + to be carryless addition and * to be carryless multiplication, then it is not necessarily true that (x * y) is the same as (x + x + ... + x + x) for a total of y x's. Yikes. So: stick with the next hint (see below). It also uses carrylessAdd and is fairly straightforward, but it is reasonable efficient and algorithmically correct. Good luck with it. Hint #2: Here's a hint on one way to solve this problem (there are many ways, and this way is not the most efficient, to be sure, but it is efficient enough and it is perhaps among the clearest and easiest ways). Consider multiplying 123 * 456. Observe that: 123 * 456 = 123 * 4 * 100 + 123 * 5 * 10 + 123 * 6 in this way, we actually only have to multiply 123 times a single digit each time, then multiply that result by the right power of 10. Right? Ok, so now, to multiply by a single digit, we can instead just add that many times. That is: 123 * 6 == 123 + 123 + 123 + 123 + 123 + 123 Why is that interesting? If we take + to be carryless addition and * to be carryless multiplication, (x * y) is the same as (x + x + ... + x + x) if y is a one-digit number. Because we already have carrylessAdd, so we can just use that to do all this addition. Of course, multiplying by simply adding is very inefficient. But since we are only doing it for multiplying by a single digit, there's a max of 9 additions (8 if you think about it), and so it's not so inefficient. It's actually acceptable, if not ideal, and certainly good enough for hw2, though again better approaches do exist. Hope this helps. And, again, you can safely ignore all of this and solve this problem any way you wish.