Confusing previous exam answer

Zach S

unread,

Dec 10, 2010, 4:17:22 PM12/10/10

to Cornell CS 2110

In the Sping '07 final exam, in the first question it lists an O(1)
runtime for finding the largest element in a sorted doubly-linked
list. Could this ever be the case if the head didn't have a "previous"
pointer to the tail?

Lonnie Princehouse

unread,

Dec 10, 2010, 4:39:00 PM12/10/10

to cornell...@googlegroups.com

O(1) needs the assumption that you have a pointer to the tail, or that the list is sorted in descending order.

We will do our best to avoid implicit assumptions on the final.

--
You received this message because you are subscribed to the Google Groups "Cornell CS 2110" group.
To post to this group, send email to cornell...@googlegroups.com.
To unsubscribe from this group, send email to cornell-cs211...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/cornell-cs2110?hl=en.

Ken Birman

unread,

Dec 11, 2010, 8:35:33 AM12/11/10

to Cornell CS 2110

Lonnie and I made up the fall 2009 exam. We can vouch for it. If
some other exam has a bug... well, nobody is perfect!

Reply all

Reply to author

Forward