CS 297: Championship Algorithms

• Leenarat. A lab-on-a-chip (LOC) is a device that can minimize 50-square-meter laboratory, especially chemical laboratory, into a chip. The chips deal with very small fluid volume (pico liters). The chips have very small tube inside to conduct fluid which is controlled the flow by pump, valve, and sensor. There is some chemical substance inside in order to test the sample to show the result color. This can show many experiment results at the same time by split the sample to different tubes. In the future, this can be applied to use in clinics which already have full facilities of medicines but lack of diagnostic tools, which currently use lot of expensive tools and wide area. The technology takes many advantages from its size. It consumes very small volume of sample. As a result, it dramatically improves response time due to short diffusion distances, fast heating, etc. And because every thing is very small, it lowers cost and allows it to do on mass production.
  nanotech.sc.mahidol.ac.th/nano/EnablingNano2.pdf
  http://en.wikipedia.org/wiki/Lab-on-a-chip
• Greg. I reviewed the work done as published in IEEE Trans. Signal Processing55(1), 111-119 (2007) undertaken by Steven G. Johnson and Matteo Frigo. A link to the paper maybe be found at: http://www.fftw.org/newsplit.pdf. Cooley and Tukey were the first to propose a method to computer the FFT in O(nlgn) time. However, in creating the new time standard, they neglected to pay close attention to the operation count involved (because their time speed-up was so awesome, who cares?). In 1968, Yavne created the split-radix algorithm which guaranteed 4nlgn-6n+8 flops and was accepted for a few decades as best minimum operation count method. New work begain really in the 2000s to further reduce the the flop count. Johnson and Frigo attained 34/9 nlgn + other stuff which was on average a 5.6% improvement on Yavre's accepted method of nearly four decades. It is acknowledged by many as the best algorithm from a minimal operation point of view. In practice, there may be other algorithms to try first, since minimum flops is not always going to be the best approach to solving the problem. Also review Van Buskirk for similar on-going work.
• Xiaofan. My example given in the class was about the 'improved' magnetic tape. The recently developed magnetic tape using barium ferrite - a new magnetic medium can store 29.5 billion bits per square inch. And this new tape, whose capacity is around 35 terabytes, can provide more than 40 times storage than the tape currently available. One gigabyte storage with this new tape costs less than one cent, comparing to $3 -$20 per gigabyte for solid state drive. Due to the 'extremely' small density of the data and electromagnetic inference, new signal processing algorithm has been developed by IBM group. See http://www.technologyreview.com/computing/24406/?a=f.
• Ateeq. he extreme example I mentioned in class was regarding data transmission using carrier pigeons. We are all somewhat familiar with IETF's Requests for Comments (RFCs). Some RFCs are standards track, some are informational, and some are down-right hilarious. RFC 1149 is one such example. Written by D. Waitzman for April Fools' Day in 1990 (http://tools.ietf.org/html/rfc1149), the RFC describes a mechanism to transmit "IP datagrams over avian carriers," or IPoAC (hint: datagram, so it's not a reliable protocol).

  Though originally intended as an Aprils Fools' joke, a South African company (The Unlimited) decided to take this a step further in September 2009 and actually implement it in order to demonstrate that this IPoAC transmission protocol was actually faster than their local ISP, Telkom SA. In this case, IPoAC was much faster than the DSL provided by Telkom SA-- by the time the IPoAC transmission was complete, the transmission over DSL was only 4% complete. The The BBC article describing this event can be found here: http://news.bbc.co.uk/2/hi/africa/8248056.stm.

• Sandeep. Tartan Racing team from Carnegie Mellon was the winner of the DARPAâ~@~Ys 2007 Urban Challenge. This car was an example of extreme technology because it had to employ a number of sophisticated algorithms to control the carâ~@~Ys movements at all times. The car had to be programmed to get to find a route to the destination, adjust to obstacles encountered on the road, plan turns and other motions, and maintain a model of the world around it. See http://www.darpa.mil/GrandChallenge/TechPapers/Tartan_Racing.pdf
• Chinfeng. High-Speed Rail - Maglev (magnetic levitation) Theoretical max speed: 4000mph above Max speed record in real world: 581 km/h (Japan, 2005) 3 kinds of system: 1. EMS: Use electromagnetic suspension to construct. Can attain 500 km/h. Both on-board and off-board magnet are electromagnet. Wheelless. 2. EDS: Use high temperature superconductors in its onboard magnets. Off-board magnet is very powerful electromagnet. The technique used here is "electrodynamic suspension" (Meissner Effect). 3. Inductrack System (Permanent Magnet EDS): Still no commercial version. Use permanent magnet instead of electromagnet. References: Wikipedia entry on Maglev (transport). Wikipedia entry on Meissner effect.
• Rizwan. Beretta Less than Lethal: LTL 7000 is a teaser gun. Unlike a standard teaser gun which disarms by fires probes into its target's body to transfer high voltage electric pulses, LTL transfers kinetic energy of its bullet into trauma - a wound which is not lethal but will definitely convince its target to submit to law enforcement officials. A standard teaser gun is effective up to 10 feet but LTL has a range of 50 to 230 feet. What is amazing about this gun is that it transfers a constant kinetic energy, 210 to 230 miles per hour, over a variable range 50 to 230 feet. The energy transferred is just under the lethal limit of greater than 250 miles per hour.  (Source: Discovery channel's Future Weapons, season 3, episode 2; online at http://technorati.com/videos/youtube.com/watch%3Fv%3DrvRvNb-SfbQ)