Getting index error in evalPoly

[Afif Khaja]

Hi,

I tried to trace through my code but can't find the source of the problem.

The index error happens in for loop when f = [ai] + f*x

 

# Evaluate Polynomial (Horner's Method)
# f(x) = 2 + 3x + 4x^2  deg = 2     x = 5
def evalPoly(a,deg,x):
    f = 0.0
    for i in reversed(a):
        f = a[i] + f*x
    return a

a = [2,3,4]
print evalPoly(a,2,5)

 

Thanks,

Afif

[Jeremy Kun]

What is the i variable? Start by asking: what is its type?

If you still can't figure it out, try to do the same problem without using reversed.

Jeremy Kun

Mathematics Graduate Student

University of Illinois at Chicago

--
You received this message because you are subscribed to the Google Groups "uic-mcs260-s13" group.
To unsubscribe from this group and stop receiving emails from it, send an email to uic-mcs260-s1...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Afif Khaja]

i is an integer and f is a float, but it's ok to add  and multiply ints and floats, right?

I tried the problem without reverse but it change (as I expected) because the size of the list stays the same either way.

Afif

[Afif Khaja]

Something is not right. When I take out the i and iterate through the list, the code works. To me, it seems like I'm doing the same thing as before.   

 

# Evaluate Polynomial (Horner's Method)
# f(x) = 2 + 3x + 4x^2  deg = 2     x = 5
def evalPoly(a,deg,x):
    f = 0.0

    for element in reversed(a):
        f = element + f*x
    return a

a = [2,3,4]
print evalPoly(a,2,5)

 

# THIS WORKS!!! But WHY?

[Jeremy Kun]

How can you think that's the same thing?! You changed "a[i]" to "i", which means you're not indexing anything anymore. 

Like I said, it seems you don't know how "reversed" works, because "i" is not an integer. I suggest looking up how reversed works, or doing the problem without using reversed.

Here's the same mistake you made on a trivial example. Why should the following program crash?

L = [3.4, 6.7, 9.9]

M = [2.2, 9.9, -5.4]

for i in L:

   print M[i]

Jeremy Kun

Mathematics Graduate Student

University of Illinois at Chicago

[Afif Khaja]

ok. I think I know the problem. I thought I was using the i as an iterator (for i in range(0,deg+1)) but I was actually iterating through the list (for i in reversed(a)) to begin with, so instead of calling a[i], all I had to do was call i.

Thanks,

Afif

[Jeremy Kun]

Yup! reversed returns a generator of entries in the original list.

Jeremy Kun

Mathematics Graduate Student

University of Illinois at Chicago

--

[Afif Khaja]

Can I also ask what's the correct implementation of quicksort in python? This one's giving me "none"

 

# Quicksort
def quicksort(a,n):
    qsort(a,0,n-1)
def qsort(a,l,r):
    if l >= r:
        return
    m=l
    for i in range(l+1,r+1):
        if a[i]<a[l]:
            m+=1
            a[m],a[i]=a[i],a[m]
    a[l],a[m]=a[m],a[l]
    qsort(a,l,m-1)
    qsort(a,m+1,r)
a = [6,8,4,5,8,3]
print a
a = quicksort(a,6)
print a

[Afif Khaja]

My questions stands (even after adding a return statement)

[Jeremy Kun]

These things exist all over the internet in hundreds of languages, for instance http://rosettacode.org/wiki/Quicksort.

Jeremy Kun

Mathematics Graduate Student

University of Illinois at Chicago

[S.F. Kyale]

What best describes the contract for Quicksort is

Quicksort: list, int -> qsort(list, int, int)

What is the contract for qsort?

Is it 

qsort: list, int, int -> list

or is it

qsort: list, int, int -> None

Try this:

a = [6,8,4,5,8,3]

b = a

print a,b

a = quicksort(a,6)

print a,b

[Jeremy Kun]

qsort is not a type, so it can't be part of a contract. 

If your sorting routine creates a new list as output (doesn't sort the list in place), it would be the following for both Quicksort and qsort:

list -> list

There is no need for an integer because in Python we can compute the length of a list just from the list alone (Lowman put the int in there because one can't compute the lengths of lists in C, and again, Lowman writes C code not Python).

If you're sorting the list in place (that is, modifying the input list), then you need to keep track of which sub-section of the list you're working with in a given recursive call. This requires a lower index and an upper index, so the recursive function would have contract

list, int, int -> None 

because again, it just sorts the list in place. The whole routine (the helper function which initializes the variables for the first call to the recursive function) would have contract

list -> None

This whole business about sorting in place versus creating a new list is a question that every sorting algorithm has to answer. For instance, bubble sort sorts in place because it swaps elements one by one. Mergesort on the other hand, does not sort the list in place. It turns out that for quicksort you can do either way. But if you'll notice, the contract should not change even if your algorithm changes! A sorting function will always be list -> list or list -> None, because abstractly that's what a sorting function does: it accepts a list and produces another list (or modifies the input list).

Jeremy Kun

Mathematics Graduate Student

University of Illinois at Chicago

[S.F. Kyale]

It just occurred to me, with large enough integers (or registers) you can easily do a merge sort in place.

Save the lists to be merged as values. Store at one end and restore to the other. Just write indexes two at a time to be sure not to overwrite the merge lists being read from (the last two elements). 

Sent from my iPhone

[S.F. Kyale]

Though, Russel may find fault.