wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> online subset sum
        
(Message started by: inexorable on May 13^th, 2011, 1:32pm)

Title: online subset sum
Post by inexorable on May 13^th, 2011, 1:32pm

You have to maintain a set of numbers, starting with an empty set.
A stream of numbers come along with an operation request. The request could be
1)Add(n) - add the number n to the set
2)Remove(n) - remove the number n if already present in set.
3)int FindSum(n) - find the sum of all the numbers in the set that are less than n.

what would be the ideal data structure to support the above operations with optimal time and space complexity?

can we prove lower bound for the data structure that supports above operations?

Title: Re: online subset sum
Post by Grimbal on May 14^th, 2011, 8:35am

A binary search tree with the sub-tree total stored at each node would be perfect for that. If you balance the tree it should take O(log n) average time for all operations.

[oops, silly mistake fixed]

Title: Re: online subset sum
Post by inexorable on May 14^th, 2011, 10:27pm

If it was to be implemented without writing 'redblack' trees or 'avltrees' from scratch for a balanced binary search tree.
would it be possible using c++ stl, boost ?

Title: Re: online subset sum
Post by spicy on May 15^th, 2011, 5:55am

By using hash and array we can do
insert and delete in O(1) and findsum(n) in O(N)

Title: Re: online subset sum
Post by mmgc on May 16^th, 2011, 3:31am

on 05/14/11 at 08:35:06, Grimbal wrote:

A binary search tree with the sub-tree total stored at each node would be perfect for that. If you balance the tree it should take O(n log n) average time for all operations.

How about just maintaining the sum ( of all numbers less than the node ) at each node in BST. time complexity - O(lg n )

Title: Re: online subset sum
Post by towr on May 16^th, 2011, 8:40am

on 05/16/11 at 03:31:16, mmgc wrote:

How about just maintaining the sum ( of all numbers less than the node ) at each node in BST. time complexity - O(lg n )

Then you'd need to update all nodes if you add a number that is less than all numbers already in the set. So updates wouldn't be O(log n) as they are in Grimbal's case.

Title: Re: online subset sum
Post by blackJack on May 17^th, 2011, 3:22am

on 05/14/11 at 08:35:06, Grimbal wrote:

A binary search tree with the sub-tree total stored at each node would be perfect for that. If you balance the tree it should take O(n log n) average time for all operations.

O(n log n) time will be the avg time for one operation? If i am not wrong, for a balanced bst, insert , remove will take O(log n) time and findSum(n) will have to traverse the tree for nodes less than n, so O(n) time. How O(n log n) is arrived?

Title: Re: online subset sum
Post by Grimbal on May 18^th, 2011, 1:39am

Oops, I meant O(log n). My finger sometime type ahead of what I mean.

And I said "on average" because I wasn't sure whether the balancing of the tree can occasionally take more than O(log n), but I guess it shouldn't.

If the sum of a node and all children is stored at each node, you should be able to return the partial sum in O(log n).