CSE642 Algorithms Seminar

Locations and Hours:

Friday 11:30-12:45 @ Computer Science Lounge (CS Building 1211).

Course Description:

This reading group provides a meeting place for Stony Brook faculty, postdocs, and students interested in the analysis of algorithms. We meet once a week, with one of three different missions:

  • Paper presentations -- This is fairly informal, with one person (i.e. student) responsible each time for leading the discussions. Nobody will have to lead for more than one paper per semester. We highly encourage students to volunteer for paper presentations, as it is a good opportunity to learn how to give a technical presentation and our reading group is a friendly group of audience to start with. The list of papers you can choose to present, if you do not have a paper already, can be found below.
  • Open Problem Bull Sessions -- where we pose and attack accessible research problems. A good time is had by all.
  • Road Trips -- to the special computational geometry or theory days at NYU, Columbia, and the like.

You can get one credit for participating by simply registering for CSE 642. You are also welcome to come without registering. 

We have a mailing list. Please email me (Jie

 Gao) if you want to be added to the list.

Schedules for Spring08: (past offering: Spring 2006, Fall 2006, Spring 2007, Fall 2007)

2/1: Open problem session.

2/8: Open problem session. Notes and pictures of the discussion can be found here. Thanks to Giordano Fusco for taking the pictures.

2/ 15: Paper presentation by William Lahti on “The hiring problem and Lake Wobegon strategies”, in SODA’08. A blog article from the author. The secretary problem. And Google uses this hiring strategy.

2/22: School closed due to heavy snow storm.

2/29: Open problem session.

3/7: Paper presentation by Giordano Fusco on “Linked decomposition of networks and the power of choices in Polya Urns”, in SODA’08.

3/14: Open problem session.

3/21: Spring break, no meeting.

3/28: GRC, no meeting.

4/4: Open problem session.

4/11: Paper presentation by Slava Akhmechet on “In-place 2D nearest neighbor search”, SODA’08.

4/18: Open problem session

4/25: Open problem session.

5/2: Paper presentation by Pat Regan on “How to optimally read a train schedule”, SODA’08.

5/9: Open problem session.

List of papers for presentation:

I do not give links to these papers. Typically you can find the pdf of the paper (or even better, the slides made by the authors) by a google search on the paper title. If you can not find it, I have hard copies in my office.

1.         Linked decomposition of networks and the power of choices in Polya Urns, SODA’08.

2.        The hiring problem and Lake Wobegon strategies, SODA’08.

3.        In-place 2D nearest neighbor search, SODA’08.

4.        Non-decreasing paths in a weighted graph or: How to optimally read a train schedule, SODA’08.

5.        Minimum weight convex Steiner partitions, SODA’08.

6.        Greedy drawings of triangulations, SODA’08.

7.        Your suggestion?

Last updated: 1/28/07