Projects will be presented in class the week of April 20th. A report on each project, of no more than 4 pages (with an optional 5th page for figures/experimental results), with details of (a) the problem (b) the algorithm (c) your ideas (d) any relevant experiments, is due by midnight on Sunday, April 19th, and should be submitted by email.

- Spanning trees: Expected linear time algorithm (Karger-Klein-Tarjan)
- Spanning trees: application to vision: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.6267&rep=rep1&type=pdf
- Integer multiplication with FFT
- Max-flow: Lee-Rao-Srivastava
- Matrix multiplication
- Nearest neighbors: K-d trees (Bentley)
- Solving linear equations mod n.
- Factoring integers
- Satisfying parity equations (with and without noise).
- Linear programming: simplex and variants (Barasz-V.)
- All-pairs network reliability (Karger)
- Knapsack/Subset-sum in polynomial space (Lokshtanov-Nederlof): http://www.ii.uib.no/~daniello/papers/SaveSpace.pdf

I’m interested in working on the Knapsack/Subset-sum in polynomial space and am looking for people to work with. Would anyone be willing to work with me on this?

Hey if you are still looking for people I would be interested in working with you.

I’m interested on working on this too, if there’s room in your group.

Petros and I would like to work on Max flow using Lee, Rao, Srivastava.

Chris Altonji and I would like to work on the All-pairs network reliability problem. We do want to ask a few questions after class though.

I am joining Chris and Hunter on this project

Shawn and I are interested in working on Spanning trees: Expected linear time algorithm (Karger-Klein-Tarjan)

I will be working on ANN.

Which paper? Who are your partner(s)?

I’ll be joining Willie on ANN.

I will also be one of his partners.

Wenduo Yang, Hongzhao Guan and I will be working on topic 10 “Linear programming: simplex and variants (Barasz-V.)”

Suvrat Bhooshan and Goutam Venkat will be working on Topic 12: Knapsack

Ratchapong and I are interested in topic 8 Factoring integers.

Farhan, Dale, and I would like to work on 5. Matrix multiplication

Surya and I will be working on expected linear time algorithm for spanning trees

This project has already been chosen.

Hey Daniel, would you and Surya mind having another member? And if you haven’t chosen another project yet, spanning trees: application to vision has not been chosen yet, as far as I know.

Sure! It will be the three of us on Spanning trees: application to vision then.

I would like to work on topic 2, spanning trees: application to vision (if it hasn’t been chosen). If anyone would like to join me, please let me know.

Alternatively, if you are just looking for group partners and have another project in mind, I am flexible with the research topic choice. Thanks!