15-112 Spring 2015 Homework 2
Due Sunday, 25-Jan, at 10pm

Read these instructions first!

Except for the 1-hour group study session (as noted below), this hw is SOLO.

There is no starter file this week. Instead, you should download hw1.py from hw1, and rename it to hw2.py. Then replace the functions above the #ignore_rest line with your autograded functions (and their helper functions, if any), and replace the test functions below the #ignore_rest line with your new test functions.

Starting this week, you may use loops and conditionals, but (as usual) you may not use constructs we have not yet covered (strings, lists, sets, maps, recursion, etc), unless explicitly allowed below.

Seeing as you do not have a starter file this week, we will allow more Autolab submissions than usual. Even so, to help avoid an overreliance on the autograder, this week you may only make up to 10 submissions max to Autolab. As usual, only your last one counts.

Do not use global variables! Do use test functions!

You can and should use previous functions on the hw to solve later functions.

You also can and should use your own helper functions, where appropriate.

And you also can use anything from the course notes, including isPrime, fasterIsPrime (which you can rename to isPrime), and nthPrime. Just cite it if you use it, and be sure you can also generate the code from first principles!

While optional this week, you are still strongly encouraged to attend small-group CA sessions. These should be a big help for hw2.

A. Manually-Graded Portion [20 pts; 10 pts each]
Submit the solutions to these problems in a triple-quoted string at the top of hw1.py (it is already there for you). Be sure to include these solutions entirely within the triple-quoted string, so Python basically ignores them.

1-hr Group Study Session
Be sure to read this entire writeup before starting! For this exercise, you need to form groups of between 2 and 5 total students, all currently enrolled in 112. You are encouraged to form groups on your own, but we will also help form groups at recitation, and also at our CA office hours on Thursday, Friday, and Saturday. In any case, your group must meet for a 1-hour practice session, where you will work together on problems which we will provide, or others of your choosing. For the session to count, these rules must all be followed precisely:
- The group must give itself a name. Everyone must use the same name when referring to the group.
- Everyone in the group must participate for a full hour. If someone arrives late, you'll have to run one hour from that time (or have them join a different group).
- Upon completing the hour, everyone in the group must separately fill out this form where they will list this information: group name, group meeting date, group meeting time, group meeting location, andrew id's of everyone in the group.
Once again: you only get credit for attending if you are on time and stay the whole time. You have nothing to submit for this except to fill out the form. We 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 your peers, and to let you see another helpful resource available to you in your career here at CMU.

f14 Quiz 2
In the triple-quoted string at the top of your hw1.py file, include the solutions to f14's quiz2 (except for the bonus, which you should skip (or do for fun if you wish)). Remember that this is SOLO!

B. Autograded Portion: Problem-Solving (Writing functions) [80 pts]

findZeroWithBisection [10 pts]
Read the writeup for findZeroWithBisection here.

nthEmirp(n) [10 pts]
Write the function nthEmirp(n), where an emirp is a prime number that becomes a different prime number when its digits are reversed. See here for details. So nthEmirp(0) returns 13, and nthEmirp(10) returns 149.

carrylessAdd(x,y) [10 pts]
First, read the first page (page 44) from here about Carryless Arithmetic. Fun! Then, write the function carrylessAdd(x, y) that takes two non-negative integers x and y and returns their carryless sum. As the paper demonstrates, carrylessAdd(785, 376) returns 51.

