# FacultyAlgorithmChallenge ## Guidelines for Evaluation This document can also be accessed through ### Faculty ELi5 Algorithm Teaching (FEAT) challenge `#FEAT` #### UPDATE 2 The key thing is `ELi5` -> "Explain Like I am 5" applies to the part of explaining the algorithm. Of course, for the real world use case, they might want to target a more mature audience. The faculty presentation will be scored on * the power and elegance of algorithm * the interestingness and entertainment value of the real world application * the style and content of the presenter and his presentation **OBJECTIVE**: To tell the world why you as a CSE faculty care about algorithms, which is the bedrock of Computer Science. Secondly, your presentation must motivate and inspire your peers and students to adopt an algorithm of their choice and be inspired to make a presentation which is as fascinating as yours. **IMPORTANT**: Bonus points for adopting PechaKucha format, and sticking to 400 seconds (20 by 20). No more than 10 minutes, whatsoever. > 1. Personality of the presentation - there is no right or wrong in your choice of algorithm. All that matters, why are *you* passionate about the algorithm and what about it is so fascinating from your perspective? > 2. Choose at least one real-world application that the algorithm finds use for. Don't choose more than two. Describe the real-world application. > 3. Show the code for the algorithm either in pseudo code or your favourite language > 4. Choose whatever format makes sense to you to present all the above three. Bring your creativity to the fore. ## Inspiration for Algorithmic Challenge How do I go about finding algorithms to get inspired by? Visit any of the following links. ### Algorithms at work * ### Dictionary of Algorithms and DS (DaDS) ### Quora Based * * * -must-implement-at-least-once-in-life * plementation-to-date ### Misc * * by various application domains * * * - what you need to know to get employed at leading tech companies ### Stackoverflow TCS (Theoretical Computer Science) * * [Euclid's Algorithm](https://cstheory.stackexchange.com/questions/189/algorithms-from-the-book) features in this list * And also on this list - * From [Software Engineering SO](https://softwareengineering.stackexchange.com/questions/20128/which-are-the-significant-algorithms-for-humankind-in-past-decades) ### Personality based * 50 ways MIT has transformed computing - * - what Knuth thinks of algorithms (search for "algorithm" across the article) - - Hackers on Knuth's books * - It's not an algorithm, but a data structure. I've always marveled at the simple tree-based data structure for disjoint-set union, using union by rank and path compression (Section 21.3 in the third edition of CLRS). The code is amazingly simple, the data structure operations take just barely superlinear time, and the analysis (by Bob Tarjan) blows my mind. * [Slack's Keith Adams, Chief Architect](https://www.quora.com/What-are-some-of-the-most-ingenious-algorithms-in-computer-science/answer/Keith-Adams?srid=ul6v) favourites * Skip lists * Paxos * The "state machine" family of lock-free algorithms. * - SIAM News, Volume 33, Number 4 * - American Institute of Physics and the IEEE Computer Society - Comments about it on [reddit](https://www.reddit.com/r/programming/comments/1qztc0/from_the_ieee_computer_society_journal_the_top_10) ### Nine Algorithms that change the World An algorithm is a well defined procedure for performing a task. A household example of an algorithm is a recipe -- for example, the list of ingredients together with the sequence of instructions needed to bake a pie. In order for a computer to perform a task, it needs ingredients -- the data -- and instructions -- the algorithm. Author John MacCormick, currently Professor of Computer Science at Dickinson College, has chosen nine important tasks performed by computers and explained the algorithms that are used. In a chapter devoted to each, he explains: * The development of search engines -- how to find information on the internet. * The PageRank process used by Google to produce highly relevant search results. * Public-key cryptography, enabling secure transmission of secret messages -- such as your credit card number -- over open communication channels. * Methods for detecting errors in data transmission and automatically correcting them. * Several pattern recognition techniques, illustrated by classifying handwritten numbers, facial recognition, and decision trees. * Data compression. Storing text, music, and images efficiently. * Databases. Storing and retrieving information efficiently. Techniques for modifying databases reliably, even when computers crash while the modification is in progress. * Digital signatures. How to be certain data is trustworthy. * Deciding what is computable. Even though the techniques that enable these algorithms are complex, Dr. MacCormick explains them in a clear and interesting manner using well constructed examples. I highly recommend this book for a fascinating and easily accessible look at the core of computer science and its application to everyday lives. ### Timeline of Computer Science Please read and (including the zillion comments below). **CS timeline voting: the results are in!** #### The top 10 1. Euclid’s Elements: 116 votes 2. Turing’s “On Computable Numbers”: 110 votes 3. Gödel’s Incompleteness Theorem: 107 votes 4. Gödel’s P vs. NP Letter to von Neumann: 106 votes 5. George Boole’s Logic: 88 votes 6. Shor’s Algorithm: 88 votes 7. Wikipedia: 85 votes 8. Claude Shannon’s Digital Logic: 82 votes 9. PRIMES in P: 82 votes 10. Cook-Levin Theorem: 80 votes #### The rest Al-Khwarizmi’s “On the Calculation with Hindu Numerals”: 79 votes\ Bardeen, Brattain, and Shockley Invent Transistor: 79 votes\ Babbage’s Analytical Engine: 77 votes\ Tim Berners-Lee Invents WWW: 75 votes\ Fast Fourier Transform: 73 votes\ Brin and Page Create Google: 73 votes\ von Neumann Architecture: 71 votes\ RSA: 70 votes\ Hilbert Calls for Mechanization of Mathematical Reasoning: 69 votes\ Simplex Algorithm: 69 votes\ Claude Shannon Formalizes Cryptography: 68 votes\ Dijkstra’s Algorithm: 68 votes\ Gaussian Elimination Described in Ancient China: 67 votes\ Quicksort: 65 votes\ UNIX and C: 65 votes\ Newton’s Method: 64 votes\ Leibniz Describes Binary Notation, Calculus Ratiocinator: 64 votes\ First Program written by Ada Lovelace: 64 votes\ Gauss’s Disquisitiones Arithmeticae: 62 votes\ Monte Carlo Method: 62 votes\ “Bit” Coined: 62 votes\ TeX Typesetting: 62 votes\ Ginsparg Creates arXiv: 61 votes\ Kleene Invents Regular Expressions: 61 votes\ McCarthy Invents LISP: 59 votes\ “The Art of Computer Programming”: 59 votes\ TCP/IP Protocol: 58 votes\ Strassen’s Algorithm: 58 votes\ PCP Theorem: 56 votes\ Turing Test: 55 votes\ Randomized Primality Testing: 55 votes\ IP=PSPACE: 55 votes\ Scott and Rabin’s Paper on Nondeterminism: 54 votes\ Jacquard Loom: 54 votes\ Colossus Begins Operation at Bletchley Park: 53 votes\ Integrated Circuit: 53 votes\ Chomsky Hierarchy: 52 votes\ Pascal Builds Arithmetic Machine: 51 votes\ First Genome Sequenced: 51 votes\ Reed-Solomon Codes: 50 votes\ Time Hierarchy Theorem: 50 votes\ ARPAnet: 49 votes\ Four Color Map Theorem Proved: 49 votes\ Linux: 49 votes\ Diophantine Equations Proved Undecidable: 46 votes\ Feynman Suggests Quantum Computing: 46 votes\ Deep Blue Defeats Kasparov: 46 votes\ Solomonoff-Kolmogorov-Chaitin Complexity: 44 votes\ Lempel-Ziv Data Compression: 43 votes\ GPS: 42 votes\ Marian Rejewski’s “Bombe” + Alan Turing’s Improvements: 41 votes\ Diffie-Hellman Public Key Exchange Protocol: 41 votes\ Zuse’s Z1: 40 votes\ Viterbi Algorithm: 40 votes\ First Email Message: 38 votes\ Pseudorandom Generators: 37 votes\ Oughtred Invents Slide Rule: 36 votes\ FORTRAN: 36 votes\ ENIAC: 35 votes\ Semaphores: 35 votes\ Gottlob Frege’s “Begriffsschrift”: 34 votes\ Grace Murray Hopper Creates A-O Compiler: 34 votes\ Conway’s Game of Life: 34 votes\ Xerox Parc’s Alto With First GUI: 33 votes\ Kuttaka Algorithm from Ancient India: 32 votes\ Scientific Computing During Manhattan Project: 30 votes\ Wilkes, Wheeler, and Gill Define Closed Subroutines: 29 votes Stroustrup creates C++: 28 votes\ Zimmermann creates PGP: 28 votes\ Dartmouth Conference Popularizes Term “AI”: 27 votes\ Moore’s Law: 27 votes\ Boosting in Machine Learning: 27 votes\ Codd Proposes Relational Databases: 26 votes\ Ethernet Invented: 26 votes\ Valiant Proposes PAC-Learning: 26 votes\ Stallman Writes GNU Manifesto: 25 votes\ Wiesner Proposes Quantum Money and Multiplexing: 24 votes\ Antikythera Mechanism: 23 votes\ BitTorrent: 23 votes\ Low-Density Parity Check Codes: 23 votes\ McCulloch and Pitts’ “A Logical Calculus Immanent in Nervous Activity”: 22 votes\ Engelbart and English Invent Mouse: 22 votes\ Dijkstra’s “Go To Statement Considered Harmful”: 22 votes\ Back-Propagation: 22 votes\ MIT SAGE Creates First Large-Scale Computer Network: 21 votes\ Vannevar Bush Creates First Large-Scale Analog Calculator: 20 votes\ IBM Introduces Hard Drive: 20 votes\ Checkers Solved: 20 votes\ First Packet-Switching Network: 20 votes\ Atanasoff and Berry’s Vaccum-tube Computer: 19 votes\ Vannevar Bush’s “As We May Think”: 19 votes\ Hollerith’s Electromechanical Counting Machine: 18 votes\ MIT Builds First Time-Sharing System: 18 votes\ First Computer Virus: 18 votes\ IEEE Floating-Point Standard: 18 votes\ IBM PC: 18 votes\ “Spacewar!”, First Computer Game: 17 votes\ RISC Architecture: 17 votes\ Intel’s 8086: 17 votes\ al-Jazari’s Water Clocks and Musical Automata: 17 votes\ Edward Lorenz (Re)discovers Chaos Theory: 16 votes\ Apollo Guidance Computer: 16 votes\ CAPTCHAs: 16 votes\ VC Dimension: 16 votes\ Macsyma Computer Algebra System: 15 votes\ Amazon.com: 15 votes\ UNIVAC I: 13 votes\ DaVinci Surgical Robot: 13 votes\ Mark II Incident Popularizes Word “Bug”: 12 votes\ Weizenbaum Creates ELIZA: 12 votes\ ASCII: 11 votes\ TI Handheld Calculator: 11 votes\ Simula 67: 11 votes\ MIT Whirlwind I Displays Graphics: 10 votes\ Sketchpad, First CAD Software: 10 votes\ NCSA Mosaic: 10 votes\ Robert Morris’ Computer Worm: 9 votes\ Pixar Releases “Toy Story”: 9 votes\ Stuxnet Worm: 9 votes\ IBM System/360: 8 votes\ Mac Hack Chess Program: 7 votes\ Microsoft Windows: 7 votes\ Sojourner on Mars: 7 votes\ BASIC: 6 votes\ Apple Macintosh: 6 votes\ SETI\@home: 6 votes\ IBM’s Watson Wins At Jeopardy!: 5 votes\ Atari’s Pong: 4 votes\ Atlas Computer in Manchester: 4 votes\ Norbert Wiener Founds Cybernetics: 3 votes\ First ATM in Tokyo: 3 votes\ Youtube Launched: 3 votes\ VisiCalc: 2 votes\ Jevon’s Logic Piano: 1 vote\ Apple II: 1 vote\ Adobe PostScript: 1 vote\ SABRE Travel Reservation System: 0 votes\ Fischer-Lynch-Paterson Theorem: 0 votes\ Facebook, Twitter Use in Egypt Revolution: 0 votes\ First Machine Translation Demonstration: -1 vote\ Usenet: -1 vote\ Akamai: -2 votes\ TX-0: -3 votes\ CDC 6600: -3 votes\ Compact Disc Invented: -3 votes Aiken’s Mark I: -4 votes CM-1 Connection Machine: -4 votes Whirlwind I Displays Graphics: -5 votes Floppy Disk Invented: -6 votes MITS Altair Microcomputer and Microsoft BASIC: -6 votes Axelrod’s “The Evolution of Cooperation”: -7 votes Microsoft Office: -7 votes Pentium FDIV Bug: -7 votes EDSAC: -8 votes UNIMATE, First Industrial Robot: -9 votes CLU Programming Language: -9 votes 1ESS Switching System: -11 votes UNIVAC Predicts Presidential Election: -12 votes Stanford Arm: -13 votes “2001 A Space Odyssey” Introduces HAL: -15 votes “Spam” Coined: -16 votes First Denial-of-Service Attack: -17 votes Y2K Bug: -18 votes Facebook Launched: -18 votes Nintendo’s Donkey Kong: -19 votes “Robot” Coined: -21 votes CSIRAC -21 Apple’s iPhone: -21 votes Slashdot: -27 votes Godwin’s Law: -29 votes Asimov’s Three Laws of Robotics: -32 votes Match.com: -34 votes de Vaucanson’s Mechanical Duck: -39 votes von Kempelen’s Mechanical Turk: -52 votes ## The Next 50 years of Computing by MIT ### SESSION 1 9:00 AM\ Fifty Years of Robotics; Now the Practical Payoff Rodney Brooks, Rethink Robotics, Inc Tales from the Blocks World Matt Mason, Carnegie Mellon University Dynamic Robots Marc Raibert, Boston Dynamics Aerial Robots: Computing in the Sky Russ Tedrake, MIT CSAIL The Analysis Revolution in Genomics and Modern Medicine Manolis Kellis, MIT CSAIL 10:30 AM - BREAK ### SESSION II 11:00 AM Akamai: From Theory to Practice Tom Leighton, Akamai Technologies Everyday Life in a Data-Rich World Jon Kleinberg, Cornell University The Evolution of Proofs in Computer Science Yael Tauman Kalai, Microsoft Research Quantum Computing and Fundamental Physics Scott Aaronson, MIT CSAIL 12:25 PM - LUNCH ### SESSION III 2:00 PM Towards a Theory of Trust in Networks of Humans and Computers Jeannette Wing, Microsoft Research Harmonizing Technology with Society Latanya Sweeney, Harvard University On the Benefits of Coordination – Before, During, and Even After the Fact! – in Differential Privacy Cynthia Dwork, Microsoft Research The Scalable Commutativity Rule: Designing Scalable Software for Multicore Processors Nickolai Zeldovich, MIT CSAIL 3:25 PM - BREAK ### SESSION IV 4:00 PM Time Sharing vs Personal Computing Ivan Sutherland, Portland State University The End of Moore's Law and the Future of Computing Bill Dally, Stanford University How I invented Ethernet at MIT Project MAC 1969-1972 Bob Metcalfe, The University of Texas at Austin 5:20 PM – ADJOURN Banquet Dinner – Cambridge Marriott Hotel - Grand Ballroom 7:00-9:00 PM Recognition of Bob Fano Entertainment by ImprovBoston Thursday, May 29, 2014 Location: MIT Stata Center, 32-123 Kirsch Auditorium 8:00 AM Continental Breakfast/Registration ### SESSION V 9:00 AM\ Turtles All the Way Down Greg Papadopoulos, New Enterprise Associates Graduate Education and Research in the Information Age Daniel Huttenlocher, Cornell Tech NYC Some Surprising Lessons Learned while Creating a Real MOOC-based Masters of Science Charles Isbell, Georgia Institute of Technology 10:20 AM - BREAK ### SESSION VI 10:50 AM\ Small, n=me, data Deborah Estrin, Cornell Tech NYC The Right Thing: Things We Hit, Things We Missed, Things Still Left To Do Tom Knight, Ginko Bioworks Teaching Computers to See Antonio Torralba, MIT CSAIL Modeling Brain Connectivity from Functional MRI Polina Golland, MIT CSAIL Reflections of an Entrepreneur on Experiences at MIT Then and Now Ray Stata, Analog Devices, Inc *** End of File