We will update this page as people choose their projects. DATES, etc: ----------- Send me (karlin@cs.washington.edu) and Thach (ncthach@cs.washington.edu) your plan for your final project by Monday, March 2, 2009. The talks will be given on Tuesday, March 10, 2009 and Monday, March 16th, 2009. In your email, please indicate if you cannot make one of those dates, so we schedule you appropriately. Beyond that, we will schedule the talks in an order that is related to the material being covered. GENERAL GUIDELINES: ------------------- Your presentation can either be technical, in which you cover a proof (or part of a proof if you are sharing), preferably from Sipser or Arora/Barak, or historical/philosophical, in which you present some interesting information from a popular science book related to the course material. Your presentation should be 10 minutes long and should be done using slides. If you choose to cover a proof, you need to figure it out on your own. We will not be helping students to understand the proofs. GRADING: _______ As I said in class, for proofs, I will be grading on clarity. I would much rather that you do a small amount of material well, than rush through more material, so be careful about that. For historical/philosophical presentations, I will be grading you on how interesting/entertaining the presentation is. Of course I'm still looking for clarity. GENERAL COMMENTS ABOUT THEOREMS YOU COULD CHOOSE: ------------------------------------------------ Below is a list of possibilities for theorems whose proofs you could present. I'm also open to the possibility of you finding something else, but it needs to be cleared with me. Presenting the proofs of some of these theorems will require more than 10 minutes. If that is the case, I'd like you to find one or two other people to share the presentation with. If you do present a proof as a group, you'll need to figure out a logical way to partition the proof among you. I've listed how many people I think are needed to cover each proof listed below, but it is quite possible that I am not very good at judging this. As I said above, I'd rather you do a smaller amount well than a larger amount in a less clear or rushed fashion. Some of these theorems require background. For example, if you do a theorem related to context free grammars, you need to define what a context free grammar is. The only background you can assume on the part of the listener is what I've covered in class, but even there use your judgement as to what concepts need to be reviewed in order for the presentation to be clear. You should design your presentations so that they are clear to the whole class. pwd Some of these theorems I mentioned in class, but didn't prove. Or else I hand-waved the proof. Those are perfectly legitimate choices for presentation. SOME POSSIBLE THEOREMS WHOSE PROOFS YOU COULD CHOOSE TO PRESENT FROM SIPSER (2nd edition) ------------------------------------ *'ed theorems are taken already. * Theorem 3.13 [Claim 1.9 in Arora/Barak] (1 person) Richard Cook rcook@cs.washington.edu * Theorem 3.16 (1 person) Arun A V avarun123@yahoo.co.in * Theorem 4.1 James Shimada jshimada@gmail.com * Theorem 4.2 Jian Li lijian@microsoft.com * Theorem 4.5 Jianan Wang numenor@gmail.com * Theorem 4.8 Vlad Alexandrov Vlad.Alexandrov@microsoft.com March 16 * Theorem 4.7 Tyler Akidau t.a.akidau@gmail.com Any of Theorems 4.3, 4.4, 4.9 (each is 1 person) * Theorem 5.13 Ryan Sturgell ryan.sturgell@gmail.com Theorems 5.9, 5.10 (each is 1 person) Theorem 5.15 (2 people) * Theorem 5.30 (1 person) -- Duncan Smith duncanesmith@gmail.com * Solution to Problem 5.28 (1 person) David St. Hilaire davidjsh@u.washington.edu Theorem 7.37 [Section 2.3.4 in Arora/Barak] (3 people) * Theorem 8.9 (1 person) Abdul Hyee Waqas awaqas@cs.washington.edu * Theorem 8.14 (2 people) Umair Aftab omairaftab@gmail.com Material from Section 8.4 [Corresponding material in Arora/Barak is Section 4.4] (5 people worth of material, but individuals could pick off something) Theorem 9.3 (2 people) Theorem 9.4 (1 person) -- I did it, but it could be done more carefully. Theorem 9.15 (2-3 people) Theorem 9.20 [Related material in Arora/Barak is in Section 3.5] (2 people) * Section 10.3 [Section 5.2 in Arora/Barak] (2 people) * -- Eric McCambridge ericm6@cs.washington.edu March 16. SOME POSSIBLE THEOREMS YOU COULD CHOOSE TO PRESENT FROM ARORA/BARAK =================================================================== (There is overlap between the two books. Generally below I have only included theorems that are NOT listed above as being in Sipser.) Claims 1.8 * Claim 1.11 (1 person each) Scott Anson sanson@microsoft.com Theorem 1.13, the proof in Appendix 1.A (2 people) Material in Section 2.3.6 (1 person) * Theorem 2.17 (1 person) Domenico Lemme domlemme@hotmail.com * Theorem 2.25 (1 person) David Fields dcf@alumni.cmu.edu * Section 7.2.1 (1 person) Xiaoxuan Jin jinn_amaranth@hotmail.com * Section 7.2.3 (1 person) Eric Leese eleese99@yahoo.com Lemma 7.14 + 7.15 (1 person) David Driver dvdriver@u.washington.edu Theorem 7.18 (2 people) Section 8.4 (3 people, but 2 could do most of it) Appendix 8A (3 people) * Anything you want from Chapter 10 (quantum computation) John Franco jcf@drizzle.com March 16 Dennis Mattoon mattoon@u.washington.edu BOOKS: ======= NOTE: It's fine for up to 4-5 people to choose the same book. There is plenty of material in each, but you will need to coordinate your presentations so there is no overlap. The Universal Computer: From Leibniz to Turing Alan Turing: The Enigma -- * Aaron Greene akgreene@gmail.com "Incompleteness: The Proof and Paradox of Kurt Godel" or "Godel's Proof" -- * Alex West awest@u.washington.edu March 16 -- * Hemanth Srinivas hemanth@u.washington.edu March 10 -- * Thais Melo thaismelo@gmail.com The Mystery of the Aleph: Mathematics, the Kabbalah, and the Search for Infinity -- * Jason Terpsma jason.terpsma@gmail.com -- * Bryce Morsello morseb@u.washington.edu The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography -- * Rick Byers rbyers@cs.washington.edu -- * Egor Nikitin enikitin@cs.washington.edu -- * Will Morton frostbyte@gmail.com