"The 112 Game" (play112) [50 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!

Bonus/Optional: carrylessMultiply(x,y) (2 pts)
Similarly to carrylessAdd, write carrylessMultiply(x,y). The same paper shows that carrylessMultiply(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.

Bonus/Optional: Fun with generators! (3 pts; 1 pt each)
Note: if you attempt the optional bonus problems, please be sure to place your solutions above the #ignore_rest line, so the autograder can see them and test them.

First, do your own Google search to read about the "yield" statement and so-called "generators" in Python. Then, carefully look at this code, play around with it, and understand it:

def oddsGenerator():
    odd = 1
    while True:
        yield odd
        odd += 2

def oddsGeneratorDemo():
    print "Demonstrating use of oddsGenerator()..."
    print "   looping over oddGenerator():",
    for odd in oddsGenerator():
        # This is how generators are typically used
        print odd,
        if (odd > 20): break
    print "Done!"
    print "   This time, using the next() function:",
    g = oddsGenerator()
    for i in xrange(11):
        # Explicitly calling the next() function is a less common
        # way to use a generator, but it still works, of course..
        print g.next(),
    print "Done!"

oddsGeneratorDemo()

Bonus/Optional: squaresGenerator()
Write the function squaresGenerator(), so that it passes the following tests. Your function must not use globals or other explicit non-locals (don't worry if you don't know what those are), and it must use "yield" properly.

def testSquaresGenerator():
    print "Testing squaresGenerator()...",
    # This time, we'll test twice.  First with next(),
    # then with a "for" loop
    g = squaresGenerator()
    assert(g.next() == 1)
    assert(g.next() == 4)
    assert(g.next() == 9)
    assert(g.next() == 16)

    # ok, now with a for loop.
    squares = ""
    for square in squaresGenerator():
        # we'll check the concatenation of the str's,
        # since we cannot use lists on this hw!
        if (squares != ""): squares += ", "
        squares += str(square)
        if (square >= 100): break
    assert(squares == "1, 4, 9, 16, 25, 36, 49, 64, 81, 100"
          )
    print "Passed!"

Bonus/Optional: nswGenerator()
First, read about Newman-Shanks-Williams primes here. (Hint: the recurrence relation is probably the most important part for this task.) We will build a generator for these! Before generating the NSW (Newman-Shanks-Williams) primes, we'll just generate all the values, prime or not, in the NSW series as described in that link. As noted, these values are also listed here.

With this in mind, write the function nswGenerator(), so that it passes the following tests. Again, your function must not use globals or other explicit non-locals (don't worry if you don't know what those are), and it must use "yield" properly.

def testNswGenerator():
    print "Testing nswGenerator()...",
    nswNumbers = ""
    for nswNumber in nswGenerator():
        # we'll check the concatenation of the str's,
        # since we cannot use lists on this hw!
        if (nswNumbers != ""): nswNumbers += ", "
        nswNumbers += str(nswNumber)
        if (nswNumber >= 152139002499): break
    # from: http://oeis.org/A001333
    assert(nswNumbers == "1, 1, 3, 7, 17, 41, 99, 239, 577, 1393, 3363, 8119, "
                         "19601, 47321, 114243, 275807, 665857, 1607521, 3880899, "
                         "9369319, 22619537, 54608393, 131836323, 318281039, "
                         "768398401, 1855077841, 4478554083, 10812186007, "
                         "26102926097, 63018038201, 152139002499"
          )
    print "Passed!"

Bonus/Optional: nswPrimesGenerator()
Now we put it all together and make an nsw primes generator. Practically, we will be limited by the inefficiency of our isPrime (well, fasterIsPrime) function. So we will only test this function out to 63018038201, and not 489133282872437279 or beyond. Even so, be sure not to hardcode the answers, but instead solve this generally.

With this in mind, write the function nswPrimesGenerator(), so that it passes the following tests. Again, your function must not use globals or other explicit non-locals (don't worry if you don't know what those are), and it must use "yield" properly.
```
def testNswPrimesGenerator():
    print "Testing nswPrimesGenerator()...",
    nswPrimes = ""
    for nswPrime in nswPrimesGenerator():
        # again, we'll check the concatenation of the str's,
        # since we cannot use lists on this hw!
        if (nswPrimes != ""): nswPrimes += ", "
        nswPrimes += str(nswPrime)
        if (nswPrime >= 63018038201): break
    # from: http://oeis.org/A088165
    # print nswPrimes
    assert(nswPrimes == "7, 41, 239, 9369319, 63018038201"
                        #"489133282872437279"
          )
    print "Passed!"
```

15-112 Spring 2015 Homework 2 Due Sunday, 25-Jan, at 10pm

15-112 Spring 2015 Homework 2
Due Sunday, 25-Jan, at 10pm