6,676 reputation
1836
bio website
location United Kingdom
age 44
visits member for 4 years, 5 months
seen 9 hours ago

13h
comment Is it possible to speed up a hash table by using binary search trees for separate chaining?
Good point - e.g. for a constant-sized hash table with unbounded data, the asymptotic performance of the hash table is the same as the asymptotic performance of the collision handling - the hash table only changes the constant factors.
13h
comment Is it possible to speed up a hash table by using binary search trees for separate chaining?
In asymptotic terms, using a binary tree for collision handling doesn't change expected performance of a hash table provided that the hash table already did the usual tricks to achieve amortized O(1) performance anyway. Resizing the hashtable to ensure good performance means that the expected items per bucket (the size of binary trees) is expected to be small too, so you end up with the same expected amortized O(1) either way. Even for worst case - without any balancing constraint specified, worst case performance for a binary tree is that it ends up behaving like a linked list anyway.
13h
answered Is it possible to speed up a hash table by using binary search trees for separate chaining?
18h
comment Haskell types for functions
My first thought is that this can be solved (but not in Haskell) with an infinite type so that adding/removing layers of application still leaves the same infinite type - kind of the same as saying infinity + 1 = infinity. I think that would mean either a = a -> (a -> (a -> (...))) or a = (((...) -> a) -> a) -> a - not sure which ATM.
1d
revised Finding the first index in which the element and the index are the same
Corrected broken overlapping-range check (I hope)
1d
revised Finding the first index in which the element and the index are the same
added 791 characters in body
1d
answered Finding the first index in which the element and the index are the same
1d
comment Finding the first index in which the element and the index are the same
Note - I haven't got a counterexample and I'm not claiming it's wrong, I'm just curious about the proof.
1d
comment Finding the first index in which the element and the index are the same
The line if i==[i]: isn't looking at the list I at all - [i] is a new list containing that one element. I think you meant if i==I[i]:. BTW - that's an interesting problem - I mistook it for binary search for a bit. I can see that you can recursively eliminate ranges where there's no overlap between the index range and the value range (as indicated by the first/last elements) but I'd like to see the proof that sufficient ranges can be eliminated early to allow an O(log n) solution.
Mar
17
revised What algorithm can be used to determine order given incomplete information?
added 281 characters in body
Mar
17
revised What algorithm can be used to determine order given incomplete information?
Updated with complexity note due to Dovals comment
Mar
17
comment What algorithm can be used to determine order given incomplete information?
@Doval - it could be the "+ Edges" part of that big-O that resolves my confusion. What I said about true/false/don't-know obviously applies to full-order sorting (it's just that the don't-know case never happens) and that obviously has O(n log n) complexity, but n in that case is only the number of vertices. The number of possible edges in a digraph with n vertices (and at most one edge in each direction between any pair of vertices) is n^2, so the number of edges is significant. A full order sort based on an O(n) topological sort would presumably be O(n^2) because all possible edges exist.
Mar
17
answered What algorithm can be used to determine order given incomplete information?
Mar
17
comment What algorithm can be used to determine order given incomplete information?
Another possibility is a "transitive closure". A closure takes some seed set and grows it until all reachable members are included in that set. If you have a < b and b < c in your seed set, by transitivity, you also have a < c, so a transitive closure would add that to the set, and then use that as if it were a seed element as well to try to find more, until no further ordering statements can be proven from those already found.
Mar
17
comment What algorithm can be used to determine order given incomplete information?
You might be looking for "topological sort". Note that depending on which statements you're working from, you may only have a partial order (so there are multiple possible orderings and topological sort just chooses an arbitrary one) or there might be a contradiction (so there's no possible ordering).
Feb
4
awarded  Nice Answer
Dec
2
comment How would one implement communication between an input device and a PC?
Of course I could be making some obsolete assumptions. For example, when you think about it, a USB game controller driver doesn't own a particular USB port. The port its currently dealing with may host multiple devices via a hub. IOW a game controller driver isn't really communicating directly with the hardware - there's other drivers in-between. And I'm sure I've heard about user-mode drivers or something like that.
Dec
2
comment How would one implement communication between an input device and a PC?
That's why Microsoft decided that all drivers should be checked by them (at a price) and should be signed - you still get unsigned drivers on occasion, but the user gets an alert and has to give specific permission to install them. So Microsoft has been systematically testing drivers and charging for that for quite a while. I'm not sure how far they are following the Apple model and checking and controlling Apps in the app store, but drivers were controlled for a long time before, there's good reasons for that, and Microsoft are unlikely to get complacent about them.
Dec
2
comment How would one implement communication between an input device and a PC?
For the windows store issue - I don't know for sure, I've never considered writing software to sell there, but drivers have special privileges and have an ability to crash the whole operating system that other software shouldn't have. If you remember Windows 98, almost all of the crashing issues with that were due to bad drivers - partly because Microsoft didn't control their development (e.g. the DDK back then was IIRC a free or cheap download) and partly because even the DDK examples had errors and there were few tools to catch them.
Dec
2
comment How would one implement communication between an input device and a PC?
I'm not sure why doing "some manner of magic" is a problem. Drivers, background services and applications are all software - they can all do calculations and make decisions. For joysticks, Windows has its own model of game controllers. You can fake that at the driver level certainly, but I can't see why you can't fake it at the Win32 API level by sending fake messages as well. That's not strong evidence that it can be, of course.