CMU 15-112: Fundamentals of Programming and Computer Science
Check2 Practice (check2 in class on Tue 6-Sep)

• These problems will help you prepare for check2.
• To start:
  1. Create a folder named 'week2'
  2. download both check2.py and cs112_f16_wk2.py to that folder
  3. Edit check2.py using pyzo
• Do not use strings, lists, or recursion this week.
• Do not hardcode the test cases in your solutions.

0. Week1 time report and brief reflection
   First, if you have not done so already, take a brief moment to fill out this week1 time report and brief reflection. Thanks!


1. Loops notes and videos
   Next, carefully watch the videos and review the notes on Loops. Be sure to thoroughly understand them before proceeding to the next step!


2. Code Tracing
   What will this code print? Figure it out by hand, then run the code to confirm. Then slightly edit the code and try again.
   • Trace #1 of 3:
     
     def ct1(m, n): total = 0 for x in range(m, n+1, 3): print('x =', x) total += x for y in range(m, m+2): print('y = ', y) total += y return total print(ct1(1,9))
   
   
   • Trace #2 of 3:
     
     def ct2(n): k = 0 total = 0 while (n >= k): print('k =', k) for i in range(k): total += n%10 n //= 10 print(i, n%10, total) k += 1 print('total =', total) print(ct2(1234))
   
   
   • Trace #3 of 3:
     
     def ct3(z): total = 0 for y in range(z,1,-1): if (y % 2 == 0): print('skip y =', y) continue total += y if (total > 20): print('break at y =', y) break return total print(ct3(10))


3. Reasoning Over Code
   Find parameter(s) to the following functions so that they return True. Figure it out by hand, then run the code to confirm. There may be more than one correct answer for each function, and you can provide any one of them.
   • RC #1 of 2:
     
     def rc1(n): if ((not isinstance(n, int)) or (n > 100)): return False total = 0 while (n > 0): total = 10*total + n%10 n //= 10 return (total == 42)
   
   
   • RC #2 of 2:
     
     def f(n): if (n == 0): return 1 n = abs(n) count = 0 while (n > 0): count += 1 n //= 10 return count def rc2(m): if (not(isinstance(m, int)) or (m < 0)): return False start = 0 while True: count = 0 for n in range(start, start+3): count += f(n) if (count > 9): break start += 1 return (m == start)


4. digitCount(n)
   Write the function digitCount(n) that takes a possibly-negative int and returns the number of digits in it. So, digitCount(12323) returns 5, digitCount(0) returns 1, and digitCount(-111) returns 3. One way you could do this would be to return len(str(abs(n))), but you cannot do that, since you may not use strings here! This can be solved with logarithms, but seeing as this is "loops week", you should instead simply repeatedly remove the ones digit until you cannot.


5. hasConsecutiveDigits(n)
   Write the function hasConsecutiveDigits(n) that takes a possibly- negative int value n and returns True if that number contains two consecutive digits that are the same, and False otherwise.


6. gcd(m, n)
   [Note: to receive any credit, you must solve this problem using Euclid's algorithm, and by no other means. In particular, do not just loop through all integers less than min(m,n) and find the common factors that way -- it is much too slow!]
   According to Euclid, the greatest common divisor, or gcd, can be found like so:
      gcd(x,y) == gcd(y, x%y)
   We can use that to quickly find gcd's. For example:
       gcd(270,250) == gcd(250, 20) # 270 % 250 == 20
                    == gcd(20, 10) # 250 % 20 == 10
                    == gcd(10, 0) # 20 % 10 == 0
   When we get to gcd(x,0), the answer is x. So gcd(270, 250) is 10. With this in mind, write the function gcd(x,y) that takes two positive integers x and y and returns their gcd using Euclid's gcd algorithm.


7. nthPrime(n) and
   Write the function nthPrime(n) which takes a non-negative int n and returns the nth prime number. We start counting at 0, so nthPrime(0) returns 2, nthPrime(1) returns 3, and so forth. You should use the faster isPrime method from the course notes. Of course, do not just copy-paste that code, but be certain to thoroughly understand it and be able to easily and quickly and correctly reproduce it.


8. nthAdditivePrime(n)
   Write the function nthAdditivePrime(n) that takes a non-negative int n and returns the nth Additive Prime, which is a prime number such that the sum of its digits is also prime. For example, 113 is prime and 1+1+3==5 and 5 is also prime, so 113 is an Additive Prime.


9. nthPerfectNumber(n)
   Write the function nthPerfectNumber(n) that takes a non-negative integer n and returns the nth perfect number, starting at n=0, where a number is perfect if it is the sum of its positive divisors less than itself. For example, 6 is perfect because 6 = 1 + 2 + 3. Also, 28 is perfect because 28 = 1 + 2 + 4 + 7 + 14. The next one is 496, then 8128. For full credit, you need to use a faster version, which uses the same observation that sped up isPrime, so that you only have to search for factors up to the square root of n.


10. Practice!!!
    Do not stop yet! For you to learn this, you must do it yourself! Start from check2.py and write all the functions from scratch, and repeat this until you can do it easily and quickly and correctly. This is absolutely essential for you to learn this material well, and for you to do reliably well on check2 and hw2 and beyond.