The Big Programming Thread - Page 846

On February 17 2017 12:11 Blisse wrote:
-12 / 7 = 1 remainder -5

On February 18 2017 11:28 travis wrote:
Is this the proper way to negate this statement?

statement: for all x, there exists y [x < y^2]

negation: for all y, there exists x [ x > y^2]

On February 18 2017 12:13 travis wrote:
edit: ok nevermind after thinking it about it some more I do see the difference. in the 2nd statement it means that it is for all y this thing happens universally, and in the first one that isn't the case

On February 18 2017 12:13 travis wrote:
the order matters?

I thought I remembered the professor saying the order matters for this, but when I conceptualized it I couldn't see the difference between

there exists x, such that for all y

and

for all y, there exists x


edit: ok nevermind after thinking it about it some more I do see the difference. in the 2nd statement it means that it is for all y this thing happens universally, and in the first one that isn't the case

thank you, Blisse

On February 18 2017 10:49 Blitzkrieg0 wrote:
Which node are you actually deleting is probably where you're running into issues.

When you delete the final node in the list your pointer is at position p. p.next is the final node in the list and it's p.next.next value is null. When you set the node at position p's next value to null you're removing the last node in the list as expected and not causing a problem.

HEAD -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] -> null

So if I need to delete 7, I want to traverse the list until p.next == 7. p will be at 6. Then I set p.next equal to p.next.next. The resulting list:

HEAD -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> null

Consider the difference between delete(value) and delete(pointer). In the latter you've already done the search which is causing the discrepancy. The delete(value) function runs in O(n) time because you must traverse the list to find the node. However, the function signature looks like you're telling it to delete a pointer after you've traversed the list making it a O(1) deletion time. There is no search in the pseudo code.

Same example, but with delete(pointer):

function delete(6)
p=position
p.next = p.next.next

p.next.next is null. Set p.next equal to null and node 7 is removed in constant time.

On February 18 2017 14:29 dsyxelic wrote:

If I have 'end' return me a pointer to the actual last node with data in it, I can't delete the last node in constant time.

Is this correct?

On February 18 2017 12:13 travis wrote:
the order matters?

I thought I remembered the professor saying the order matters for this, but when I conceptualized it I couldn't see the difference between

there exists x, such that for all y

and

for all y, there exists x


edit: ok nevermind after thinking it about it some more I do see the difference. in the 2nd statement it means that it is for all y this thing happens universally, and in the first one that isn't the case

thank you, Blisse

On February 18 2017 16:12 Acrofales wrote:
Re Hahn: it's not true that (1) is a weaker or stronger version of (2). They say completely different things about the set. The original statement says there is no minimum element. (1) says there is a minimum element. (2) says nothing about minima, but instead says there is no maximum element. For instance, (1) is true for the set [0, 1,2], but (2) is not (and neither is the original statement).

there exists x, such that for all y

and

for all y, there exists x

Not sure what you mean by that, the 1st statement is stronger than the 2nd. (1) is false but (2) is true.

On February 18 2017 15:20 Yurie wrote:


You could if you used a double linked list instead of a single linked list. That makes each position take up more space though since you have the element, pointer to next AND pointer to previous.

Basically a question of what action you will be performing on the list. If you add and remove at the start you don't even need an end pointer since you never need to find the last element (unless you use a check on it to see if it is the last element before doing first as null). LIFO / Stack is other terms for that type of list.


As for the rest, don't know about python so can't comment on its standard lists.