15-112
Fall 2020

Home

Syllabus

Schedule

Gallery

Staff

Piazza

Autolab

OH Queue

Forms

CMU 15-112: Fundamentals of Programming and Computer Science
Collab 2 (Due Monday 14-Sep at 8pm ET (Pittsburgh-time))


  1. Standard problems Do as many of these as you are able in the allotted time! You may do them out of order, and it is ok if you do not finish them (in fact, you probably won't). Your code must demonstrate effort, however, and your TA should be able to see you have collaborated well.
    Download the starter file here
    (and the linter if you need it)

    1. integral(f, a, b, N)
      Background: in calculus, we use the integral of a function f from x=a to x=b to compute the area under the curve between those points (or the negative area if the function is below the x-axis). One way to approximate this area (that is, to find it without doing any actual calculus!) is by replacing the smooth function with a collection of N trapezoids, as shown in this image:


      As in that image, here we will only use uniform widths, so each of the trapezoids has a width of (b - a)/N, so that all N of them together span the width of (b - a).

      In any case, the larger N is, the more trapezoids you use, the more accurate your approximation becomes. You can read more here about this so-called trapezoidal rule.

      With this in mind, write the function integral(f, a, b, N) that takes a Python function f (that itself takes one value x, a float, and returns a float), and two floats a and b, where a<=b, and a positive int N, and uses the trapezoidal rule with N trapezoids to return the approximate area under the curve of f(x) where a <= x <= b. To be clear, in the case where N=1, this uses just one trapezoid, where the left edge is at (a, f(a)) and the right edge is at (b, f(b)), so the result is (b - a) * (f(a) + f(b))/2 (the width times the average height of the trapezoid).

      Hint: you should use almostEqual if you have your own tests or add any to our test function. Also, you'll probably want to use some very simple curves for testing, as we did in the test function, such as f(x)=x, f(x)=2*x+3, and f(x)=2*x**2, and then in ranges (a,b) with values of N such that you can fairly easily compute the expected answer by hand.

      Another hint: here is a basic example showing how functions work as parameters to other functions: 
      def f1(x): return x+1
def f2(x): return x+2
def h(f): return f(10)
print(h(f1)) # calls f1(10), prints 11
print(h(f2)) # calls f2(10), prints 12

    2. findZeroWithBisection(f, x0, x1, epsilon)
      Write the function findZeroWithBisection(f, x0, x1, epsilon) as described here.

    3. nthCarolPrime(n)
      Write the function nthCarolPrime(n), which takes a non-negative int and returns the nth Carol Prime, which is a prime number of the form ((2**k - 1)**2 - 2) for some value positive int k. For example, if k equals 3, ((2**3 - 1)**2 -2) equals 47, which is prime, and so 47 is a Carol Prime. The first several Carol primes are: 7, 47, 223, 3967, 16127, 1046527, 16769023,... As such, nthCarolPrime(0) returns 7.

      Note: You must use a reasonably efficient approach that quickly works up to n==9, which will return a 12-digit answer! In particular, this means you cannot just edit isPrime. Hint: you may need to generate only Carol numbers, and then test those as you go for primality (and you may need to think about that hint for a while for it to make sense!).

    4. countingPrimes (parts a, b, and c)
      Do parts a, b, and c of the "Counting Primes" problem here.

  2. Discuss solutions to Standard Problems
    Like in collab1, TAs will lead a discussion where you and your teammate(s) will present your work on the standard problems we gave you above. Your TA will be grading you based on demonstrated effort and good collaboration, so participate!


  3. Video Discussion: Deepfakes Watch This 5-minute video
    1. Discuss these questions:
      1. Do you think deepfakes are a serious concern? Do you believe they could weaken Democracy?
      2. CMU teaches the courses in Machine Learning and Graphics technologies that you need to make deepfakes (and, of course, to also do many other things besides that). Is this ok? Does it give us any special obligations to our fellow peers, or to society? If so, what?
    2. You are graded on attentiveness and courtesy. (In other words, pay attention and be respectful.)


  4. Turtle Puzzles
    Each team (you and your partner(s)) must solve one of the two turtle puzzles shown in the youtube videos below, just like in collab1. Your group will choose one puzzle. You "solve" a puzzle by writing a program that produces the same behavior. You will be graded based on effort during the time with your TA, not correctness, and it doesn't matter which puzzle you do. You must write your solutions collaboratively using repl.it, and you must work with your teammate at all times. You may use and modify the demo apps, which contain all the Turtle calls you'll need. Note: There is no autograder for this problem!

    Download the turtle demos here

    We recommend you do this one! Youtube link


    The puzzle below is much harder. Only do this if your whole group wants a big challenge!
    Youtube link


  5. Create a New Turtle Puzzle
    Each team must create a new Turtle Puzzle like you did last week in collab1. Your puzzle must use loops (and it should be hard or impossible to solve your puzzle without loops).
    You will also receive puzzles from the other groups. Your team will be graded on your genuine level of effort to solve the puzzles during the allotted time (which is short). You may be asked to comment on these puzzles later in the meeting.
    After this, if you made a puzzle, you can share it with the rest of the group. If they solve it in the next section (and it isn't trivial) both of you will get some extra credit.


  6. Solve Group Turtle Puzzles
    Attempt to solve some of the puzzles made by the other teams earlier. Your team will be graded on your genuine level of effort to solve the puzzles during the allotted time (which is short). If someone makes a non-trivial puzzle and you solve it before the group moves on to the next section, show your solution to your TA! We'll give you and and the puzzle's creator a bonus point (+5 max). You may be asked to comment on these puzzles later in the meeting.


  7. Do the secret fun thing
    Your TA will tell you what the secret fun thing is when it happens! (Don't worry, you can't lose points here.)


  8. Discuss solutions to Turtle Puzzles
    Like in collab1, TAs will lead a discussion where you and your teammate(s) will present your work on the turtle puzzle we gave you along with any group-made puzzles you tried to solve. Your TA will be grading you based on demonstrated effort and good collaboration, so participate!

Did you finish early?
Take some time to get to know your fellow students!

SUBMIT TO AUTOLAB!
Note the submission deadline at the top of the page. You must submit to autolab by that time. The time is in ET (Pittsburgh time). We strongly recommend you submit immediately after your group is finished! No work will be accepted after the deadline (unless of course your collab meeting is after the deadline).
Submit a zip file to Autolab containing the following items:
  1. Your collab2.py file containing answers to the standard problems.
  2. Your solution to our turtle problem
  3. Your solutions to any group turtle problems (unless no groups gave you turtle problems)

(It is ok if you did not finish some parts, and it is ok if any of these files do not run. You are graded on demonstrated effort. There is no autograder.)

If you realize you messed up your submission (i.e. submitted a blank file, blank zip, etc) you can submit up to 5 times, but you really ought not need to.

Remember, no late work is accepted! Uploading to autolab takes a few minutes at most. Do not wait until the deadline and risk getting a zero.