Past meetings

Past Meetings‎ > ‎

Discussion Meeting (October 2012)

* Doug's talk on sorting networks
   http://hoytech.github.com/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)
** Parallelism
   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
   Hasse Diagrams
   - Denote comparison results with a graph
** Swaps
   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)
** Applications
   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)
** Conclusion
   Sorting algorithms where all operations are planned out ahead of time
** Q&A
   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

* Discussion 
** 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)
   www.acme.com

** 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

Comments