Re: [SigBio] Safety meetings and link to Trac

["rahul mehta" <mehta5@xxxxxxxx>]

Skip lists are special lists and only take O(log n) for insertion and find, because you contain multiple levls of the same value so they are much easier to move through.

http://en.wikipedia.org/wiki/Skip_list

On 2/2/07, Kim Vlcek < kvlcek2@xxxxxxxx> wrote:

oh yea, i think that your bigO times are off. sorted lists are really expensive to maintain. im seeing that first algorithm at like... not linear, even.

On 2/2/07, Kim Vlcek <kvlcek2@xxxxxxxx> wrote:

hey dudes.

http://www.harveycartel.org/metanet/tutorials/tutorialA.html

On 2/1/07, Cyrus Omar < comar2@xxxxxxxx> wrote:

Hey guys, I also posted when the safety meetings are (only 2 more left) which everyone probably needs to go to on the wiki as well.

The URL once again is http://www.acm.uiuc.edu/projects/Cells/wiki/WikiStart.

The tasks everyone has been assigned are up there too.  Kim, if you want to be involved with the collision detection you two can work on it together since its the most complicated part.  I put him on it because we discussed a more efficient way to do after you had left -- basically we impose a maximum width and height to each element and keep a sorted list of the x locations of each edge and the y locations of each edge, and only go left and right in that list far enough that the maximum dimensions aren't violated.  That prevents having to search through all of the cells but is still more efficient in the average case than having to look up the cells at every location within the cell, which would be order O(wh) where w = width, h = height.

If thats a bit too hard to finish in a week we can work on it next week too.

_______________________________________________
SIGBio-l mailing list
SIGBio-l@xxxxxxxxxxxx
https://www-s.acm.uiuc.edu/cgi-bin/mailman/listinfo/sigbio-l

_______________________________________________
SIGBio-l mailing list
SIGBio-l@xxxxxxxxxxxx
https://www-s.acm.uiuc.edu/cgi-bin/mailman/listinfo/sigbio-l

-- 
Rahul Mehta