Next Talk: Dec. 2nd, MC13, 15:30 - 16:30

From Sam Loyd to Laszlo Fejes Toth:
The fifteen puzzle and discrete motion planning
Janos Pach, City College, CUNY and Renyi Institute, NYU

Abstract:
We discuss a variety of discrete motion planning questions that can be regarded as far-reaching generalizations of the fifteen puzzle. For instance, given an initial position of a system of n congruent circular or square modules in the plane, is it possible to transform it into a prescribed target position, obeying certain natural motion rules? If the answer is yes, what is the smallest number of steps sufficient for completing this task? We survey some recent developments in this field, including the discovery of unexpected connections between questions of this type and old density problems for disk packings, due to Laszlo Fejes Toth (1915-2005).

  
   
 
         

General Information

The SOCS colloquium is a weekly lecture series organized by the School of Computer Science at McGill University. The lectures are held during Fall and Winter semesters on Fridays from 15:30 to 17:00 in McConnell room 13 (1st floor, close to the elevators). Every week, an invited speaker presents interesting research in some area of computer science. See the schedule for more details and abstracts of upcoming talks.

But the colloquium is not only a source of scientific inspiration, it is also a social event. Following the talk, snacks and drinks are served in the SOCS lounge, encouraging the attendees to continue questions and discussions on the talk in a more relaxed atmosphere. The intention is to encourage opportunities for networking among professors and post-docs, allows graduate (and undergraduate!) students to meet their professors in a more relaxed setting, and create a SOCS team spirit among the entire department.

Mailing List

If you want to receive notifications of upcoming seminars on a regular basis, you can subscribe to the SOCS colloquium mailing list. To do so, send an email to majordomo@cs.mcgill.ca with the following body "subscribe socs-colloquium".

Attendance for Master Students

1st year Computer Science master students are to attend the colloquium regularily. In order to complete the COMP-601 Reading Course, a student must have been to at least 10 colloquium talks (checked by means of an attendance list).

Miscellaneous

If you are looking for a higher quality image of the SOCS colloquium logo, click here.
McGill | SOCS Last modified: 12/1/05, Jörg Kienzle