15-112 Fall 2011 Homework 1
Due Wednesday, 7-Sep, at 10pm

Read these instructions first!

Some possibly very helpful hints:


  1. nthFibonacciNumber
  2. isPerfectIntCube
  3. getInRange
  4. encodeRgba
  5. isGreen
  6. getColorFamily
  7. getSpecialSection
  8. bonus/optional:  bonusGetLetterGrade
  9. bonus/optional:  bonusFindIntRootsOfCubic

  1. nthFibonacciNumber  [16 pts]
    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. isPerfectIntCube [16 pts]
    Write the function isPerfectIntCube(x), which takes an arbitrary value x (which may or may not be an int) and returns True if x is an int value and it is a perfect cube (that is, it is the cube of another int value).  For example, 27 is a perfect cube, because 27 equals 3 cubed.
     
  3. getInRange [16 pts]
    Write the function getInRange which takes 3 values (which you may assume are all numeric) -- x, bound1, and bound2, where bound1 is not necessarily less than bound2. If x is between the two bounds, just return it unmodified.  Otherwise, if x is less than the lower bound, return the lower bound, or if x is greater than the upper bound, return the upper bound.
    For example:
        getInRange(1, 3, 5) returns 3 (the lower bound, since 1 lies to the left of the range [3,5])
        getInRange(4, 3, 5) returns 4 (the original value, since 4 is in the range [3,5])
        getInRange(6, 3, 5) returns 5 (the upper bound, since 6 lies to the right of the range [3,5])
        getInRange(6, 5, 3) also returns 5 (the upper bound, since 6 lies to the right of the range [3,5])
     
  4. encodeRgba [16 pts]
    Background:  computer programs often store colors using their red, green, blue, and alpha (transparency) components.  These are often stored in a single 32-bit integer, where each successive 8-bit portion of the 32-bit number represents each of red (most-significant), green, blue, and alpha (least-significant) in order.  So, for example, consider the rgba value 0x40ff0080 (which is hex for the decimal value 1090453632).  This single number represents a color with some red (0x40, or 64, with a max of 255, so about 1/4th intensity), full-on green (0xff, or 255, which is full intensity), no blue at all (0x00, or 0, so none), and an alpha transparency of 0x80 (or 128, or about half-transparent).

    With this in mind, write the function encodeRgba that takes 4 values representing the red, green, blue, and alpha portions of an rgba value. You may assume those values are int's, but you may not assume they are in the right range. Use the getInRange function you just wrote to adjust each value as needed to be in the range [0,255] (inclusive). Then, use bitwise operators as needed to encode a single 32-bit int value with these 4 8-bit values, with red on the top, then green, then blue, and finally alpha at the bottom. Finally, return that int value.  For example:
        encodeRgba(0x12, 0x34, 0x56, 0x78) returns 0x12345678
        encodeRgba(1234,-1234, 1234,-1234) returns 0xff00ff00
     
  5. isGreen [16 pts]
    Write the function isGreen that takes a single 32-bit rgba value (which you may assume is an int value) and returns True if it represents some pure shade of green, and False otherwise. That is, return True if the green value is positive, both red and blue are zero, and the alpha is positive.
     
  6. getColorFamily [10 pts]
    Write the function getColorFamily that takes a single 32-bit rgba value (which you may assume is an int value) and returns 1 if that value is "mostly red" (that is, if the red value is greater than both the blue value and the green value), 2 if it is "mostly green", 3 if it is "mostly blue", and 4 otherwise (for example, if there is just as much red as green).
     
  7. getSpecialSection [10 pts]
    In a certain fictitious CMU course, each week a section is designated as a "special" section. This is done in a simple rotation, where section "A" gets the first two weeks, "B" gets the next two weeks, and so on, wrapping around as needed.  Sections are lettered "A", "B", "C", etc, and you may assume there are no more than 26 sections.  Sections may contain up to 30 students, and a course always offers the minimum number of sections required.  Write the function getSpecialSection which takes the total number of students in the course (which you may assume is a positive integer) and the week number (which you may also assume is a positive integer), and returns the letter of the specially designated section for that week.  So, for example, getSpecialSection(60, 5) returns "A", because with 60 students there would be 2 sections, and in week #5, we'd wraparound back to section A being special.
    Note: this problem may be more naturally and elegantly solved using conditionals (which are not available this week).
    Hint: 31/30 equals 1, but -31/30 equals -2. Why might this be a hint? Hmmm...
     
  8. bonus/optional:  bonusGetLetterGrade [2 pts]
    Write the function bonusGetLetterGrade which takes a score, which you may assume is a numeric value, and returns the corresponding letter grade, where 90 or higher is an "A", 80-89 is a "B", 70-79 is a "C", 60-69 is a "D", and below 60 is an "F".  Scores should be rounded, so 89.5 rounds to 90 and hence an "A".  Also, there is no upper or lower limit to incoming scores (thus, for example, 101 gets an "A").
    Note: this problem would be more naturally and elegantly solved using conditionals (which are not available this week)
     
  9. bonus/optional:  bonusFindIntRootsOfCubic [4 pts]
    Write the function bonusFindIntRootsOfCubic 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