The history of our algorithms seminar demonstrates that these sessions lead to publications with considerable regularity. We encourage students to take these problems and complete/polish the results so they can be pushed out the door. Problems which have the potential of making it include the car painting problem, string compliant mazes, two person tree walking, alarm clock TSP, and realizing rectangles by paper folding -- can you make them happen?

We are missing the notes of many problem sessions, particularly in the years 2000 to 2002. Please send me anything you can find and I will add them to the list...

2006 Sessions

• March 10, 2006 -- Problem Session Hole-Free Polygons and Guarding Lead by Joe Mitchell. Notes by Girishkumar Sabhnani and Joe Mitchell.
• March 17, 2006 -- Problem Session. The Hip-Hop DJ Scratches Again Lead by Steven Skiena Notes by Valentin Polishchuk.

2005 Sessions

• January 28, 2005 -- Problem Session Planarity of k-Nearest Neighbor Graphs Lead by Joe Mitchell. Notes by Joe Mitchell and Yue Wang.
• March 4, 2005 -- Problem Session Performance Analysis of a Pseudo-Diameter Algorithm Lead by Steven Skiena. Notes by Janet Braunstein and Joondong Kim.
• April 29, 2005 -- Problem Session Permutation Pattern Matching in Strings Lead by Steven Skiena Notes by Sudipto Mukherjee.
• September 2, 2005 -- Problem Session TSP with Countries Lead by Steven Skiena Notes by Shweta Jain.
• October 23, 2005 -- Problem Session Affirmative-Action Matching, Lead by Estie Arkin. Notes by Haodong Hu.
• December 2, 2005 -- Problem Session Scheduling with Start-Up Costs, Lead by Steven Skiena. Notes by Rob Johnson.

2004 Sessions

• March 10, 2004 -- Problem Session Reeb Graph Construction Lead by Herbert Edelsbrunner. Notes by Reid Powell.
• March 12, 2004 -- Problem Session Incremental Motif Construction from Profile Matrices. Lead by Steven Skiena (from Pavel Sumazin). Notes by Reid Powell.
• April 15, 2004 -- Problem Session String-Compliant Maze Problem Lead by George Hart. Notes by Andrew Mehler. (We also have a hardness proof for trees, but what about a path?)
• April 23, 2004 -- Problem Session Minimizing two-person tree traversal time. Lead by Steven Skiena (from Samir Das). Notes by Joe Mitchell.
• September 3, 2004 -- Problem Session, Binary string packing without carries Lead by Steven Skiena (from Jeff Nickerson). Notes by Eli ``String'' Packer. Subsequent results are described by Joe Mitchell.

  This work became Attention and Communication: Decision Scenarios for Teleoperating Robots J. Nickerson and S. Skiena, Proc. 38th IEEE Hawaii Int. Conf. System Sciences, Big Island Hawaii, January 3-6, 2005.

• October 22, 2004 -- Problem Session, The greedy postage stamp problem for peer-to-peer networks Lead by Alex Mohr. Notes by Alex Mohr.
• November 12, 2004 -- Problem Session, The Hip-Hop DJ Problem (a variation on string compression). Lead by Steven Skiena Notes by Janet Braunstein, with subsequent results by Xiaotian(Tim) Yin.

2003 Sessions

• February 14, 2003 -- Problem Session Maximum weight subgraph of low girth Lead by Steven Skiena (from Pavel Pevzner) Notes by Levon Lloyd.

  This work was cited in ``De novo Repeat Classification and Fragment Assembly'' by Pevzner, Tang, and Tesler, RECOMB 2004.

• April 4, 2003 -- Problem Session Coordinating camera control (from Olaf?)
• September 12, 2003 -- Problem Session, School Class Partition / Lawn Mowing with Clippings Lead by Joe Mitchell. Notes by Matthew Knecht.
• October 17, 2003 -- Problem Session, Hotel Reservation Scheduling System Lead by Steven Skiena. Notes by Dimitris Papamichail.
• October 31, 2003 -- Problem Session, Matya's Load Balancing Problem. Lead by Matya Katz
• November 7. 2003 and beyond-- Problem Session, Dror's TSP conjecture. Lead by Joe Mitchell (from Moshe Dror). Reports from Joe Mitchell, Saurabh Sethia, Shweta-Jain, and the group at large.

  Ultimately the conjecture was disproved. This work lead to the paper: M. Dror, Y. Lee, J. Orlin, V. Polishchuk. The TSP and the Sum of its Marginal Values International Journal of Computational Geometry and Applications, Vol. 16, No. 4, pp. 333--343, 2006.

• November 21, 2003 -- Problem Session Double wedge separability with horizontal/vertical lines to maximize the product of cardinality of 1st and 3rd quadrants (how to beat O(n^2)?) We solve it. (see notes)

2002 Sessions

