Computer Science 15-112, Fall 2012
Class Notes:  Practice (through week3)


Read these instructions first!

Additional Practice
Here are a bunch of functions you should be able to write now.  These are taken from various recent versions of the 15-112 course notes, so you can Google to find the full descriptions and usually also some test functions.  Any of these may appear (directly or modified) on a quiz or exam!

Graphics Problems
These links contain many pictures we can draw, but they also contain some (perhaps many) we cannot yet draw.  Focus on the pictures that can be drawn with loops and basic shapes (lines, rectangles, ovals, arcs, etc).

  1. Flags of the world
  2. Simple geometric patterns (checkerboards, tessellations, other patterns, ...)

Loop and Conditional Problems
No strings, no imports, no recursion

  1. digitCount(n, digit) # digitCount(123423526, 2) returns 3
  2. mostFrequentDigit(n)
  3. hasConsecutiveDigits(n)
  4. longestDigitRun(n) # longestDigitRun(11777332) returns 3 (because there is a run of 3 consecutive 7's)
  5. longestBitRun(n) # same problem, but in base 2, so longestBitRun(0b1011101101) returns 3
  6. setBitCount(n) # returns number of bits set to 1 in non-negative number n, so setBitCount(0b101101001) returns 5).
  7. goldbachPrime(n) # For even n>0, returns the smallest prime p such that (n-p) is also prime
  8. is/nthRotation(x,y)  # eg, 3412 is a rotation of 1234, and 321 (with an implicit leading 0) is a rotation of 3210
  9. is/nthPalindromicNumber(n)  # 12321 is palindromic
  10. is/nthPerfectNumber(n)  # 28 is perfect because its proper divisors are 1, 2, 4, 7, 14 and 1 + 2 + 4 + 7 + 14 = 28
  11. is/nthPrime(n) # know both the simple and the faster versions of isPrime
  12. is/nthEmirpsPrime(n) # Primes such that the number resulting from reversing their digits is also prime
  13. is/nthAdditivePrime(n) # Primes such that the sum of their digits is also prime
  14. is/nthCarolPrime(n)  # Primes of the form (2n-1)2 - 2 for some integer n
  15. is/nthCircularPrime(n) # Primes such that any cyclic rotation of its digits remains prime
  16. is/nthDihedralPrime(n) # Primes that remain prime when read upside down or mirrored n a seven-segment LED display
  17. is/nthFibonacciPrime(n) # Primes in the Fibonacci sequence
  18. is/nthIsolatedPrime(n) # Primes p such that neither p-2 nor p+2 are prime
  19. is/nthLeftTruncatablePrime(n) # Primes that remain prime when the leading digit is successively removed
  20. is/nthMarkovPrime(n) # Primes p for which there exist integers x and y such that x2 + y2 + p2 =  3xyp
  21. is/nthMersennePrime(n)  # Primes of the form 2n-1 for some integer n
  22. is/nthPalindromicPrime(n)
  23. is/nthSelfPrime(n) # Primes that are self numbers (cannot be generated by adding any number to the sum of its digits)
  24. is/nthWeaklyPrime(n) # Primes where any change of any digit always results in a composite number
  25. is/nthKaprekarNumber(n) # a Kaprekar number is a non-negative integer, the representation of whose square can be split into two parts (where the right part is not zero) that add up to the original number again.  For instance, 45 is a Kaprekar number, because 45**2 = 2025 and 20+25 = 45.
  26. is/nthWithProperty309(n) # We will say that a number n has "Property309" if its 5th power contains every digit (from 0 to 9) at least once.  309 is the smallest number with this property.
  27. is/nthSquareSumOfTwoSquares(n) # takes a non-negative int n and returns the nth number that is itself a perfect square and is also the sum of two other positive perfect squares.  For example, the first such number is 25, because 25=5**2, and 25 = 16 + 9 = 4**2 + 3**2.

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem