The Talk --------- Being able to give a good talk is an important and difficult skill. In the course evaluation, almost everyone said that giving a talk was very useful, but that hearing them was a big waist of time because no one followed them. Grade ----- - Class understanding and interest 33 1/3% (marked by class) - Quality of material covered 33 1/3% (relevancy,difficulty) - Quality of talk & slides 33 1/3% - Aim for 15 min. You will loose 3% for every minute over 20 mins. (We need a time keeper) Giving a good talk. ------------------- Goals: - Get most of the audience to follow the talk. (Give a few things for people who are slower and a few things for people who are faster) - Get people interested in the topic. Why are you interested in it? - Get people to understand the big picture. - Get people to understand the general proof techniques. Do NOT give a talk that the class does not understand. - This is a waste of time. - I did not understand most of the class talks. I got the impression that the speaker did not understand what they were saying either. - It is better to cover the material at the level that you know it or to cover easier material. - Practice with someone. Have that someone be honest whether he/she understands it within the required time. - Do not copy from a paper to the slides and then read the slides without understanding what you are saying. Study the material. Understand the material. Then CLOSE the books. Take a 1/2 hour break. Then put together the talk in YOUR OWN words. Do not open the book to copy. If you get stuck, repeat these step always taking a break between reading an writing. - Perhaps I should even make students do it on the blackboard with NO NOTES. This way we know what YOU know. Do NOT run over the time slot given. - Aim for 15 min and DO NOT exceed 20 min. It is YOUR job to stop. - You will loose 3 marks for every minute over 20 mins. - To keep a talk to a short time, it needs to be well orchestrated and practiced. - Dont cover so much material. - use few slides. & its ok to have slides that you never use. Give a user friendly talk - Do not simply read your slides. Talk to us. Look at the audience - Don't go too fast - Type check your slides (typos are very distracting) - Make sure the type font you use is not too small - When explaining something, assume that they have only understood 1/2 of what you have said before. Remind them. If there are places where you start something new, tell them that they can turn their brains on again if they have turned off. - Once a person is lost for a minute, you risk having their brain turn off. - Do not have more text on a slide than people are willing to read. Help them know where you are on the slide. I like pictures. They can be worth 1000 words. - As an audience, I find it hard to both listen to what is being said and to read lots text on the screen. Topics -------- 2005 - Union Find in log^*(n) amortized time - For which sets of coins does greedy alg work - Random algorithms (MaxCut, MinCut, Primality testing ...) - On line algorithms (Borodin's book) - Genetic Algorithms - Game Theory (Pebbles game) - Quantum Algorithms (too hard) - probabilistic method (Spencer's book) - Cryptography (Elliptic Curves, ...) - Approximating Traveling Salesman on a plane. - Simulated Annealing - Fair/EvyFree Cake cutting 2006 - Genetic Algorithms - Eliptic curves - cryptography - Unit-Task Scheduling Problem - Game Algorithms - k-Server Problem - pebbles: time vs space - Dynamic Programming - Robust Graph Coloring on Paths - Convex hull - Art Gallery Problem - Chart Packing Problem - Markov Chain Monte Carlo - Huffman codes - Linear Programming - Nearest Neighbor Algo for P2P Settings - Travelling Salesman Problem (TSP) - Edmonds-Karp Network Flow - Path with largest smallest edge 2007 - Hamitonian Path is NP-Complete - String Match - Max Cut - Genetic Algorithms - Approx Algorithms - Huffman Codes - Elliptic Curve Cryptography - Hidden Markov Model - The Art Gallery Problem - The Pebble Game 2009 (Sabatical) 2010 - A* Algorithm - Ant Algorithm - Genetic Algorithms - Huffman Code V.S. Optimal Binary Search Tree - Interesting Convex Hull Algorithm - Minimal Steiner Tree - Painter's Algorithm - Finding Bridge in a Graph - Artificial Neural Networks 2011 - Neural Nets (Quantum) - Graphic Models - Stone Game & P Space - Consistent Hashing - QR algorithm for finding Eigen Values Sources Corman Gems of CS papers (we have had limited success)