Question

Open question to anyone who has completed problem set 2 or is good at math for CS.

I'm very familiar and comfortable with polynomials, derivatives, and newton's method, and can come up with workarounds to these problems. But, when looking at the actual solutions to these problems I'm not sure I could have ever arrived at them the way Guttag intended. Any general strategies for how people approach the math in these problem sets?

Answer 1

You really have to realize how stupid computers are, and find out exactly what things it can/prefers to deal with, and what it doesn't. For instance, evaluating a polynomial by hand is pretty trivial, but that's because you take a lot of things for granted, you can't help but use shortcuts. Problem is, in programming, a lot of these simple tasks have to be explicited in a good amount of details.

When I tackle a PS, I ask myself some questions: what is my goal, what is my line, loop, function, or program supposed to do? For instance I sometimes write say, 5 lines of code when one would've been enough: the problem is that I sometimes get too caught up in the mechanics of programming and kinda lose sight of what it is I'm trying to achieve. But once in a while I have one of those aha moments, where I go "oh so THAT'S what I was trying to do here!" Clearer thinking = clearer programming. As soon as I get one of my functions working properly, I always take some time to refine it, it helps me get the things I got right *really* right...

You said you can come up with workarounds to these problems, which indicates you're probably doing a few things right, no? Now the only thing you need is some more of those aha moments ;) Also, your question was about how to approach the math in these problems, and I didn't exactly touch on that subject, precisely because I think it doesn't really matter whether the problem is more mathematical in nature or not. Chances are you'll bump into more or less the same kind of issues even on less mathy PSs.

Not sure if that long reply is of any help :) Heck maybe you could post your code, you could get better adjusted feedback from me or someone else more experienced.

Answer 2

Also keep in mind that a lot of times the TAs create the answer key for the assignments. There are many ways to arrive at the same product from programs, so don't doubt your intellectual intuition. Just try to understand the vocabulary and functions within the language and use them engineer your own code.

But yeah, you should post some you've written.

Answer 3

I just finished reading problem set #2. I think I know how to approach it, but I probably won't start until Friday. I think this one will be easier for me than PS #1, finding the payment by bisection was. I'm sure if we all compared our solutions they would all differ from the solution provided on OCW, and they would also differ from each other's solutions. Lots of ways to skin a cat.

Answer 4

For the first question regarding polynomials, my approach was to have a user enter the coefficients and constant using raw_input and then have their input correlate to the tuple "poly." This restricted the format of the polynomial to an ax^2 + bx + c format (standard polynomial), and then I used the function "evaluate_poly(poly, x)" to evaluate the polynomial with any given value for x. The drawback to this was it restricted the polynomial to only one format. I couldn't figure out how to have a user enter an infinity large polynomial, and even after looking at the answer don't really understand how it works or how I would have been able to arrive at that solution with only the instruction given in the lectures. It seems a lot of outside learning is expected, which will probably help me learn the material better but at the same time is frustrating.

Answer 5

I have to preface this by stating that I did not start the problem set yet. I have read it and will start this weekend. From reading the problem statement, I get that you write a function evaluate_poly(poly, x). Then you define a tuple and a variable x, such as in the problem set. poly = (0.0, 0.0, 5.0, 9.3, 7.0) and setting x = -13 Then you call the function with something like print evaluate_poly(poly, x). The tuple and the value for x will then be passed to the function, the polynomial evaluated at x, and the result passed back to the print statement via the return command in your function. Otherwise you could set some variable in your program like y = evaluate_poly(poly, x) and use that number for some calculation. In your program, your function you'll know how many terms and what degree the polynomial is from doing something like n = len(poly). You can test this way of getting the number with a short program:

poly = (1, 3, 5, 9)
n = len(poly)
print n

You should get the answer 4. You can strip the numbers out of the tuple one at a time and use them as multiplier constants times x raised to a power using a loop that will run 4 times in this example. The first time through the loop you'll evaluate 1*x**n where n = 0 the first time through the loop. Then 3*x**n where n = 1 for the second time through the loop. Then 5*x**n where n = 2 for the third time through the loop, etc. I'll get back to you this weekend on how this works out and code details over the weekend while I'm working on it if you wish. Good luck!

Answer 6

Sounds good!

Answer 7

SPOILER ALERT

@JR_Red : First, as has been said, there are always more than one way to get to the solution, but in this case, your code doesn't follow the specifications (takes in a tuple), which is more of an issue :/

The key insight here was that since you're gonna be doing the same thing to more than one elements (namely: multiply a number by x to some power; remember that the constant is simply a number multiplied by x**0), you should use iteration. Iteration is great for "automated" tasks.

At this point, a reasonable question would be: should I use a while or a for loop, and what iterable object should I use? A for loop seems like the natural way to do it because you want your function to take a look at a finite and known set of elements (namely, the tuple you give it as input. So to be more precise: the length and content of the tuple are not known at the time you write the function, but they will be when you actually call the function), and perform the same operations on each element. while and for loops can be interchangeable in some cases, but usually a while loop is more interesting when you don't know a priori how many times you'll have to execute it, for instance when using guess and check algorithms.

As for the iterable object, range len(poly) is one possibility; I used poly itself since tuples are iterable, so you can tell your function to take a look at a tuple's elements in order, and do stuff. In this case, both would allow you to execute the loop the right number of times; personally I find the latter more intuitive, but it's kind of a matter of taste in the end. Notice though that depending on which iterable object you use, the way to implement your loop will be quite different.

So that was for the part where you evaluate each term. If you want to evaluate a polynomial, you then need to add those terms. The easiest way to do this is to add them as you go though the loop, i.e. each time the loop gets executed, you add the term you've just evaluated to some total that *doesn't get reinitialized* each time you go through the loop otherwise you'd simply end up with your last term when your function returns a value.

By the way, you don't *need* outside learning in order to do the problem sets, but it can certainly help!

Answer 8

kizolk, thanks for including your comments. It gives me some things to chew on as I get started that would not have occurred to me without your input. I may just write two functions, each using a different approach, just for the fun of it. I'm spending part of my evening with a print out of "How to Think Like a Computer Scientist" on my lap. You may not "need" outside learning sources, but I think they are worth the time and trouble. After-all, "outside sources" are suggested in the course materials. And we are doing this exercise because we WANT TO, not because we HAVE TO, right?!

Answer 9

Yeah, I sometimes try to write the same function with different approaches, it's always interesting ^^ Also, I haven't read "How to Think Like a Computer Scientist" entirely yet, but it's pretty good I have to say!

Answer 10

I worked on problems #1 last night and #2 this morning. I got two short functions that work. However, when I looked at the solution, I noticed a big difference between the assigned problem set and the solution!

In the problem set handout #2:

problem #1
given-
poly: tuple of numbers, length > 0
x: number
returns: float

problem #2
given-
poly: tuple of numbers, length > 0
returns: tuple of numbers

In the solution to problem set #2

problem #1
given-
poly: list of numbers, length > 0
x: number
returns: float

problem #2
given-
poly: list of numbers, length > 0
returns: list of numbers

This discrepancy makes a fairly big difference in your solution because a list is mutable, and a tuple is NOT. So if you are following directions, you CANNOT use exactly the same approach that they do!