Computer Science 15-112, Spring 2013
Class Notes:  Practice (through week1)

Read these instructions first!
  1. Mystery Functions
    In just a few words of plain English, what does each of the following functions do?  Provide some explanation for your answer.
    1. def f(x,y):
          epsilon = 0.0000001
          d1 = abs(x)**2
          d2 = abs(y)**0.5
          return abs(d1 - d2) < epsilon
       
    2. def g(x):
          return (type(x) == int) and (x/10 == x%10)
       
    3. def h(x):
          return (type(x) == int) and (x >= 0) and ((int(round(x**0.5)))**2 == x)
       
  2. Review examples from class notes
    1. onesDigit
    2. tensDigit
    3. eggCartons
    4. militaryTimeToStandardTime
       
  3. Write functions
    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!

    Data and Expressions Problems
    No loops, no conditionals, no strings, no imports, no recursion
     
    1. nthFibonacciNumber(n)
      Write the function nthFibonacciNumber that takes a positive integer n and (without using loops) returns the nth Fibonacci number, so:
         nthFibonacciNumber(1) returns 1
         nthFibonacciNumber(2) returns 1
         nthFibonacciNumber(3) returns 2
         nthFibonacciNumber(4) returns 3
         nthFibonacciNumber(5) returns 5
         nthFibonacciNumber(6) returns 8
      Hint: look at formula (8) here, where phi (in the numerator) is the Golden Ratio. Cool!
       
    2. integerSquareRoot(x)
      Given a non-negative int x, return the integer value that is closest to its square root.  For example, integerSquareRoot(10) returns 3.
       
    3. celsiusToFahrenheit(degrees)
      Given a temperature in Celsius, return the same temperature in Fahrenheit.  So celsiusToFahrenheit(0) returns 32, and celsiusToFahrenheit(100) returns 212.
       
    4. isRightTriangle(x1, y1, x2, y2, x3, y3)
      Given six numeric values representing the points (x1, y1), (x2, y2), and (x3, y3), return True if the triangle formed by connecting the 3 points is a right triangle, and False otherwise.  You may ignore the case where the 3 points are collinear (and so do not form a triangle).  Hint:  Herod's Formula.
       
    5. triangleArea(x1, y1, x2, y2, x3, y3)
      Given six numeric values representing the points (x1, y1), (x2, y2), and (x3, y3), return the area of the triangle formed by connecting the 3 points.  You may ignore the case where the 3 points are collinear (and so do not form a triangle).  Hint:  Herod's Formula.
       
    6. pghHour(londonHour)
      This function takes an integer, the current hour in London, and returns the current hour in Pittsburgh (which is 5 hours behind London). However, London time is given in 24-hour time (so londonHour is between 0 and 23, inclusive), but Pittsburgh time must be returned in 12-hour time (so the result must be between 1 and 12, inclusive, where "am" and "pm" are ignored). Here are some examples:
      londonHour pghHour(londonHour)
      0 (midnight) 7 (7pm)
      10 (10am) 5 (5am)
      12 (noon) 7 (7am)
      17 (5pm) 12 (noon)
      18 (6pm) 1 (1pm)

      Note: the hardest part is when it is 12 o'clock in Pittsburgh.
       

    7. dayOfWeek
      Write a function that takes a date represented by three integers, the month (1-12), the day (1-31), and the year, and returns an integer representing the day-of-week for that date, where Sunday is 1, Monday is 2, and so on, and Saturday is 7.

      While there are several ways to do this, you must use this formula (from the most-excellent web site mathforum.org):
            N = d + 2m + [3(m+1)/5] + y + [y/4] - [y/100] + [y/400] + 2
      Then the remainder when you divide N by 7 is the day-of-week, where Saturday is 0 and Friday is 6.  Note that these values for the days are not quite the same as those returned by this method.

      Here is mathforum's description of the formula:  "d is the number or the day of the month, m is the number of the month, and y is the year. The brackets around the divisions mean to drop the remainder and just use the integer part that you get.  Also, a VERY IMPORTANT RULE is the number to use for the months for January and February. The numbers of these months are 13 and 14 of the PREVIOUS YEAR. This means that to find the day of the week of New Year's Day [of 1998], 1/1/98, you must use the date 13/1/97."

      Note: you must make the adjustment to the month and year when appropriate.  So, for example, the date of New Year's Day for 1998 would be obtained in the natural way:  dayOfWeek(1, 1, 1998).  You may ignore the cases where the month, day, or year are out of bounds.

      def testDayOfWeek():
          print "Testing dayOfWeek... ",
          # On 2/5/2006, the Steelers won Super Bowl XL on a Sunday!
          assert(dayOfWeek(2, 5, 2006) == 1)
          # On 6/15/1215, the Magna Carta was signed on a Monday!
          assert(dayOfWeek(6, 15, 1215) == 2)
          # On 3/11/1952, the author Douglas Adams was born on a Tuesday!
          assert(dayOfWeek(3, 11, 1952) == 3)
          # on 4/12/1961, Yuri Gagarin became the first man in space, on a Wednesday!
          assert(dayOfWeek(4, 12, 1961) == 4)
          # On 7/4/1776, the Declaration of Independence was signed on a Thursday!
          assert(dayOfWeek(7, 4, 1776) == 5)
          # on 1/2/1920, Isaac Asimov was born on a Friday!
          assert(dayOfWeek(1, 2, 1920) == 6)
          # on 10/11/1975, Saturday Night Live debuted on a Saturday (of course)!
          assert(dayOfWeek(10, 11, 1975) == 7)
          print "Passed all tests!"
       
    8. challenge: findIntRootsOfCubic(a, b, c, d)
      Write the function findIntRootsOfCubic that takes the real (float) coefficients a, b, c, d of a cubic equation of this form:
           y = ax3 + bx2 + cx + d
      You are guaranteed the function has 3 real roots, and in fact that the roots are all integers.  Your function should return these 3 roots in increasing order.  How does a function return multiple values?  Like so:
          return root1, root2, root3
      To get started, you'll want to read about Cardano's cubic formula here (great stuff!).  Then, from that page, use this formula:
       
      x   =   {q + [q2 + (r-p2)3]1/2}1/3   +   {q - [q2 + (r-p2)3]1/2}1/3   +   p

      where:

      p = -b/(3a),   q = p3 + (bc-3ad)/(6a2),   r = c/(3a)

      This isn't quite as simple as it seems, because your solution for x will not only be approximate (and not exactly an int, so you'll have to do something about that), but it may not even be real!  Though the solution is real, the intermediate steps may include some complex values, and in these cases the solution will include a (possibly-negligibly-small) imaginary value.  So you'll have to convert from complex to real (see hint above), and then convert from real to int.

      Great, now you have one root.  What about the others?  Well, we can divide the one root out and that will leave us with a quadratic equation, which of course is easily solved.  A brief, clear explanation of this step is provided here.  Don't forget to convert these to int values, too!

      So now you have all three int roots.  Great job!  All that's left is to sort them.  Now, if this were later in the course, you could put them in a list and call a built-in function that will sort for you.  But it's not, so you can't.  Instead, figure out how to sort these values using the limited built-in functions and arithmetic available this week.  Then just return these 3 values and you're done.

      Good luck!!!

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