COT 5420: Theory of Computation I -- Fall 01
Semester Project

November 27

• Cartaya, Thomas, Barreto, Duque -- Circuit Complexity
• Yan, Yujian, Zheng -- Neural Networks
• Wei, Kasa, Sun, Wu -- Self-Organizing Maps
• Luo, Sun, Wen, Yang -- Elevator Systems

  November 29

• Bresan, Gunawan, Menendez, Nur -- Probabilistic TMs
• Xu, Zhao, Liao, Zhan -- Interactive Protocols
• Yang, Zhang, Dai -- Quantum Computing: Shor/Grover algorithm
• Grosso, Rivera, Martin, Berkley -- Quantum Computing: Cryptography

• Plan for a 16-17 minute presentation, leaving about 3-4 minutes for questions. I suggest making a powerpoint presentation. Presentations that go over the 20 minute limit will be stopped midway.
• The computer cart will be set up for the presentations on both days. Bring your presentation on a diskette. Load it on the computer and open up the file before class starts on the day of your presentation. This would mean arriving 10 minutes before class on that day.
• Make sure that your slides are clear and uncluttered. In general, do not photocopy pages from a book or paper. Put minimal amount of information on the slide and let you oral presentation do the rest of the job. DO NOT READ FROM THE SLIDE, REGARDLESS OF HOW BAD YOUR ENGLISH IS. It is better never to put complete sentences on the slide, since otherwise you will tend to read from it; only put down major points. If necessary, bring a separate sheet of paper with some notes. A good picture or example is worth a thousand words. Concentrate on major ideas and concepts and less on formalism (leave that for the report). Use color and animation liberally to highlight text or pictures. Look at the audience while speaking.
• All members of your group should participate in the presentation. Make sure your group is well coordinated so that no time is wasted and no material is repated.
• As part of the audience, you are strongly encouraged to ask questions. Questions are never meant to harass the speaker. Instead, they help to clarify the presentation for the rest of the class. If you do not understand a presentation, then it was wasted. Learn to look at a presentation critically. You can learn from the mistakes and the successes of other presentations.

1. Write a 1-page summary containing (a) the names of the members of your group, (b) the main references that you used for your project, and (c) a short description of your project. Each group should present one summary.
2. Write a detailed report of your project (no page limit). Wherever possible give original examples and explanations. It would be in your interest to summarize at the end what is original (or different from the main references you used) in your project. Brief and concise descriptions are preferred. Figures will help. Each group presents one report. An ideal report should be neatly formatted, less than 5 pages long and should contain as much original work, examples and descriptions as possible. Print out your reports with the names of your group members on it. All reports should be submitted to me before NOON on November 26. Electronic submissions are fine. Reports that do not cite all their references and that do not cite the source of the material in the report will be penalized.
3. Prepare a 16 minute PowerPoint presentation (allowing for 3-4 minutes for questions). Each group makes one combined presentation. Divide your presentation into approximately 4 equal parts so that all members of the group can be involved in the presentation. Presentations where only one person makes the whole presentation or that does not budget the allotted time properly will be penalized. If you cannot prepare a PowerPoint presentation, make neat transparencies. Photocopies of pages from your references should be avoided as much as possible. Putting too much "text" in your slides is very much discouraged. Presentations that simply involve reading from a slide or a piece of paper will be penalized. Presentations should focus on important concepts, ideas and examples, and should avoid lengthy detailed proofs. All groups should be ready to present on Nov 27th. However, the exact schedule will be announced before Thanksgiving, and they will be scheduled on Nov 27 and 29.

1. Pick a topic or a set of papers and read it thoroughly.
2. Pick a problem or an application where you can apply the idea.
3. Research your application and propose a problem that you can solve.
4. Write down your solution.

• Quantum Computing: Papers & Articles; News; Lots of Related Links; See paper by Bernstein and Vazirani "Quantum Complexity Theory" (postscript form); See paper by Ambianis "A New Protocol and Lower Bounds for Quantum Coin Flipping"; Also see the collection of downloadable papers at tIgor Markov's Quantum Computing Circuits course website;
• Molecular Computing: Seminal Paper by Leonard M. Adleman "Molecular Computation of Solutions to Combinatorial Problems"; Other Publications; Erik's Molecular Computation page; See paper by Reif "Alternative Computational Models: A Comparison of Biomolecular and Quantum Computation"; See paper by Reif "Paradigms for Biomolecular Computation" ; See paper by Paun and Salomaa "From DNA Recombination to DNA Computing Via Formal Languages" ; See paper by Castellanos, Paun, et al. "Computing with Membranes: P Systems with Worm-Objects" ;
• Alternating Turing Machines: See the classic paper titled "Alternation" by Chandra, Kozen and Stockmeyer, Journal of the ACM, Vol. 28, No. 1, 1981, pages 114-133.
• Pebble Games and Time-Space Tradeoffs: See 2 classic papers (1) "On Time Versus Space" by Hopcroft, Paul and Valiant, Journal of the ACM, Vol. 24, No. 2, 1977, pages 332-337, AND (2) "Space Bounds for a Game on Graphs", by Paul, Tarjan, and Celoni, Mathematical Systems Theory, Vol. 10, 1977, pages 239-251.
• Probabilistic Turing Machines: See another classic paper by Gill titled "Computational Complexity of Probabilistic Turing Machines", SIAM Journal on Computing, Vol. 6, No. 4, 1977, pages 675-695.
• Information Theory: There is a book by Gregory Chaitin titled "Algorithmic Information Theory" (on reserve in Library), and two articles by him: (1) "On the length of programs for computing finite binary sequences", Journal of the ACM, Vol. 13, 1966, pages 547-569, AND (2) "A theory of program size formally equivalent to information theory", Journal of the ACM, Vol. 22, 1975, pages 329-340.
• Oracle Turing Machines and Relativizations: Yet another classic paper titled "Relativizations on the P=NP question", by Baker, Gill and Solovay, SIAM Journal on Computing, Vol. 4, 1975, pages 431-442.
• The Power of Interaction and Arthur-Merlin Games: See the following 3 papers: Lund, Fortnow, Karloff and Nisan: "Algebraic Methods for Interactive Proof Systems", Journal of the ACM, pages 859-868; Shamir: "IP = PSPACE", Journal of the ACM, pages 869-877; Shen: "IP = PSPACE: Simplified Proof", Journal of the ACM, pages 878-880.
• Parallel Models of Computation: See a recent paper by Juurlink and Wijshoff "A quantitative comparison of parallel computation models" to find lots of reference to parallel models of computations and parallel machines that have been built.
• Miscellaneous Models See book by Gary Flake titled Computational Beauty of Nature (placed in the reference section in the library) - this book views interesting topics such as Fractals, Chaos, Complex systems, and Adaptation from a computational viewpoint. For example, what is an L-system? what is an IFS? how can it help you to model a tree from a garden? What is a cellular automata and how are they classified? What is Conway's "Game of Life"? What are applications of these models? What is a neural network and what are its applications? How do they learn or acquire knowledge? What are phase transitions and its applications? What are self-organizing maps and their applications? What are hidden markov models and what are they useful for?