• Team and topic selection due 11:59pm April 9.

  • Checkpoint due 11:59pm April 19

  • Project due 11:59pm April 28

  • Presentations during the final exam block: 7:00pm-10:00pm May 6.

Introduction

The goal of the final project is to give you several weeks to explore a topic related to randomized algorithms of your choice in more depth. In the next section are some suggestions, but feel free to consider other ideas (but discuss them with me before you start).

Please keep in mind the amount of time you have to do this project; you should plan to do about the same amount of work on the project each week that you would on a normal lab. In other words, don’t pick a project you can finish in two days, but don’t pick one that would take two months either.

Here’s a synopsis of key details of the final project:

  • You will work in groups of 2-3 students (3 is normative)

  • Each group will produce a written project report (2-3 pages per person), and will give a 25 min slide presentation.

  • Some groups will also produce code and/or experimental data.

Project Ideas

Here are some potential project ideas:

  • Research: select an open research problem you encountered in class this semester, and come up with a plan to try to solve it.

    • Improved bounds on Ramsey Numbers

    • Better algorithms for SAT or 3-SAT

    • Better approximation algorithms for 3-SAT

    • More efficient algorithms for MIN-CUT

  • Advanced Topics: pick an advanced algorithms or theory CS topic that is beyond the scope of class. Write an expository paper explaning the area and what some of the key result(s) are, and develop a 25 min presentation showing what you found.

    • Pseudo-Random Generators

    • Zero-Knowledge Proofs

    • Probabilistically Checkable Proofs and the PCP theorem

    • Martingales

  • Implementation or Experimentation: Pick one of the algorithms or one topic we’ve seen this semester and produce code to implement and/or experiment with randomness in practice

    • SAT algorithm(s)

    • Algorithms for generating random graphs and/or testing properties of random graphs

    • Experimenting with randomness in practice

Or come up with your own idea (again, please discuss with me before getting started)

You are welcome to use existing libraries as well as other resources you find on the web, as long as you use proper attribution and it’s clear what work you personally did.

Project Etiquette

Some of the project ideas might involve large data sets that could quickly blow through your disk quota. To avoid this, you can save them to scratch (instructions). Data on scratch is unlimited, but isn’t backed up.

As a general rule, /scratch is a good place for things that are large, but can be re-created if they’re lost (e.g. data files, program output (if it’s big and the program is deterministic), etc.). You should still keep your source code in your home directory (and in GIT). Definitely don’t add giant data files to your GIT repo, though.

Also, take a look at the department’s suggestions for long running jobs. As that page suggests, the screen program is very helpful, but remember that your screen sessions will last until you manually end them, so try to avoid leaving dozens of abandoned instances of screen on a server.

Project Checkpoint

By the end of the first week, you need to have turned in the project checkpoint in the file checkpoint.tex. Details about what to include in your checkpoint are provided in the file. We will then take time during lab that day (April 20) for each group to describe their project idea to the class in 3-5 minutes.

Project Report

In the LaTeX file, project.tex, you will describe your project. This file already contains a basic structure that you should follow. Feel free to change the section headings, or insert additional sections. Recall that you use the command pdfLaTeX to convert the LaTeX into a pdf file.

Your project repo contains a file called rubric.md. This gives a detailed account of how your project will be graded.

Project Presentation

In addition to your project report, you should present a 25 minute slide presentation describing your project topic and what you did for the project.

Submitting

Before the deadline, you need to submit the following things through git:

  • The LaTeX file for your checkpoint: checkpoint.tex

  • For implementation/experimentation projects, code you wrote to implement your experiments and a README file explaining how to run your code and access any data you use.

  • The LaTeX file with your write-up: project.tex

  • As your project develops and you create more files, be sure to use git to add, commit, and push them. Run: git status to check that all of the necessary files are being tracked in your git repo.

In addition, you must turn in a printed copy of your project report outside my office by the deadline.

Acknowledgements

The structure of this final project closely follows one created and used by Lisa Meeden in her CS63: Artificial Intelligence class.