Overview of Requirements

• Sign up for both a topic and partner on the Piazza post titled: Final Project sign-up form
• (5%) A one-paragraph abstract emailed to me by Wednesday, November 11.
• (15%) A 1-2 page initial report and proposed action plan emailed to me by Friday November 20.
• (5%) A brief status update checkpoint emailed to me on Wednesday November 25.
• (5%) A second status update checkpoint emailed to me on Friday December 4.
• (40%) A (maximum) 10 page paper discussing your topic due on Monday, December 7. To get proper formatting for this writeup, use the sample paper format contained here. Instructions on how to untar this file and how to use its contents are in the FAQ section below.
• (25%) A 15 minute presentation presenting your topic, to be given December 11 during our finals period.
• (5%)Critical Review/Evaluations of other project presentations, to be done during the December 11 finals period.

Do not blow off the initial report or checkpoints. The action plan should describe what tasks you plan on accomplishing in the remaining three weeks. Each checkpoint should describe how tasks from the action plan have been accomplished, or what issues have arisen that prevented intermediate tasks from being completed on time.

This final project should be done with one partner, but you don't have to work with your usual partner. In fact, I recommend looking at possible topics on your own and then finding a student with similar interests. You are welcome and encouraged to discuss ideas with anyone in the class (not just your lab or final project partner).

Frequently Asked Questions

• How do I open/use the sample-paper?
  The sample-paper is contained in a tar file. In order to open and productively use this file, do the following:
  • Download sample-paper.tar
  • Enter tar xvf sample-paper.tar This should "untar" the tar file. You should get a directory named sample-paper which contains several .tex files and one .bib file.
  • Inside this directory, use template.tex as a base template for your file. It should contain proper formatting for your final paper, instructions on how to enter author information, how to compile your paper, etc.
  • If you want to see a paper that uses this template, compile sample-paper.tex. Instructions on how to compile this are in comments in sample-paper.tex
• Can I choose a project I've worked on before?
  If previously you've worked on a topic related to the probablistic method, randomized algorithms, etc. before, you're welcome to continue with this topic. However, you can't just hand in already-completed work. In your action plan clearly state what you've already done for your topic, and what you plan on doing this semester for this class. For instance, perhaps you want to augment an algorithm to provide additional functionality. Or maybe you've worked w/Ramsey Theory, and you'd like to get even newer/better bounds on them. That's great, but make sure it's clear what work counts for this class and what work you've already done before.
• Four weeks doesn't seem like much time to do research. What if we plan on getting new results but fail? Do we just end up failing the CS49/Math59?
  Four weeks isn't much time to accomplish new results, so no, you won't fail just because you didn't get a publication out of your final project. It's perfectly fine if your project is about deeply understanding existing work and writing an expository paper. If you do want to try to tackle new results but don't end up getting them, write down where things went wrong and what insights you gained from your failed attempt.

Introduction

Throughout the course, we have seen a good amount of discrete probablity theory, several different problems, techniques for using the Probabilistic Method, and many different problems/applications of the Probabilistic Method. With each topic, you have built foundations of an advanced toolkit for understanding and analyzing combinatorial and computational processes that use probability and randomness. The constraints of a 13-week course limited the number of Probablistic Method/Theoretical Computer Science topics we considered, as well as the variations and nuances of some that we did cover. The central goal of this course, however, was not to memorize every technique and problem ever considered. Rather, it was to develop the skills of design and analysis that are a prerequisite to becoming a competent theoretical computer scientist.

For your final project, you will demonstrate these newly acquired skills by exploring a related topic at a deeper level than what we've been able to cover in class. You will write a medium-length paper which will discuss your chosen topic. Your report should introduce the topic, provide a motivating example, compare and contrast to a related result (when applicable), and analyze a few aspects of your topic in detail. (For example, if your topic is a detailed randomized algorithm, you should analyze a few of the main details. If your topic is a probabilistic Method technique that involves nontrivial analysis, you should examine some (but not necessarily) all of the details. You will demonstrate not only your conceptual understanding of the topic(s), but also your ability to analyze probabilistic/randomized processes, as well as your written and oral communication skills.

Project Format and Deliverables

