CMU 15-112: Fundamentals of Programming and Computer Science
Homework 2 (Due Saturday 7-Sep at 8pm)

• This homework is solo. You must not collaborate with anyone (besides current course TA's and faculty) in any way. See the syllabus for more details.
• The exercises included here are worth 75% of your homework score. The other 25% come from this week's writing session.


• Helpful forms
  Note: you must be authenticated to andrew.cmu.edu for these to work:
  • Hw1 Extension Request Form
  • Note: this week all Hw2 Booster Sessions are walk-in only!


• To start:
  1. Create a folder named 'week2'
  2. Download both hw2.py and cs112_f19_week2_linter.py to that folder
  3. Edit hw2.py
  4. When you have completed and fully tested hw2, submit hw2.py to Autolab. For this hw, you may submit up to 10 times (which still is way more than you should require), but only your last submission counts.
• Do not use string indexing, lists, list indexing, or recursion this week.
• Do not hardcode the test cases in your solutions.

---

1. Attend TA-led small-group OR large-group sessions [10 pts]
   Every week, everyone is strongly encouraged to attend TA-led sessions. This week in particular, though, this is required, so that everyone knows what those sessions are and can better judge if they will be useful to them in the future. So this week, everyone must attend one of these:
   • Attend one TA-led small-group session
     Thee are led by your recitation TA's. They will be in touch with details to set these up.
   
   OR
   
   
   • Attend one TA-led large-group session
     These are as noted in the course syllabus. You have many to choose from, including the content review session, hw booster sessions, hw solution sessions, and quiz prep sessions. Note that the optional advanced lectures are not TA-led this week, and so do not count as part of this hw.


2. integral(f, a, b, N) [5 pts]
   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 (from here, with N=5):
   
   
   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
   



3. nthSmithNumber(n) [10 pts]
   Write the function nthSmithNumber that takes a non-negative int n and returns the nth Smith number, where a Smith number is a composite (non-prime) the sum of whose digits are the sum of the digits of its prime factors (excluding 1). Note that if a prime number divides the Smith number multiple times, its digit sum is counted that many times. For example, 4 equals 2**2, so the prime factor 2 is counted twice, thus making 4 a Smith Number.


4. drawPattern1(points, canvas, width, height) [5 pts]
   Note: each of the next several exercises draws a graphics pattern using only lines. Some notes about each of these exercises:
   • The first parameter, points, varies in meaning, but in each case, your pattern must take it into account.
   • The pattern should fill the canvas (so it must be based on the width and height parameters).
   • The writeup includes a function to run the drawing. For example, for drawPattern1, the writeup includes runDrawPattern1(points, width, height) that creates a canvas, calls drawPattern1(points, canvas, width, height), and then displays the result.
   • These graphics exercises are not autograded. The TA's will manually grade these.
   • There are many reasonable ways to solve these exercises!
   
   With that in mind, write the graphics function drawPattern1(points, canvas, width, height), that draws this pattern using only lines:

   	runDrawPattern1(4, 200, 200)		runDrawPattern1(5, 200, 200)		runDrawPattern1(10, 400, 200)

   
   Note:
   • points is the number of points along each side.


5. drawPattern2(points, canvas, width, height) [10 pts]
   Write the graphics function drawPattern2(points, canvas, width, height), that draws this pattern using only lines:

   	runDrawPattern2(4, 200, 200)		runDrawPattern2(5, 200, 200)		runDrawPattern2(10, 400, 200)

   
   Notes:
   • points is the number of points along each axis in one quadrant (including the center and the endpoint).
   • Hint: Think of this as an x and y axis. Now, look only at the first (top-right) quadrant. See that as we move down the y axis, we move right across the x axis. We draw a line from each point on the y axis to the corresponding point on the x axis as we go. In this way, the lines start mostly vertical and end mostly horizontal. Think about it! Then do the same basic idea for the other 3 quadrants.


6. drawPattern3(points, canvas, width, height) [10 pts]
   Write the graphics function drawPattern3(points, canvas, width, height), that draws this pattern using only lines:

   	runDrawPattern3(4, 200, 200)		runDrawPattern3(5, 200, 200)		runDrawPattern3(10, 400, 200)

   
   Note:
   • points is the number of points along each side (like the first drawing above).


7. drawPattern4(canvas, width, height) [10 pts]
   Draw a clever, attractive, original line pattern of your own design, so that:
   • It fills the canvas for any width and height.
   • It is visually appealing. (We will take a broad view of this when grading.)
   • It uses loops and conditionals in an interesting way. (Ditto.)
   Be thoughtful but don't overthink this. The point is to have some creative fun showcasing your knowledge of loops, conditionals, and drawing lines, so as long as you do that, you are fine. Also, we may apply some modest bonus points to the top few submissions, as selected by our always-thoughtful TA graders.


8. playPig() [15 pts]
   First, read about the dice game Pig here. Then, write the function playPig(), that allows two players to play the game Pig. You will want to use random.randint(1,6) to randomly choose a number between 1 and 6 inclusive. Grading criteria:
   • Your game must enforce the basic rules of Pig.
   • Your game should not use any graphics. This is a console-based game.
   • Your game should use the input(prompt) function to get user input.
   • Your game should print enough information to make the game reasonably fun and usable.
   As with the previous creative problem, be thoughtful but don't overthink this. Any reasonably fun, playable game of Pig will do fine here. Have fun!


9. Bonus/Optional: bonusPlay112 (The 112 Game) [2.5 pts]
   Read the writeup for "The 112 Game" here (skip to Part B). Be sure to follow the spec exactly, so the autograder can properly grade your work! As with all bonus, we recommend that you only do this for the joy of learning (which is great), and not for the points (which are modest).


10. Bonus/Optional: bonusCarrylessMultiply(x, y) [2.5 pts]
    Write the function bonusCarrylessMultiply(x, y), that works similarly to carrylessAdd(x, y) (which we will cover in the writing session), based on this paper on Carryless Arithmetic. This paper shows that bonusCarrylessMultiply(643, 59) returns 417. Hint: it may help if you do this differently than usual long multiplication. Instead of working by rows in the output, work by columns. So first compute all the ones digit values, and sum those mod 10. Then compute all the tens digit values, and sum those mod 10. And so on. You may assume x and y are non-negative.
    
    Hint #1: do not solve carrylessMultiply(x, y) by simply calling carrylessAdd(x, result) a total of y times. That is wrong on two levels. First, it is simply too inefficient (what if we are multiplying 20-digit numbers?). Second, it is also wrong algorithmically! CarrylessMultiply is not like normal multiply, and if we take + to be carrylessAdd and * to be carrylessMultiply, then it is not necessarily true that (x * y) is the same as (x + x + ... + x + x) for a total of y x's. Yikes. So: stick with the next hint (see below). It also uses carrylessAdd and is fairly straightforward, but it is reasonable efficient and algorithmically correct. Good luck with it.
    
    Hint #2: Here's a hint on one way to solve this problem (there are many ways, and this way is not the most efficient, to be sure, but it is efficient enough and it is perhaps among the clearest and easiest ways).
    
    Consider multiplying 123 * 456. Observe that:
    
        123 * 456 = 123 * 4 * 100 + 123 * 5 * 10 + 123 * 6
    
    in this way, we actually only have to multiply 123 times a single digit each time, then multiply that result by the right power of 10. Right?
    
    Ok, so now, to multiply by a single digit, we can instead just add that many times. That is:
    
        123 * 6 == 123 + 123 + 123 + 123 + 123 + 123
    
    Why is that interesting? Because we already have carrylessAdd, so we can just use that to do all this addition.
    
    Of course, multiplying by simply adding is very inefficient. But since we are only doing it for multiplying by a single digit, there's a max of 9 additions (8 if you think about it), and so it's not so inefficient. It's actually acceptable, if not ideal, and certainly good enough for hw2, though again better approaches do exist.
    
    Hope this helps. And, again, you can safely ignore all of this and solve this problem any way you wish.