This document can also be accessed through http://j.mp/facultyPK
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.
- 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?
- Choose at least one real-world application that the algorithm finds use for. Don't choose more than two. Describe the real-world application.
- Show the code for the algorithm either in pseudo code or your favourite language
- Choose whatever format makes sense to you to present all the above three. Bring your creativity to the fore.
How do I go about finding algorithms to get inspired by? Visit any of the following links.
- 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
- 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
- https://cstheory.stackexchange.com/questions/189/algorithms-from-the-book
- Euclid's Algorithm features in this list
- And also on this list - https://cstheory.stackexchange.com/a/10422/12933
- From Software Engineering SO
-
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
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.
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!
- Euclid’s Elements: 116 votes
- Turing’s “On Computable Numbers”: 110 votes
- Gödel’s Incompleteness Theorem: 107 votes
- Gödel’s P vs. NP Letter to von Neumann: 106 votes
- George Boole’s Logic: 88 votes
- Shor’s Algorithm: 88 votes
- Wikipedia: 85 votes
- Claude Shannon’s Digital Logic: 82 votes
- PRIMES in P: 82 votes
- Cook-Levin Theorem: 80 votes
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
http://mac50.csail.mit.edu/agenda.html
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
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
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
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
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
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