• September 9, 2002 and beyond -- Problem Session. Sorting with Length-Weighted Reversals Lead by Steven Skiena.

  This work became the paper Improved Bounds on Sorting with Length-Weighted Reversals (with M. Bender, D. Ge, S. He, H. Hu, R. Pinter, S. Skiena, and F. Swidan) 15th ACM-SIAM Symp. on Discrete Algorithms (SODA '04). New Orleans LA, January 2004.

• Fall 2002 -- Problem Sessions Olaf's Box Moving Problem. Lead by Olaf Hall-Holt. This work ultimately became The Box Mover Problem by Valentin Polishchuk, Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04), pp. 36-39.
• November 15, 2002 -- Problem Session Alarm Clock TSP Lead by Steven Skiena.

2001 Sessions

• April 13 and 20, 2001 -- Problem Session, Deconvolving Sequence Variation in Mixed DNA Populations. Notes by Steven Skiena.

  This work became the paper Deconvolving Sequence Variation in Mixed DNA Populations by A. Wildenburg, S. Skiena, and P. Sumazin, Proc. RECOMB 2002.

• March 9, 2001 -- Problem Session, The Snowblower Problem Posed by Joe Mitchell. Notes by Valentin Polishchuk.

  This work became the paper E. M. Arkin, M. A. Bender, J. S. B. Mitchell, V. Polishchuk. The Snowblower Problem. Proc. 7th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2006, pp. to appear, New York City, July 16--18, 2006. . See Arxiv for a longer version.

2000 Sessions

• March 16, 2000 -- Problem Session, Scheduling for Memory Coherent Ray Tracing From Kevin Kreeger and Ingmar Bitter.
• September 8, 2000 and beyond -- Problem Session, The Car Painting Problem Lead by Steven Skiena Notes by Jonathan Danieley and Pavel Sumazin.
• September 27, 2000 -- Problem Session, Online processor allocation/ Lead by Michael Bender.
• December 8, 2000 -- Problem Session, Job Scheduling and Car Painting Notes by Nenad Jovanovic.

1999 Sessions

• January 29, 1999 -- Problem Session, Separating Red/Blue Points with an Axis-Oriented Cross Lead by Carlos Serra. Notes by Steven Skiena and Joe Mitchell.

  This work became Some Separability Problems in the Plane, by E. Arkin, F. Hurtado, J. Mitchell, S. Skiena and C. Seara. 16th European Workshop on Computational Geometry, 51-54, Eliat, Israel, March 13-15, 2000.

• February 12, 1999 -- Problem Session, Computing the Edit Distance Between Two Graphs Posed by Gabriel Valiente. Notes by Steven Skiena.
• February 26, 1999 -- Problem Session, Minimum weight zero skew trees Lead by Joe Mitchell Notes by Saurabh Sethia.
• March 5, 1999 -- Problem Session, More on Minimum weight zero skew trees Lead by Joe Mitchell Notes by Saurabh Sethia.
• March 19, 1999 -- Problem Session, Folding Paper Maps Posed by Erik Demaine. Notes by Steven Skiena.

  This work became When Can You Fold a Map? E. Arkin, M. Bender, E. Demaine, M. Demaine, J. Mitchell, S. Sethia, and S. Skiena, Proc. 7th Workshop on Algorithms and Data Structures (WADS), Providence, RI, USA August 8-10, 2001. Springer-Verlag LNCS 2125, 401-413. Also, Computational Geometry: Theory and Applications, to appear.

• April 8, 1999 -- Problem Session, Steiner tree problem with minimum number of Steiner points and bounded edge-length Posed by Saurabh Sethia.
• October 22, 1999 -- Problem Session, Table Layout Optimization Posted by Erik Demaine. Notes by Barry Cohen.
• October 29, 1999 -- Problem Session, Point Sets Admitting Many Non-Crossing Matchings

1998 Sessions

• January 23, 1998 -- Problem Session, lead by Steven Skiena Covering Graphs by Bipartite Cliques.
• February 20, 1998 -- Problem Session, lead by Steven Skiena Maintaining Dynamic Set-Partitions

  This work became the paper Efficient Data Structures for Maintaining Set Partitions M. Bender, S. Skiena, and Saurabh Sethia, Proc. SWAT 2000.

• April 20, 1998 -- Problem Session, lead by Steven Skiena Identifying Gene Regulatory Networks

  This work became the paper Identifying Gene Regulatory Networks from Experimental Data (with T. Chen and V. Filkov) Proc. RECOMB '99, Lyon France, April 1999.

• September 4, 1998 -- Problem Session, lead by Joe Mitchell Realizing Rectangles by Paper Folding.
• September 11, 1998 -- Problem Session, lead by Joe Mitchell Progress on Realizing Rectangles by Paper Folding. Notes by Saurabh Sethia, including figure.
• September 18, 1998 -- Problem Session, lead by Steven Skiena More Progress on Realizing Rectangles by Paper Folding. Notes by Pavel Sumazin.
• October 2, 1998 -- Problem Session, lead by Steven Skiena Sorting Permutations Using Editing Commands.
• October 23, 1998 -- Problem Session, lead by Estie Arkin. Optimal Crane Sorting.

1997 Sessions

• September 5, 1997 -- Problem Session, Drawing Fixed-Vertex Planar Graphs. Notes by Jim Klosowski.
• September 12, 1997 -- Problem Session, lead by Giri Narasimhan. Minimal Bounding Rectangles. Notes by Barry Cohen.
• September 26, 1997 -- Problem Session, lead by Joe Mitchell. Metric Realization of Graphs.
• October 10, 1997 -- Problem Session, lead by Steven Skiena. Frequency Block Scheduling.
• October 17, 1997 -- Problem Session, lead by Joe Mitchell. Flushing Out Enemy Forces.
• October 31, 1997 Problem Session, lead by Steven Cosares. Frequency Block Scheduling II.
• November 14, 1997 -- Problem Session, lead by Joe Mitchell. k-Fence Enclosures.
• November 21, 1997 -- Problem Session, lead by Steven Skiena. Passing Exams without Reading the Questions.

  This work became the paper Shift error detection in standardized exams (with P. Sumazin). Journal of Discrete Algorithms, 2 (2004) 313-331