CMU 15-112 Spring 2019: Fundamentals of Programming and Computer Science
Homework 1 (Due Sunday 20-Jan, at 5pm)




    Lab collaborative problems [25pts]

    NOTE: These problem descriptions will be released during Friday's scheduled lab session. You will be required to collaborate with your classmates on these problems. You should have enough time to finish the lab problems during the session, but you must complete and submit them as part of your hw1.py file. Lab collaborative problems are worth 25 total points out of 100 possible points for hw1.

    Collaborative problems

    NOTE: These problems are collaborative. That means you can work on them with other students! However, you must follow the collaboration rules as specified by the syllabus, and you must list your collaborators in the special collaboration functions above each solution. These functions (like nearestOddCollaborators() ) should be modified to return a string containing all of your collaborators' andrewIDs separated by commas. Since these are not lab problems, you may work on it solo if you prefer. If you collaborated but did not list your collaborators, you may lose points and this may be considered an academic integrity violation.

    #Here is an example collaboration function. It returns a single string. #This person lists three collaborators! def exampleCollaborators(): return "mdtaylor, krivers, acarnegie"


  1. COLLABORATIVE Code Writing: nearestOdd(n) [10pts]
    Write the function nearestOdd(n) that takes an int or float n, and returns as an int value the nearest odd number to n. In the case of a tie, return the smaller odd value.

    Hint: Remember that the built-in round function has one major flaw: it varies in whether it chooses to round .5 up or down (ugh!). If you need to round anything, you should use the roundHalfUp function from this week's notes instead!

  2. COLLABORATIVE Code Writing: colorBlender(rgb1, rgb2, midpoints, n) [15pts]
    This problem implements a color blender, inspired by this tool. In particular, we will use it with integer RGB values (it also does hex values and RGB% values, but we will not use those modes). Note that RGB values contain 3 integers, each between 0 and 255, representing the amount of red, green, and blue respectively in the given color, where 255 is "entirely on" and 0 is "entirely off".

    For example, consider this case. Here, we are combining crimson (rgb(220, 20, 60)) and mint (rgb(189, 252, 201)), using 3 midpoints, to produce this palette (using our own numbering convention for the colors, starting from 0, as the tool does not number them):

    color0: rgb(220, 20, 60) color1: rgb(212, 78, 95) color2: rgb(205, 136, 131) color3: rgb(197, 194, 166) color4: rgb(189, 252, 201)

    There are 5 colors in the palette because the first color is crimson, the last color is mint, and the middle 3 colors are equally spaced between them.

    So we could ask: if we start with crimson and go to mint, with 3 midpoints, what is color #1? The answer then would be rgb(212, 78, 95).

    One last step: we need to represent these RGB values as a single integer. To do that, we'll use the first 3 digits for red, the next 3 for green, the last 3 for blue, all in base 10 (decimal, as you are accustomed to). Hence, we'll represent crimson as the integer 220020060, and mint as the integer 189252201.

    With all that in mind, write the function colorBlender(rgb1, rgb2, midpoints, n), which takes two integers representing colors encoded as just described, a non-negative integer number of midpoints, and a non-negative integer n, and returns the nth color in the palette that the tool creates between those two colors with that many midpoints. If n is out of range (too small or too large), return None.

    For example, following the case above: colorBlender(220020060, 189252201, 3, 1) returns 212078095

    Hint: RGB values must be ints, not floats. Again, remember that the built-in round function varies in whether it chooses to round .5 up or down! When calculating midpoint colors, you should use the roundHalfUp function from this week's notes instead.


  3. Solo problems

    NOTE: The remainder of the assignment must be completed solo. That means these problems must be completed without collaboration. It is your responsibility to maintain academic integrity as outlined in the syllabus. You may always use piazza, office hours, and other official 15-112 course resources for questions.


  4. Syllabus Review [5pts, hand-graded]
    You should read the entire syllabus so that you're familiar with the class's policies. You are responsible for knowing and adhering to these policies even though we do not have time to discuss them all in class! Read the syllabus carefully, then return the answers to the five questions below inside the triple-string in syllabusAnswer. This question will be hand-graded by TAs.

    1. (Fill in the blank): Extensions on assignments will only be given for university-approved absences, medical emergencies, and _____.
    2. When are you allowed to use a laptop in lecture?
    3. Can you use both grace days on one assignment?
    4. Can you fill out the attendance forms later in the day and still get credit?
    5. If you notice a grading mistake on a quiz or assignment, who do you submit a regrade request to, and how?

  5. Debugging Short Answer [5pts, hand-graded]
    Read over the code shown in the block below. This function should return True if the input x is either an even integer less than or equal to 10 or an odd integer greater than 10. The function should return False otherwise.
    This code has a bug! Please describe the bug, classify it as a syntax, runtime, or logical error, and briefly explain how to fix the bug without changing more than two lines of code. This question will be hand-graded by TAs, and your answer should not be more than three sentences. (It can be shorter!)

    def buggyFunction(x): if not isinstance(x,int): return False if x <= 10: if x % 2 == 0: return True if x > 10: if x % 2 == 1: return True else: return False

  6. Reasoning Over Code [5pts]
    Given the function roc (shown below), find a value that will make roc return True. You should then modify the function rocAnswer() to return that value so that the autograder will accept your work.

    def roc(x): if type(x) != int: return False elif x <= 120: return False elif x % 100 == x - 100: a = x // 10 b = x % 10 if a != 2 * b: return False return True else: return x == 42

    Note: yes, you could try every possible value in this function until you find one that works. That won't help you learn, though. Instead, try working through the problem on paper, to see if you can figure out what a correct answer should look like without going through all the possibilities.

  7. Code Writing: threeLinesArea(m1, b1, m2, b2, m3, b3) and helpers [15pts]
    NOTE: Wait to do this problem until after Friday's lab, where you will collaboratively write distance(x1, y1, x2, y2). You'll need to use this as a helper function to complete this problem.
    Write the function threeLinesArea(m1, b1, m2, b2, m3, b3) that takes six int or float values representing the 3 lines:

    y = m1*x + b1 y = m2*x + b2 y = m3*x + b3

    First find where each pair of lines intersects, then return the area of the triangle formed by connecting these three points of intersection. If no such triangle exists (if any two of the lines are parallel), return 0.

    To do this, you must write two new helper functions in addition to your distance(x1, y1, x2, y2) function:
    • Write lineIntersection(m1, b1, m2, b2) to find where two lines intersect (which you will call three times)
      • This function takes four int or float values representing two lines and returns the x value of the point of intersection of the two lines. If the lines are parallel, or identical, the function should return None.

    • You will need distance(x1, y1, x2, y2) to find the distance between two points (again called three times). You will collaboratively write this function in Friday's lab! Also, make sure you only define the distance function once in your file.

    • Write triangleArea(s1, s2, s3) to find the area of a triangle given its side lengths (which you will call once).
      • This function takes three int or float values representing side lengths of a triangle, and returns the area of that triangle. To do this, you may wish to to use Heron's Formula.

    You may write other helper functions if you think they would be useful, but you must at least write these exactly as described above, and then you must use them appropriately in your solution. Once you have written and tested your helper functions, then move on to writing your threeLinesArea function, which of course should use your helper functions. That's the whole point of helper functions. They help!

    Note that helper functions help in several ways. First, they are logically simpler; they break down your logic into smaller chunks that are easier to reason over. Second, they are independently testable, so you can more easily isolate and fix bugs. And third, they are reusable, so you can use them as helper functions for other functions in the future. All good things!

  8. Code Writing: getKthDigit(n, k) and setKthDigit(n, k, d) [20pts]
    Write the function getKthDigit(n, k) that takes a possibly-negative int n and a non-negative int k, and returns the kth digit of n, starting from 0, counting from the right. So:

    getKthDigit(789, 0) == 9 getKthDigit(789, 1) == 8 getKthDigit(789, 2) == 7 getKthDigit(789, 3) == 0 getKthDigit(-789, 0) == 9

    Then write the function setKthDigit(n, k, d) that takes three integers -- n, k, and d -- where n is a possibly-negative int, k is a non-negative int, and d is a non-negative single digit (between 0 and 9 inclusive). This function returns the number n with the kth digit replaced with d. Counting starts at 0 and goes right-to-left, so the 0th digit is the rightmost digit. For example:

    setKthDigit(468, 0, 1) == 461 setKthDigit(468, 1, 1) == 418 setKthDigit(468, 2, 1) == 168 setKthDigit(468, 3, 1) == 1468

  9. Bonus: bonusFindIntRootsOfCubic(a,b,c,d) [3 pts]
    Note: we usually offer bonus problems for students who want an extra challenge. These problems are optional, and should only be attempted after the rest of the assignment has been finished. Uncomment the last test at the bottom of the file in testAll() to test your solution!

    Write the function bonusFindIntRootsOfCubic(a,b,c,d) that takes the int or 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. 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 (try c.real if c is complex), 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.