Basically: pick a problem and a paper, read the paper, and write a report about it (at most 10 pages).
You may choose a paper on your own (see some examples below). Please check with me (e.g., by e-mail or during my office hours) to ensure that your choice is appropriate. In accordance with the "spirit" of this course, the emphasis should be on well-defined problems and algorithms with provable performance guarantees (worst-case time, expected time, approximation factor, competitive ratio, etc.).
The first part of your report should devoted to an introduction to the problem and a short survey of known results. (This may require looking up multiple papers in the literature.)
The second part of your report is a description of the algorithm and analysis from your chosen paper. Don't just paraphrase the paper's description. Give your own interpretation. Because of the page limit, you might want to highlight intuition and the main ideas rather than explain all the low-level details (and if the paper contains multiple results, you don't have to describe all of them -- pick the most interesting parts). Point out any connections with techniques we have seen from class.
The final part should be your critique of the paper (e.g., how do the techniques and results of the paper compare with previous work? with known lower bounds?). State open problems, including any of your own, for future work in the area. (And if you are able to obtain an improvement or solve an open problem, I'd be happy to hear about it!)
Below are just a few random examples, to give you some ideas; you don't have to choose from this list. Use Google Scholar and DBLP to search for papers. Well-known conferences in the area include SODA, FOCS, STOC, ICALP, ESA, WADS, etc.