Homework 2

Due Tuesday 21-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 15 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 [10 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. isLangfordPairing [15 pts]
    Complete the problem isLangfordPairing(n) from CS Academy. You must solve the problem directly on the website, doing all of your testing there. Do not write the solution in Thonny (or a different IDE) and copy/paste it into the website.

  4. longestDigitRun [20 pts]
    Write the function longestDigitRun(n) that takes a possibly-negative int value n and returns the digit that has the longest consecutive run, or the smallest such digit if there is a tie. So, longestDigitRun(117773732) returns 7 (because there is a run of 3 consecutive 7's), as does longestDigitRun(-677886).

  5. carrylessAdd(x, y) [20 pts]
    First, you may wish to read the section "The Carryless Islands" (starting on page 1) 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.

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


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