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.

  1. Spanning trees:  Expected linear time algorithm (Karger-Klein-Tarjan)
  2. Spanning trees: application to vision:
  3. Integer multiplication with FFT
  4. Max-flow: Lee-Rao-Srivastava
  5. Matrix multiplication
  6. Nearest neighbors: K-d trees (Bentley)
  7. Solving linear equations mod n.
  8. Factoring integers
  9. Satisfying parity equations (with and without noise).
  10. Linear programming: simplex and variants (Barasz-V.)
  11. All-pairs network reliability (Karger)
  12. Knapsack/Subset-sum in polynomial space (Lokshtanov-Nederlof):


  1. 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?


  2. 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.


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


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


    1. 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.


  5. 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!


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s