15-112 Spring 2016 Homework 1
Due Sunday, 17-Jan, at 10pm

Read these instructions first!

Except for the 1-hour meeting with your CA, this hw is SOLO. See the syllabus for details.

Start by downloading this file: hw1.py. Edit that file and submit that edited file to Autolab.

For all programs: You may not use loops (which we've not covered yet). You also may not use strings, or recursion, or imports besides math, or anything else we've not yet covered, as the object of this week is to reinforce your understanding of basic operators and expressions.

Hint: in some cases, you may want to make use of some math functions, say perhaps math.floor or math.ceil.

Also, while you may not use the internet (or anywhere else) to find code or to get code questions answered, you most certainly may use the web to find math formulas or things of that nature.

A. 1-Hour CA-Led Practice Session [20 pts]
For this exercise, you need to attend a 1-hour week1 practice session with one of your CA's from your assigned recitation. Your CA's will contact you via email with numerous different times when they will offer these 1-hour sessions. You need to attend one of these by Saturday night. The sooner, the better, as this will be a great help for you prior to starting hw1. Note: you only get credit for attending if you are on time and stay the whole time. You have nothing to submit for this -- the CA's will take attendance and will enter this directly into Autolab, so you then receive the points for attending. Never mind the points, though: this is an invaluable time to practice with an expert, and to let you see just how wonderfully helpful it is to work with our CA's!

B. Autograded Portion: Problem-Solving (Writing functions)
Be sure you started by downloading the hw1.py file we provided! Absolutely do not retype that file, but edit it directly! Edit it using a Python editor, like IDLE or Sublime. Do not, do not, do not use a non-Python editor! Submit the edited hw1.py file via Autolab (you will practice this in recitation this week) Remember: No loops, no strings, no imports (except math), no recursion.

Big hint: the file hw1.py contains test functions for each of these functions. Before you try to solve a problem, be sure to carefully look over its test function. That can be a huge help for you to understand exactly what the problem is looking for.

As you adjust to the autograder, this week (and only this week) you may have up to 20 submissions, which is way more than will be available starting next week. Even with so many submissions, you should try to conserve your submissions and learn how to debug your code so you have high confidence that your submissions are in fact correct. However, your grade is determined only by your last submission.

  1. nearestBusStop(street) [10 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.

  2. setKthDigit(n, k, d) [10 pts]
    Write the function setKthDigit(n, k, d) that takes three non-negative integers -- n, k, and d -- where d is a single digit (between 0 and 9 inclusive), and returns the number n but 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) returns 461
    setKthDigit(468, 1, 1) returns 418
    setKthDigit(468, 2, 1) returns 168
    setKthDigit(468, 3, 1) returns 1468

  3. cosineZerosCount(r) [10 pts]
    Write the function cosineZerosCount(r) that takes a possibly-negative float r, and returns the integer number of zeros (x-axis crossings) of cosine(x) where 0 <= x <= r, and the units are radians. For example, cosineZerosCount(math.pi*2/3) would return 1, since the only zero between x=0 and x=math.pi*2/3 is at x=math.pi/2. The test function has some other test cases for you to consider.

  4. riverCruiseUpstreamTime(totalTime, totalDistance, riverCurrent) [10 pts]
    First, read the "River Cruise" example problem on this page. Then, write the function riverCruiseUpstreamTime(totalTime, totalDistance, riverCurrent) which takes three positive int or float values, the total time in hours of the roundtrip (up and back downstream), the total distance in km of the roundtrip, and the speed in km/hour of the river current. The function returns a float value of the time required to complete the upstream portion of the trip.

  5. rectanglesOverlap(left1, top1, width1, height1, left2, top2, width2, height2) [10 pts]
    A rectangle can be described by its left, top, width, and height. This function takes two rectangles described this way, and returns True if the rectangles overlap at all (even if just at a point), and False otherwise. Note: here we will represent coordinates the way they are usually represented in computer graphics, where (0,0) is at the left-top corner of the screen, and while the x-coordinate goes up while you head right, the y-coordinate goes up while you head down. Yes, up is down! This is quite common in computer graphics, and is how Tkinter and Brython in particular both work. Check out the examples in the test code we provided to see this in action. Up is down. Weird, but true.

  6. threeLinesArea(m1, b1, m2, b2, m3, b3) [30 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, you must write 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 (perhaps already covered in the notes or in class), and a third to find the area of a triangle given its side lengths (which you will call once). You may write other helper functions if you think they would be useful, but you must at least write these three exactly as described below, and then you must use them appropriately in your solution.

    The first required helper function is:
       lineIntersection(m1, b1, m2, b2)
    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.

    The second required helper function is:
       distance(x1, y1, x2, y2)
    This function takes four int or float values representing two points and returns the distance between those points.

    The third required helper function is:
       triangleArea(s1, s2, s3)
    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.

    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 helpe functions. They help! They 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!

  7. Bonus/optional: findIntRootsOfCubic(a,b,c,d) [3 pts]
    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 (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


    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.