* Doug's talk on sorting networks
** SNs fundamental properties
Not general purpose sorting tools
Have the property that a given comparison is not affected by previous comparisons
For sorts that can be expressed this way, sorting networks are faster than standard `sort` function call
** Networks are represented by "Knuth Diagrams"
Dot diagrams indicating comparisons for each member of the collection
** Different types of sorting networks
"The interesting one is Bitonic Sort, check that up"
Bitonic, Merge-Exchange, Bose-Nelson, Bubble
All the examples in this talk are Bubble Sort sorting networks (this is just for ease of explanation)
Best general-purpose sorting network algorithms entail O(n.log^2(n)) operations (there are better special-purpose ones if you're willing to accept constraints/errors)
The point of sorting networks is that arranging sorts in such a way allows for more parallelism in the sort operations
The Knuth notation doesn't express this too well, but the idea is that any operations that don't share a wire can be done in parallel
** 0-1 Principle
Given n elements, there are n! possible orderings
The 0-1 Principle states that any sorting network that is capable of sorting an array containing only the elements 0 and 1 (a bitstring) will also sort arrays of arbitrary elements
** Sort stability
Most useful networks are not stable (it's possible to write transpositions sorting networks that are)
** Alternate notation
- Denote comparison results with a graph
Good networks are good because they put elements in their final positions earlier (with fewer swaps)
Sorting networks with a constant-time compare-swap don't leak side-channel information (useful for sorting secure data)
- The sorting time is completely independant of the input data (which is what you want for cryptographic functions)
Embedded devices (sorting networks are parallelizable operations that DON'T require any stack space)
Secure multi-party communications (as a result of that side-channel security note above)
Still being actively researched (genetic END AI program currently holds records for shortest possible 12 and 16 element sorts)
Sorting algorithms where all operations are planned out ahead of time
Q: Given a sorting network, is there a quick way to test that it's correct?
A: No, I think it's been proven that it's NP complete
Q: This has a really cool graphical representation.
A: That's not a question.
Q: Are there any hardware implementations of sorting networks (coin sorting, not computer hardware)?
A: I hadn't thought about it, but I could see that being done. At first I thought you were talking about computer hardware, and in that case it's definitely "yes".
Q: Where would stable sorts be useful (in general, not in sorting networks)?
A: For serial sorts, mostly (I'm paraphrasing here, like four people answered this).
Q: Have you thought about how to slice up the search space for GPU parallelism?
A: Not specifically, but they are inherently parallelizable, so I can see that being done.
* Leo Demos Raspberry Pi
Much less intense than the preceding
Haskell, Clojure, CLISP installed from the standard ARM Debian repos
** Lighttable on Clojure
Simple smalltalk-esque browser-based programming environment
** UML Variant with diagrammatic business processes YAWL (Yet Another Workflow Language)
Conclusion: most of these workflow languages suck.
The idea is to map out processes where humans and machines are involved, and allow non-programmer humans to manipulate this stuff
Matlab's Simulink in Labview is a similar tool
Excel is apparently used a lot in the wild (especially at trading companies).
- Running remotely over servers (yes, they're basically doing Windows colocation)
** Conversation going to money markets and high-frequency trading implementation
Talking about market slicing and real-time transaction gauging (this is how the world ends, incidentally)
** Talking about the future of mobile computing input
I'm kind of hogging conversation with portable keyboard plans for RasPi
** Cool Web Servers
Antiweb vs Hunchentoot ('toot is a thread-per-connection servers)
THTTPD -- Throttling HTTP Demon (Build-a-Cat from Bloom County; it's a drug addled cat which used that name as a catch phrase)
** Lambda Cube
Variations on the lambda calculus (including various orthogonal typed versions) results in a cuboid Hasse diagram
Each vertex has a language connected with it
Past Meetings >