15-112
Summer 2021

Home

Syllabus

Schedule

Gallery

Staff

Piazza

Autolab

OH Queue

Forms

CMU 15-112: Fundamentals of Programming and Computer Science
Homework 1 (Due Thurs 7/8 at 5pm ET (Pittsburgh-time))

Important Note: Do not start this homework until you have first carefully read the 112 syllabus and submitted the 112 Student Contract!

  1. getKthDigit(n, k) [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

  2. setKthDigit(n, k, d) [20pts]
    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
    Hint: You probably ought to use your getKthDigit(n, k) as a helper function here.

  3. fabricYards(inches) [20 pts]
    Fabric must be purchased in whole yards, so purchasing just 1 inch of fabric requires purchasing 1 entire yard. With this in mind, write the function fabricYards(inches) that takes the number of inches of fabric desired, and returns the smallest number of whole yards of fabric that must be purchased. Note: 36 inches equals 1 yard.

  4. fabricExcess(inches) [20 pts]
    Write the function fabricExcess(inches) that takes the number of inches of fabric desired and returns the minimum number of inches of excess fabric that must be purchased (as purchases must be in whole yards). Hint: you may want to use fabricYards, which you just wrote!

  5. nearestBusStop(street) [20 pts]
    Write the function nearestBusStop(street) that takes a non-negative int street number, and returns the nearest bus stop to the given street, where buses stop every 8th street, including street 0, and ties go to the lower street, so the nearest bus stop to 12th street is 8th street, and the nearest bus stop to 13 street is 16th street. The function returns an integer, so for example, nearestBusStop(5) returns 8.
Bonus Problems
Bonus problems are entirely optional and worth few points. Do them for the fun and the learning.
Note that the first two are challenging but not unusually difficult (and in many semesters they're just normal hw problems). They're good practice, so we made them worth 2 points. The findIntRootsOfCubic problem is (perhaps) harder, but we'd rather you do the first two first, so it's only worth 1.

  1. bonus: threeLinesArea(m1, b1, m2, b2, m3, b3) [bonus, 2 pts]
    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, use three helper functions: one to find where two lines intersect (which you will call three times), a second to find the distance between two points, and a third to find the area of a triangle given its side lengths. Hint: you may want to briefly read about Heron's Formula.

  2. bonus: colorBlender(rgb1, rgb2, midpoints, n) [bonus, 2 pt]
    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 an 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. (Hint: Any negative n should return None.)

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

    Hints: RGB values must be ints, not floats. Also, remember to use roundHalfUp(n) instead of round(n) when calculating midpoint colors.

  3. bonus: findIntRootsOfCubic(a,b,c,d) [bonus, 1 pt]
    Write the function findIntRootsOfCubic(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.

>>( o u o )<<