The main deliverables for this project are an 8-10 page paper and a 15 minute oral presentation. (Note: if you propose to design and implement a randomized algorithm, I am willing to relax the length of the paper.)

Choosing a Topic

The choice of topic to consider is largely open-ended. However, you must send a short abstract (one paragraph) explaining your plan by Wednesday November 11. This should include the topic you plan to cover, what you aim to discuss in your paper, and what else you plan on producing (say C++ code if you plan on implementing a randomized algorithm). You can use either the Alon/Spencer book or the probability section of the Shoup book to find example topics we did not cover. You can also explore resources online.

If you have little intuition for what you want to investigate for your final project, I suggest doing one of the following:

1. Looking through the Alon/Spencer book for ideas, especially through any of the "Probabilistic Lens" sections which appear at the end of each chapter.
2. Perusing through the resources/ideas below
3. Coming to me to discuss options ;)

Other resources include:

• Wikipedia's Probablistic Method page, as well as the links contained within.
• Wikipedia list of Probabilistic Methods applications
• Me.
• Google it!

Some example Probabilistic Methods topics include:

• Ramsey Numbers (upper bounds, off-diagonal lower bounds, applications of Ramsey Theory)
• Lovasz Local Lemma (Alon/Spencer Chapter 5)
• Random Graphs
• coding theory
• random restrictions (see e.g. this wikipedia article)

Some probability-related topics include:

• Chernoff-Hoeffding Bounds
• The Berry-Esseen Theorem
• Martingales/Azuma's Inequality
• Janson Inequalities

Some example Randomized Algorithm/Theory CS topics include:

• Pseudo-random generators and/or derandomization results
• A constructive version of the Lovasz Local Lemma
• Complexity classes: P vs RP vs BPP
• randomized algorithms for k-SAT (or some other NP-Complete problems)

Writeup Requirements

Your writeup should be well-structured and follow scientific writing principles. You can structure as you see fit, but at a minimum, your paper should include:

• An introduction - this can include a history and a preview of the central features of the problem/technique/idea.
• Motivation - what is the problem that needs to be solved? You should understand why the problem/technique/idea is being studied and explain so here.
• Background/related work - what does this relate to from class? What are the conceptual differences? Are there other techniques/ideas that generally compete with your choice?
• Illustration - If you're presenting a Probabilistic Method problem, run through an example solution. (e.g. as we've done with the First/Second Moment Methods, or as we did w/Ramsey Number results)
• Analysis - If you are investigating an algorithm, provide pseudocode. For a Probabilistic Method application, provide analysis of the proof of your claim(s). This does not need to be exhaustive, and e.g. how much you cover depends on the complexity of the problem.

Your paper should be typed in LaTeX; no hand-written writeups will be accepted. The exception is with illustrations, which can be neatly drawn and attached to your writeup. I would prefer you scan and attach the images to your PDF document, if possible. If you are interested, feel free to email me any LaTeX questions.

In terms of the length of your writeup, it is really up to you to judge how much material adequately describes your data structure/algorithm. Your writeup, excluding figures, should not exceed 10 pages.

Presentation

A short, 15 minute presentation is required. All students will evaluate your presentation on the following criteria:

1. Rate the introduction/motivation for the material
2. How effective was the presenters sample illustration in conveying the high-level features of the data structure/algorithm?
3. Overall, how effective was the presentation in explaining the data structure or algorithm?
4. Briefly, describe the strongest part of the discussion
5. Briefly, list one thing the presenter could improve upon to help you understand the topic better

Both partners are expected to contribute equally to the presentation and writeup

Presentation Logistics and Tips

• You should use powerpoint/slides for your presentation. Also, be prepared to show up a few minutes early to set up your laptop.
• Some students in the past have provided a worksheet to help in their presentation, or to supplement their presentation with more details that had tobe omitted due to time.
• Be sure to practice! 15 minutes goes by much faster than you'll expect.
• Do not try to cover every aspect of your topic. Specifically, the presentation does not need to cover all the aspects of your paper. People usually overestimate how much can be fit into a 15 minute talk.
• Moreover, a good strategy is to concentrate on one sub-problem and give a high-level intuition of other topics.
• Be sure to think of a good example/illustration - this is the best way to help your peers understand the technical details of your topic in a short amount of time.