Thursday, March 11, 2021

Data structure optimized for set intersection? Computer Science

Data structure optimized for set intersection?
How do you know if the sequence chosen for Shell sort is good or bad?
Is designing and implementing a novel video game like Jonathan Blow's Braid considered computer science? If not, maybe it should be?

Data structure optimized for set intersection?

Posted: 10 Mar 2021 08:34 AM PST

The disjoint set/union find data structure is optimized for determining membership and merging sets, enabling both operations in logarithmic time.

Is there a specialized data structure/algorithm whose (only) purpose is to intersect two sets as quickly as possible? I.e. can we iterate over the intersection of A and B in O(|A \isect B|) (amortized) time?

submitted by /u/denniskb
[link] [comments]

How do you know if the sequence chosen for Shell sort is good or bad?

Posted: 10 Mar 2021 08:11 AM PST

Like if you chose a sequence like 5, 3, 1 for an array of 6 numbers, is this a good choice? Bad choice? I'm very new to this so I'm not sure what the defining features are for a "good" sequence and a "bad" sequence

submitted by /u/Missing_Back
[link] [comments]

Is designing and implementing a novel video game like Jonathan Blow's Braid considered computer science? If not, maybe it should be?

Posted: 10 Mar 2021 01:53 PM PST

In the Braid example, aren't the novel time gameplay mechanics advances in game design and worthy of being considered advances in computer science?

submitted by /u/amichail
[link] [comments]