FacultyAlgorithmChallenge

Guidelines for Evaluation

This document can also be accessed through http://j.mp/facultyPK

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

  • http://j.mp/algoAtWork

Dictionary of Algorithms and DS (DaDS)

https://xlinux.nist.gov/dads/

Quora Based

  • http://j.mp/AlgoKG

  • https://www.quora.com/What-is-the-most-clever-yet-simple-algorithm

  • https://www.quora.com/Which-are-the-10-algorithms-every-computer-science-student -must-implement-at-least-once-in-life

  • https://www.quora.com/What-are-some-interesting-algorithms-that-have-no-known-im plementation-to-date

Misc

  • http://j.mp/algo2KG

  • http://www.scriptol.com/programming/list-algorithms.php by various application domains

  • http://www.scriptol.com/programming/graphic-algorithms.php

  • http://blog.hackerearth.com/2015/05/top-7-algorithms-and-data-structures-every-programmer-should-know-about.html

  • http://interviewkickstart.com/curriculum - what you need to know to get employed at leading tech companies

Stackoverflow TCS (Theoretical Computer Science)

  • https://cstheory.stackexchange.com/questions/189/algorithms-from-the-book

Personality based

  • 50 ways MIT has transformed computing - http://j.mp/mitCSE

  • http://www.informit.com/articles/article.aspx?p=2213858 - what Knuth thinks of algorithms (search for "algorithm" across the article) - https://news.ycombinator.com/item?id=10897460 - Hackers on Knuth's books

  • https://www.quora.com/What-is-Professor-Thomas-Cormens-favorite-algorithm - 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 favourites

    • Skip lists

    • Paxos

    • The "state machine" family of lock-free algorithms.

  • http://www.siam.org/pdf/news/637.pdf - SIAM News, Volume 33, Number 4

  • https://www.computer.org/csdl/mags/cs/2000/01/c1022.html - American Institute of Physics and the IEEE Computer Society - Comments about it on reddit

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 https://www.scottaaronson.com/blog/?p=524 and https://www.scottaaronson.com/blog/?p=608 (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

http://mac50.csail.mit.edu/agenda.html

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

NextREADME

Last updated