Click for
details. Most recent items at top.
Time: Thursday 1 May 2003, 12:10-1:00PM (not the usual day)
Location: Burton B17 (not the usual location)
Dear Computer Science Students and Faculty,
This is an announcement for the final Computer Science Research Lunch
of the semester and year. We will listen to music created
by students (most of them seniors) in
CSC354: Seminar on Digital Sound and Music Processing.
Each student produced a 3 minute musical composition
for her final project. There will be extremely
minimal presentations on how the composition was
created, with most of the time devoted to listening to
the results. Interested attendees will be able to find
out more information when the students post their
final papers on the web.
Please join us for intellectual audio stimulation and lunch!
Lunch: We order sandwiches from the State Street Deli;
an endowment to the department covers the costs.
Please email Sonya Nikolova < snikolov@email.smith.edu>
specifying your intention to attend, and placing a lunch
order by 2 pm Wednesday.
The State Street Deli menu is on the bboard in McConnell 209
and at http://www.statestreetfruit.com/menu.html.
We always finish by 1:00PM.
Joseph O'Rourke
Time: Friday 18 Apr 2003, 12:10-1:00PM
Location: McConnell 403A (Seminar Room)
Dear Computer Science Students and Faculty,
This is an early announcement for our final session on
Conway's "Angel Problem," discussed at three previous
lunches.
Last time we launched into an analysis of Nick's Devil algorithm, only
to discover at the end of the session that the analysis could not be
correct. I am determined this time to get the analysis right.
Please join us to help sort through the intricacies!
Lunch:
We order sandwiches from the State Street Deli; an
endowment to the department covers the costs.
Please reply to Sonya Nikolova
<snikolov@email.smith.edu>
specifying
your intention to attend, and placing a lunch order. The State Street
Deli
menu is on the bboard in McConnel 209 and at
http://www.statestreetfruit.com/menu.html. We always finish by 1:00PM.
[Posted Sunday 4/13/2003]
Joseph O'Rourke
Time: Friday 4 Apr 2003, 12:10-1:00PM
Location: McConnell 403A (Seminar Room)
Dear Computer Science Students and Faculty,
We continue our exploration of
Conway's "Angel Problem," discussed at two previous
lunches, and at the Presentation of the Major.
We will start with an analysis of Nick's devilishly clever algorithm,
which we now think works if the devil can delete two squares for
each angel step. This is not a breakthrough, but there seems room
to improve the algorithm.
To find an algorithm that works for one devil square
deletion per angle step would be an achievement.
Please join us!
Lunch:
We order sandwiches from the State Street Deli; an
endowment to the department covers the costs.
Please reply to Sonya Nikolova
<snikolov@email.smith.edu>
specifying
your intention to attend, and placing a lunch order. The State Street
Deli
menu is on the bboard in McConnel 209 and at
http://www.statestreetfruit.com/menu.html. We always finish by 1:00PM.
[Posted Tuesday 4/1/2003]
Joseph O'Rourke
Time: Friday 28 Mar 2003, 12:10-1:00PM
Location: McConnell 403A (Seminar Room)
Dear Computer Science Students and Faculty,
This week we have a guest speaker, Daniel Scharstein
from Middlebury College, invited by Nick Howe,
who will speak to us on
Zen and the Art of Stereo Algorithm Evaluation.
Please join us for what is sure to be a stimulating talk!
Here is his abstract:
The problem of stereo vision has fascinated computer vision researchers
for more than 30 years. The problem can be stated quite simply: to
devise an algorithm whose input are two images of a scene from slightly
different views, and whose output is a depth map that represents the
distance to each scene point. Dozens of new stereo algorithms are being
published each year, yet the goal of matching the performance of humans,
or even that of simple mammals, remains elusive. The problem is clearly
harder than it looks (no pun intended). Which of the large number of
published methods performs best?
This talk addresses some of the tricky issues associated with stereo
algorithm evaluation. For a quantitative evaluation, it would clearly
be good to know what the correct answer - the true depth map - looks
like. But how do we get such a thing? Come to the talk to find out!
You'll also get a glimpse of the Middlebury Stereo Vision Page, see the
work of undergraduate research assistants, and hear answers to important
questions such as "Can't we use computer graphics?", "What does Zen have
to do with this?", and "Where the heck is Middlebury?"
Lunch:
We order sandwiches from the State Street Deli; an
endowment to the department covers the costs.
Please reply to Sonya Nikolova
<snikolov@email.smith.edu>
specifying
your intention to attend, and placing a lunch order. The State Street
Deli
menu is on the bboard in McConnell 209 and at
http://www.statestreetfruit.com/menu.html. We always finish by 1:00PM.
[Posted Tuesday 3/25/2003]
Joseph O'Rourke
Time: Friday 21 Feb 2003, 12:10-1:00PM
Location: McConnell 403A (Seminar Room)
Dear Computer Science Students and Faculty,
We continure our investigation of
Conway's "Angel Problem," still unsolved despite our
efforts last week :-).
The problem is an interesting infinite combinatorial game
whose resolution seems obvious, but no one has been able to
prove either a positive or negative result.
Last week we just started to understand the problem, and generate
new ideas. We will first reintroduce the problem to bring
newcomers up to speed, and then start exploring the various
algorithms proposed (so far we have the Thiebaut positive algorithm,
the Cardell randomized algorithm, and the Howe negative algorithm to
explore!).
Please join us!
Lunch:
We order sandwiches from the State Street Deli; an
endowment to the department covers the costs.
Please reply to Sonya Nikolova
<snikolov@email.smith.edu>
specifying
your intention to attend, and placing a lunch order. The State Street
Deli
menu is on the bboard in McConnel 209 and at
http://www.statestreetfruit.com/menu.html. We always finish by 1:00PM.
[Posted Tuesday 2/18/2003]
Joseph O'Rourke
Time: Friday 14 Feb 2003, 12:10-1:00PM
Location: McConnell 403A (Seminar Room)
Dear Computer Science Students and Faculty,
We resume our Computer Science Research Lunches
this coming
Friday with an introduction to and investigation of
Conway's unsolved "Angel Problem."
In a nutshell, this is the question.
Can the devil, who can remove one square per move from an
infinite chessboard, trap the angel, who can fly up to 1000 squares
per move?
It seems unlikely, but no one has been able to prove the angel
can always escape the most cunning devil.
Come help us wrestle with the forces of good and evil
with an informal group investigation of this intriguing problem.
Lunch:
We order sandwiches from the State Street Deli; an
endowment to the department covers the costs.
Please reply to Sonya Nikolova
<snikolov@email.smith.edu>
specifying
your intention to attend, and placing a lunch order. The State Street
Deli
menu is on the bboard in McConnel 209 and at
http://www.statestreetfruit.com/menu.html. We always finish by 1:00PM.
[Posted Saturday 2/8/2003]
Judy Franklin
Time: Friday 22 Nov 2002, 12:10-1:00PM
Location: McConnell 403A (Seminar Room)
Dear Computer Science Students and Faculty,
This Friday's research lunch will be devoted to a
discussion and initial organization of one or more teams
of Smith CS students to compete in a programming
contest in the spring. This contest is part of the
Eighth Annual Consortium for Computing Science in Colleges
Northeastern Conference (CCSCNE). Last year we had
a very impressive team that placed 13th out of 29 teams.
Take a look at how close the scores were at
http://www.cs.smith.edu/~jfrankli/department/ccscne02.html
where there is also a link to the problems they solved.
We will talk more about the contest and what it entails and
how teams can organize and work together.
If you are interested and would like to find out more, attend this
Friday's research lunch in McConnell 403A.
Lunch:
Lunch: Please reply to Sonya Nikolova
<snikolov@email.smith.edu>
specifying
your intention to attend, and placing a lunch order. The State Street
Deli
menu is on the bboard in McConnel 209 and at
http://www.statestreetfruit.com/menu.html. We always finish by 1:00PM.
[Posted Monday 11/18/2002]
Joseph O'Rourke
Time: Friday 8 Nov 2002, 12:10-1:00PM
Location: McConnell 403A (Seminar Room)
Dear Computer Science Students and Faculty,
We now resume the lunch research meetings, with two scheduled
for November: this Friday the 8th, and Friday the 22nd.
This week I will present work done in the past year in collaboration with
Becky Alexander and Heather Dyson, detailing all the convex
polyhedra that can be folded from a square piece of paper.
There are an infinite variety of such polyhedra, but they fall
into four "rings," and nine different combinatorial structures.
Lunch:
Please reply to
Sonya Nikolova <snikolov@email.smith.edu>
specifying your intention to attend,
and placing a lunch order. The State Street Deli menu is
on the bboard in McConnel 209 and at http://www.statestreetfruit.com/menu.html.
We always finish by 1:00PM.
[Posted Monday 11/04/2002]
Joseph O'Rourke
Time: Friday 11 Oct 2002, 12:10-1:00PM
Location: McConnell 403A (Seminar Room)
Dear Computer Science Students and Faculty,
This Friday
Dominique will present some of his research from the past
year and a half on an intelligent memory circuit, and discuss
its application to bioinformatics.
The "intelligent memory circuit" represents a novel new architecture
for the structure of computers.
This will be our last Friday research lunch for about a month,
so come and join us!
Lunch:
Please reply to
Sonya Nikolova <snikolov@email.smith.edu>
specifying your intention to attend,
and placing a lunch order. The State Street Deli menu is
on the bboard in McConnel 209 and at http://www.statestreetfruit.com/menu.html.
We always finish by 1:00PM.
[Posted Monday 10/07/2002]
Joseph O'Rourke
Time: Friday 4 Oct 2002, 12:10-1:00PM
Location: McConnell 403A (Seminar Room)
Dear Computer Science Students and Faculty,
This week we will meet on the 4th floor of McConnell (please note
the change in venue!) for a presentation by
Lindsay Wishnick, Class of 2003, on Microsoft .NET.
She worked this past summer at
the Federal Reserve and prepared a
powerpoint presentation on the topic for them.
The Microsoft web site explains that
"Microsoft .NET is a set of software technologies
designed to connect your world of information, people, systems, and devices."
Much of the literature on it is equally vague, so the details Lindsay
will provide will be welcome indeed.
Lunch:
Please reply to
Sonya Nikolova <snikolov@email.smith.edu>
specifying your intention to attend,
and placing a lunch order. The State Street Deli menu is
on the bboard in McConnel 209 and at http://www.statestreetfruit.com/menu.html.
We always finish by 1:00PM.
[Posted Monday 9/30/2002]
Joseph O'Rourke
Time: Friday 27 Sep 2002, 12:10-1:00PM
Location: McConnell B15 (in the basement)
Dear Computer Science Students and Faculty,
We will continue our
exploration of Python at
this Friday's
"Computer Science Research Lunch"
(CSRL).
This week will will explore using Python to perform a variety of
text-processing tasks: creating HTML, converting HTML to text,
sending email, and so on.
We will again meet in
McConnell B15, so we can project from a workstation and code interactively.
Attendance at last week's introduction is not essential.
Looking ahead, we hope to have Lindsay Wishnick explain .NET on
October 4th, and Dominique Thiebaut discuss his current research on
October 11th.
Lunch:
Please reply to
Sonya Nikolova <snikolov@email.smith.edu>
specifying your intention to attend,
and placing a lunch order. The State Street Deli menu is
on the bboard in McConnel 209 and at http://www.statestreetfruit.com/menu.html.
There is a Physics class in B15 just prior to our lunch, so
we will not be able to start early.
We always finish by 1:00PM.
[Posted Monday 9/23/2002]
Joseph O'Rourke
Time: Friday 20 Sep 2002, 12:10-1:00PM
Location: McConnell B15 (in the basement)
Dear Computer Science Students and Faculty,
We will resume our nearly weekly series of "Computer Science Research Lunches"
(CSRL)
this Friday, with an exploration of a relatively new programming language
named Python.
Python is an interpreted, interactive, object-oriented programming language.
It is gaining many adherents, taking over some programming tasks formerly
coded in Perl or in Java. I do not know the language well myself, so this
will be very exploratory. My intention is that this will be the first
of several lunches devoted to Python.
We will meet in
McConnell B15, so we can project from a workstation and code interactively.
For those new to our CSRLs, they are informal lunches open to all interested,
in which we explore interesting topics in Computer Science that fall outside
of the classroom curriculum.
Lunch:
Please reply to
Sonya Nikolova <snikolov@email.smith.edu>
specifying your intention to attend,
and placing a lunch order. The State Street Deli menu is
on the bboard in McConnel 209 and at
STMenu.
There is a Physics class in B15 just prior to our lunch, so
we will not be able to start early.
We always finish by 1:00PM.
[Posted Monday 9/16/2002]
Judy Franklin
The Last Computer Science Research Lunch of the season will
be held this coming Monday,
April 22
McConnell B15
12:10
Stan Sclaroff, from the computer science department at Boston
University will speak on Automatic
Shape-based Image Retrieval.
Please send State Street Deli lunch orders to mdonoso@cs.smith.edu by 2:30
Thursday.
Dr. Sclaroff's abstract is below:
Automatic Shape-based Image Retrieval
Stan Sclaroff
Image and Video Computing Group
Computer Science Department
Boston University
Retrieval by shape is considered to be one of the more difficult aspects of
content-based image database search. A major part of the problem is that many
techniques assume that shapes have already been segmented from the background,
or that a human operator has encircled the object via an active contour. Such
assumptions are unworkable in applications where automatic object detection and
indexing are required (e.g., the world wide web).
In this talk, I will describe a region-based approach that segments deformable
shapes from images automatically. Parametric shape templates are used to group
image regions into consistent configurations. The templates are acquired as a
precomputation, given a training set of images. Once trained, the system
autonomously segments deformed shapes from the background while not merging
them with adjacent objects or shadows. The automatic system includes two
stages: over-segmentation using a traditional region segmentation algorithm,
followed by shape-based evaluation of various region grouping hypotheses to
find an optimal partition of the region adjacency graph. The recovered shape
models can be used directly in image retrieval and object recognition.
Experiments with biomedical images (blood cell micrographs), as well as images
from the world wide web will be shown.
[Posted Tuesday 4/16/2002]
Judy Franklin
The next Computer Science
Research Lunch will be held this Friday, April 12 (and there will be no lunch
next week). We have a guest speaker, David G. Novik, from the University of
Texas El Paso. Please see his title, abstract, and bio below.
Once again, we will meet in McConnell B15 in order to use the projector.
Please send lunch orders to mdonoso@cs.smith.edu by 1:30 Thursday April
11.
Engineering User Interfaces for Safety-Critical Systems
David G. Novick
Department of Computer Science
The University of Texas at El Paso
This talk looks at development methods for human-computer interaction for
safety-critical systems, with particular focus on commercial airliner cockpits.
I argue that user interfaces, operating procedures and their documentation are
functionally equivalent parts of the interface, broadly considered, and present
a set of techniques and tools that can help developers assure the integrity of
human-computer interaction safety-critical settings. Methods for early
evaluation of operating procedures and documentation include the cognitive
walkthrough for operating procedures and the use of "low-tech"
simulation. Correctness in design and implementation can also be helped by
using a more formal model of acts and actions, and this model can be embodied
in tools for creating procedures and their documention.
---
David G. Novick earned his J.D. at Harvard University in 1977 and his Ph.D.in
Computer and Information Science at the University of Oregon in 1988. He is
professor and chair of Computer Science at the University of Texas at El Paso.
Previously, he was on the faculty of the Department of Computer Science and
Engineering at the Oregon Graduate Institute and then Director of Research at
the European Institute of Cognitive Sciences and Engineering. His research
focuses on interactive systems, and especially development methods for
interfaces and their documentation. Related interests include technologically
mediated communication and computational models of dialogue. He served as
General Co-chair of the 2000 ACM Conference on Universal Usability, organized
ACM SIGCHI's series of events in Natural Language Interfaces, and serves on the
program committee for the 2002 ACM SIGDOC conference.
[Posted Monday 4/8/2002]
Judy A. Franklin
Our next Computer Science
Research Lunch is Monday April 8
in McConnell B15
featuring Egle Karalyte who did research with Merrie Bergmann last semester.
Please send lunch orders to mdonoso@cs.smith.edu by 1:30 this Friday.
Creating Dynamic Web Sites Using PHP and MySQL
In order to create a powerful and dynamic web site, it is not just enough to
know HTML or Javascript. Nowadays, new technologies are emerging, which enable
web developers to create database-driven web sites where information is
dynamically embedded into html code according to various specifications. One of
the newest and most powerful technologies is the PHP scripting language that is
often used to communicate with the MYSQL database system. MySQL is one of the
relational database management systems (RDBMS). This type of database is often
used for the ecommerce web sites. MySQL uses SQL (Structured Query Language) to
communicate with the data. SQL is a standard database language for all modern
databases. It is an interface between the user and the database it lets you
create tables, insert, delete, and modify data. In my presentation I will
introduce these technologies and show how the information is inputted into the
database and how it is shown on the web sites.
[Posted Wednesday 4/3/2002]
Judy Franklin
On Monday April 1, Geetika Tewari will present her thesis
work for the Computer Science Research Lunch.
McConnell 403A
Please email State Street Deli lunch order to
mdonoso@cs.smith.edu by 1:30 Friday.
Here is the abstract:
We examine the problem of partitioning orthogonal polygons into fat rectangles
that arises in the photolithography step of VLSI design. VLSI masks are etched
by electron beams of some fixed minimum width. Complex shapes can only be
masked without unnecessary overexposure if they can be partitioned into
rectangles all of which are wider than this minimum width. Thus it is of some
interest to develop an algorithm that can find an optimal partition of a
polygon into rectangles, in the sense of maximizing the minimum width of any
rectangle in the partition. We approach the problem by characterizing the
complexity of polygon partitions by the types of cuts involved. We will present
a polynomial-time algorithm, and its implementation results for solving the
problem using "vertex cuts," cuts emanating from polygon vertices. We
then proceed to show several short results that lead to a bound on the maximum
number of parallel "boundary cuts," cuts anchored to the polygon
boundary, in an optimal partition.
[Posted Wednesday 3/27/2002]
Ileana Streinu
Computer Science Research Lunch will resume the very Monday
after Spring Break, Monday March 25th, at 12:10 in room McConnell 403A. Katina
Tiggas will talk about programming the AIBO robot. Please send lunch orders to
mdonoso@cs.smith.edu by 1:30 *this* Friday March 15th. And then remember to
come Monday March 25th. The abstract is below:
Programming the AIBO robot - an introduction
Presenter: Katina Tiggas
The Sony AIBO robotic dog is a programmable robot with many degrees of freedom,
a variety of sensors and quite sophisticated programming capabilities.
I will start with an introduction to the robot's capabilities and an overview
on how we program it using actions and behaviors. Then I will talk about my
work on testing AIBO's capabilities and limits, such as the range of its
"eyesight" or whether it really could walk in a straight line.
Our goal is to develop a program that consists of two dog-like behaviors:
hunger and playing. The behavior is controlled by the percent of remaining
battery power. If the battery power is below 50%, the dog is hungry. In this
case the dog will search for the battery charger and go toward it. It is not
clear that we will be able to make it actually plug itself in, but we intend to
study whether such motions are possible. To detect where the charger is, we use
AIBO's sensitivity to the color pink, and possible some "friendly
guidance" through her touch sensors. We can cover the battery charger in
pink to entice AIBO towards it. We are in the process of finding the best
search algorithm that covers the work space. When the battery power is above
50%, AIBO plays. She will randomly choose between singing, sleeping, and
dancing.
[Posted Wednesday 3/13/2002]
Judy Franklin
The next Computer Science
Research Lunch will be Monday March 11 at 12:10 in room McConnell 403a. Vicky
Manfredi will present her thesis work.
Please email mdonoso@cs.smith.edu with your lunch order by 1:30 Friday. A menu
for State Street Deli is on the bulletin board in McConnell 209.
-=-=-=-=Vicky's Abstract-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Non-linear Algorithms for Reinforcement Learning
The work we would like to present is from an honors thesis being done in
Computer Science. The faculty advisor is Judy Franklin.
We adapted two machine learning algorithms, temporal-difference learning and
Sarsa, to be non-linear. Temporal-difference learning is used for predicting
how good an action is in some some state. Sarsa, conversely, is used for
generating actions based on the temporal-difference prediction. We then used
these algorithms to predict and select notes in a musical sequence. We observed
that both the linear and nonlinear temporal-difference algorithms combined with
function approximation can learn to predict on a given note whether the future
looks good or bad; that is, whether the context of the note is good or bad,
given certain constraints. We found that the nonlinear algorithms can learn to
predict more difficult constraint problems than can the linear. We determined
that using as input to the algorithms a history of the notes being played
improved the correctness of the nonlinear prediction. Finally, preliminary
results show that with linear Sarsa, the notes chosen to be played correspond
to the prediction value of the note as given by the temporal- difference
learning algorithm. Current experiments involve exploring nonlinear Sarsa.
[Posted Tuesday 3/5/2002]
Ileana Streinu
Dear CS students and faculty -
On Monday March 4 we resume the weekly CS luncheons with a series of
presentations, done by Computer Science students about their research projects.
We meet in McConnell 403A.
The first speaker is Elif Tosun, who will talk about her honors thesis work.
Future speakers include Vicky Manfredi (Monday March 11, thesis work), Katina
Tiggas (independent study, AIBO robot) and others TBA.
Please send the luncheon order to mdonoso@cs.smith.edu, by 1:30 on Friday,
March 1st.
Here's Elif's abstract:
=======================================================================
Given visibility information at n positions of a hemispherical camera, our goal
is to reconstruct the absolute coordinates of the camera locations and
positions of image features when the images were taken. This information will
then be used the reconstruct a model of the environment.
We assume that the orientation of the camera relative to the absolute frame of
reference is known at each location, as well as approximate values for unknown
positions. The visibility information is given as a set of slopes of lines
going through camera positions and some image features in the surrounding
environment.
We worked on understanding the general problem, isolating the
geometric/combinatorial aspects, exploring it in two and three dimensions,
isolating several feasible subproblems and giving algorithmic solutions for
them.
[Posted Thursday 2/28/2002]
Judy Franklin
Programming Contest and Research Lunches Spring 2002
On Monday February 18, the CS dept. is holding a lunch for students interested
in continuing the research lunches this semester, on Mondays, as well as to
discuss Smith's participation in a new (for us) programming contest, sponsored
by the Consortium for Computing in Small Colleges, Northeast. The contest will
take place at the Seventh Annual Consortium for Computing in Small Colleges
Northeastern Conference April 19-20. The contest is the morning of Friday April
19 at Worcester State College. The awards are given at a banquet Friday night.
The conference URL is http://www.ccscne.org/2002/. The deadline for contest
entry is March 1. Come to the lunch even if you aren't interested in the
contest as we will talk about the research lunch plans for the semester.
Meeting Room: McConnell 403A (the usual place)
As usual, we will have lunch from the State Street Deli. There is a menu posted
on the bulletin board in McConnell 209. Please DO NOT REPLY TO THIS MESSAGE.
Send lunch requests to 111c@cs.smith.edu by 3pm THURSDAY 2/14 and have a Happy
Valentine's Day.
[Posted Monday 2/11/2002]
Joseph O'Rourke
Time: Friday 30 Nov 01, 12:10-1:00PM
Location: McConnell 403A (Seminar Room)
Dear Computer Science Students and Faculty,
This week we
have a guest presentation by Bjo:rn Gehlsen from the University
of Hamburg, who is here visiting
Bernd Page. He will talk about Genetic Algorithms: a Tool for Distributed
Simulation Optimization. Here is his abstract:
Genetic Algorithms (GA) provide a general process model for
heuristic optimization by simulating the principles of biological evolution.
They can be used in various areas of application by specializing its'
components according to the application's needs. Following an introduction to
GA the talk will show the application of GA in the field of simulation
optimization, where no closed form of the problem and no further analytical
information can be used to guide the search for optimal solutions. As the
arising problems in this area are very load intensive, tasks are distributed
across a network to gain significant speedup.
Lunch: Please reply to mdonoso@cs.smith.edu specifying your intention
to attend, and placing a lunch order. The State Street Deli menu is on the
bboard in McConnel 209 and at http://www.statestreetfruit.com/menu.html. There
is no class in McC403A prior to our lunch, so we should be able to start to
gather around noon. We always finish by 1:00PM.
[Posted Tuesday 12/4/2001]
Joseph O'Rourke
Time: Friday 30 Nov 01, 12:10-1:00PM
Location: McConnell B15 (in the basement!)
Dear Computer Science Students and Faculty,
We will continue the interactive code development of
lunch.pl, the Perl program to process lunch orders emailed to Melody.
Last time (2 Nov) we had progressed to the point of having a correct parsing of
the "From:" and "Subject:" lines of simulated email, with a
record of the transactions deposited in a LOGFILE. This time we should aim to
accomplish four goals: (1) Have the code recognize "Re: CSRL" in the
Subject line; (2) Install the Perl program in the correct directory on the
system, with the correct permissions; (3) Arrange that all email to Melody gets
examined by our code; (4) Test with real email. Again we will meet in McConnell
B15, so we can project the code from a workstation.
Lunch: Please reply to mdonoso@cs.smith.edu specifying your intention
to attend, and placing a lunch order. The State Street Deli menu is on the
bboard in McConnel 209. There is a Physics class in B15 just prior to our
lunch, so we will not be able to start early. We always finish by 1:00PM.
[Posted Monday 11/26/2001]
Joseph O'Rourke
Time: Friday 16 Nov 01, 12:10-1:00PM
Location: McConnell 403A (Seminar Room)
Dear Computer Science Students and Faculty,
This week we have a guest speaker, Iris Bahar from Brown University. She
will talk about designing machine architectures to minimize power consumption.
The main idea is to dynamically set microportions of the processor into
low-power mode when monitoring indicates they are not being utilized. Of
course, one cannot sacrifice high speed performace in order to achieve lower
power dissipation, which is the crux of the matter about which she will speak.
Lunch: Please reply to mdonoso@cs.smith.edu specifying your intention
to attend, and placing a lunch order. The State Street Deli menu is on the
bboard in McConnel 209, and online at
http://www.statestreetfruit.com/menu.html. If the food arrives on time, we will
start gathering shortly after 12:00, with many arriving after their classes let
out at 12:10. We always finish by 1:00PM.
[Posted Monday 11/12/2001]
Judy Franklin
Using RTcmix to manipulate sound and
make music
Veronica Morales
and Judy Franklin
Time: Friday 9 Nov 01, 12:10-1:00PM
Location: McConnell 403A (Seminar Room)
CMIX is a package of sound-processing, synthesizing, modification and mixing
programs that can be used to manipulate pre-recorded sound or create any sound
and write the result to an audio file. RTcmix adds real-time capabilities to
CMIX, and it also enables it to read sound data through TCP sockets. RTcmix is
written in C and C++ and takes advantage of the object-oriented paradigm. With
RTcmix, output can be sent directly to speakers, unlike CMIX which needed the
output to be saved to a sound file first. It can do this because it
incorporates a scheduler that dynamically calls the RTcmix instruments. Here,
an instrument is any function or class that manipulates sound. We will describe
RTCmix in more detail, go over basic ways to manipulate sound (amplitude
modulation and frequency modulation), and demonstrate several of the basic
RTcmix instruments. RTcmix is different from almost every other computer music
software package in that users can create their own instruments and so can
manipulate sound programmatically. (Nearly every other package is accessed
either with a GUI or by using scripts only). We will describe two or three
accompaniment and pitch translation instruments we worked on this past summer
when Veronica was on a Schultz Fellowship and we will demonstrate them as well.
Lunch: Please reply to mdonoso@cs.smith.edu by noon Thursday specifying
your intention to attend, and placing a lunch order. The State Street Deli menu
is on the bboard in McConnel 209. If the food arrives on time, we will start
gathering shortly after 12:00, with many arriving after their classes let out
at 12:10. We always finish by 1:00PM.
[Posted Wednesday 11/7/2001]
Joseph O'Rourke
Time: Friday 2 Nov 01, 12:10-1:00PM
Location: McConnell B15 (in the basement!)
Dear Computer Science Students and Faculty,
We will discuss the programming language Perl, which is
a useful tool in a Unix environment, especially for text processing. In
particular, we will write code to process lunch order email messages (Melody's
idea). In order to run code during lunch, we are going to meet in McConnell
B15, where there is a nice workstation and projector. We decided we could
sacrifice our pleasant, informal environment to gain ease of programming
access, for one week at least. Our plan is to look at the language Python later
in the semester, perhaps for the same task.
Lunch: Please reply to mdonoso@cs.smith.edu specifying your intention
to attend, and placing a lunch order. The State Street Deli menu is on the
bboard in McConnel 209. There is a Physics class in B15 just prior to our
lunch, so we will not be able to start early this week. We always finish by
1:00PM.
[Posted Monday 10/29/2001]
Joseph O'Rourke
Time: Friday 26 Oct 01, 12:10-1:00PM
Location: McConnell 403A (Seminar Room)
Dear Computer Science Students and Faculty,
The association of computers with binary logic seems
essential, but in fact a case can be made that digital computer hardware should
be based on base-3 numbers rather than on binary numbers. The base-3 equivalent
of a bit is a trit. Suzzane Gallagher will help describe the advantages
of trits over bits, not only in computer hardware, but in the placement of tabs
on file-cabinet folders, among other applications.
Lunch: Please reply to mdonoso@cs.smith.edu specifying your intention
to attend, and placing a lunch order. The State Street Deli menu is on the
bboard in McConnel 209. If the food arrives on time, we will start gathering
shortly after 12:00, with many arriving after their classes let out at 12:10.
We always finish by 1:00PM.
[Posted Monday 10/22/2001]
Bar-Magnet Polyhedra III
Joseph O'Rourke
Time: Friday 12 Oct 01, 12:10-1:00PM
Location: McConnell 403A (Seminar Room)
Dear Computer Science Students and Faculty,
Last Friday, the day before Fall
Break, a small group of us made a bit of progress on the problem, as I reported
in email Friday night: We proved that any tree can be directed to be balanced.
The challenge before us is to extend this positive result to a wider class of
planar graphs. Perhaps planar triangulations would be a good place to start.
There are various ways to use induction on such graphs (e.g., edge
contractions), but at the moment I don't see how they will yield a proof.
Nevertheless, let's spend one more week exploring this topic.
Lunch: Please reply to mdonoso@cs.smith.edu specifying your intention
to attend, and placing a lunch order. The State Street Deli menu is on the
bboard in McConnel 209. The class that used to meet just prior to our lunch in
that seminar room has moved, so we should be able to start gathering shortly
after 12:00, with many arriving after their classes let out at 12:10. We finish
by 1:00PM in any case.
[Posted Wednesday 10/10/2001]
Bar-Magnet Polyhedra: II
Joseph O'Rourke
Time: Friday 5 Oct 01, 12:10-1:00PM
Location: McConnell 403A (Seminar Room)
Dear Computer Science Students and Faculty,
We had an unusually large group at
our CS Research Lunch last Friday, despite the esoteric topic. I recommend we
continue with the topic at least another week. Let me first summarize our
progress.
We explored bar-magnet polyhedral graphs, and had three accomplishments:
- We caught up with the
frontier of knowledge here by reviewing the three known, partial results
on alternating assignments.
- We raised and answered a
question: Is it possible that a polyhedral graph could have the property
that, some vertex MUST have all incident poles the same? The answer is NO.
- We formulated a new question:
Might it be that every polyhedral graph's edges can be assigned a
direction so that each vertex is balanced, in the sense that its
number of incoming and outgoing edges differ by at most one? (This is
weaker than alternating.)
A few notes on each three:
1. These partial results establish not every polyhedral graph is
alternating, and that many classes are. It remains to characterize those which
are, and are not. We did not find this an attractive :-) problem.
2. Our answer NO was misunderstood by at least me, and perhaps others. Here
is a more careful proof than was explicated at lunch. Suppose a vertex v has
all incoming edges, in contradiction to what we claim. Look at three
consecutive vertices to which it is adjacent, x,y,z, consecutive in the cycle
(the "link") around v. Consider flipping the vy edge direction, which
would break the "badness" of v. This could only create badness at y
if the edges to x and z are both incoming to y: x to y and z to y (for then a
flip of vy would increase the incoming edges to y). But in this case look at x.
It has an outgoing edge to y. So flip the vx edge. This breaks the badness at
v, and cannot create total badness at x, because vx goes into x, and xy goes
out.
3. Let's call these balanced, directed graphs Gallagher Graphs :-). I think
these merit study. One route is to examine the conditions under which local
flips of edges improves the balance. The question then becomes, could we ever
have a situation where no local balance improvement is possible, despite an
imbalance? Label a node +k if it has k more incoming than outgoing edges, -k if
k more outgoing than incoming, and = if its in/out edges are balanced exactly.
Suzanne's question is whether every node can always get a label in {+1,-1,=}.
Suppose we have the situation
+2 <----- =
Then
we could flip that edge to produce
+1 ------> +1
So
if there is an intransigent unbalanced node (the +2 above), it must have
outgoing arcs, or incoming arcs from +1's or higher; otherwise the arcs could
be reversed, improving balance. It seems we could study the conditions that
must hold if (a) there is an imbalanced node, and (b) every edge flip intended
to reduce the imbalance in fact creates more imbalance. Maybe this can't
happen?
I
propose we review the above as needed, and work on proving or disproving the
hypothesis that every polyhedral graph can be directed so that all its vertices
are balanced.
Lunch:
Please reply to mdonoso@cs.smith.edu specifying your intention to attend, and placing
a lunch order. The State Street Deli menu is on the bboard in McConnel 209. The
class that used to meet just prior to our lunch in that seminar room has moved,
so we should be able to start gathering shortly after 12:00, with many arriving
after their classes let out at 12:10. We finish by 1:00PM in any case.
[Posted Monday 10/1/2001]
Bar-Magnet
Polyhedra: I
Joseph
O'Rourke
Time:
Friday 28 Sep 01, 12:10-1:00PM
Location: McConnell 403A (Seminar Room)
Dear
Computer Science Students and Faculty,
Last
week we reviewed a plethora of possible topics, and interest was at least
implicitly shown in many of them by nods around the table. The most explicit
support came from Judy, who thought the Bar-Magnet Polyhedra problem
was "attractive." It was not until she mentioned to me later that
this was a joke that I saw the pun. :-) Nevertheless, partly because many of
the other topics require advance work, I would like to start this Friday by
exploring this unsolved bar-magnet problem. I have a formal description in The Opens Problem
Project web pages, but informally it is to characterize those polyhedra one
can build out of bar magnets without placing too many like poles at a vertex
(which makes for instability). This time I will not forget to bring my models.
I think there are interesting variations possible aside from the pure
graph-theory formulation at the above link, and it would be worth us exploring
the question for one or two weeks. I should mention that although this problem
is unsolved, it is not necessarily difficult--rather it is new and therefore
relatively unexplored.
Lunch:
Please reply to mdonoso@cs.smith.edu specifying your intention to
attend, and a lunch order if desired. [The lunch menu is pinned to the bulletin
board in McConnell 209.] We will gather about 12:10 after the previous class
lets out; hopefully our lunch will be delivered more promptly this week. End by
1:00PM, promise.
[Posted Tuesday 9/25/2001]
Joseph
O'Rourke
Time:
Friday 21 Sep 01, 12:10-1:00PM
Location: McConnell 403A (Seminar Room)
Dear
Computer Science Students and Faculty,
We
are now ready to call for our first Computer Science Research Lunch meeting of the
semester, for this coming Friday. The agenda is the same as last Friday's
canceled meeting: to create a list of topics for the semester. See the previous
announcement (on the department's "Announcements" web page) for the
philosophy behind these meetings. Let me just reemphasize that they are
intended to be fun, informative, and not over anyone's head.
Lunch:
Please reply to mdonoso@cs.smith.edu specifying your intention to
attend. Please note: Melody is going to take
over the management of the lunch orders. For those of you who intended to
attend last week, you can just say "same order," as we still have a
record of your request. However, we will not reorder a lunch unless you
recommit.
There
is a class immediately prior to the lunch in the seminar room, so we'll never
be able to get in there before 12:10. We always finish by 1:00PM. It's all too
short, but we manage to have interesting discussions.
[Posted Wednesday 9/19/2001]
Joseph
O'Rourke
Time:
Friday 14 Sep 01, 12:10-1:00PM CANCELLED ; will be held the 21st instead.
Location: McConnell 403A (Seminar Room)
Dear
Computer Science Students and Faculty,
For
two years now the department has held an informal "Computer Science
Research Lunch" every Friday. We order lunch from State Street Deli (using
funds provided by an alumna) and discuss some topic in computer science. The
topics have ranged widely (see the "Announcements" link off the CS
Department homepage), but usually have a research-oriented flavor. We have
either explored some hot topic on the frontier of the field (quantum computing,
everlasting security, quantum teleportation, protein folding), or we have
worked on trying to solve some open problem via interactive research. It is
intended to be a low-pressure environment, informative, and fun. Attendance is
of course entirely voluntary, and is by no means restricted to computer science
majors--anyone interested is welcome. We typically have 8-10 students in
attendance.
This
Friday we will primarily discuss which topics we might explore this semester.
I'll offer up a plate of possibilities, and take suggestions. Whether we
actually do anything substantive beyond that remains to be seen.
Lunch:
Please reply to gtewari@cs.smith.edu specifying your intention to attend. We'll
order lunch from State Street Deli, whose menu is pinned to the bulletin board
in McConnell 209; a generic sandwich is also possible. Orders will be due
Thursday afternoon at 2:30PM so that we can FAX in the order by the end of the
day. (Please note that if you say you'll attend but do not, we end up ordering
lunch for you and wasting a portion of our endowment.)
There
is a class immediately prior to the lunch in the seminar room, so we'll never
be able to get in there before 12:10. We always finish by 1:00PM.
[Posted Monday 9/10/2001]
Geetika
Tewari
Time:
Friday 27 Apr 01, 12:10-1:00PM
Location: McConnell 403A (Seminar Room)
Dear
Computer Science Students and Faculty,
This
is the first announcement for this Friday's Computer Science Research Lunch.
The details for the lunch, its location, etc. are below. Here are Joe's
comments:
This
will be our last CSRL lunch of the semester, as I will be away on May 4th.
After three sessions on exploring papers on protein folding, I feel it is time
for us to do some original, interactive research. I thought of a perhaps new
locked-chains problem inspired by our investigations into protein folding, and
I would like to work on that. I will bring a bag of straws (to represent the
backbone of a protein), and scissors and tape, and we'll start a hands-on
exploration.
Lunch:
Please reply to gtewari@cs.smith.edu specifying your intention to attend. We'll
order lunch from State Street Deli, whose menu is pinned to the bulletin board
in McConnell 209; a generic sandwich is also possible. Orders will be due
Thursday afternoon at 2:30PM.
[Posted Saturday 4/21/2001]
Geetika
Tewari
Time:
Friday 20 Apr 01, 12:10-1:00PM
Location: McConnell 403A (Seminar Room)
Dear
Computer Science Students and Faculty,
This
is the first announcement for this Friday's Computer Science Research Lunch.
The details for the lunch, its location, etc. are below. Here are Joe's
comments:
For
our penulimate meeting of the semester, I would like to return to one aspect of
the "probabilistic road map" (PRM) algorithm that we did not explore:
How to generate random points in the configuration space of the protein molecule
so that the bottlenecks in the space (the thin channels that must be threaded
for the protein to fold) receive sufficiently many points. As we observed
before, it would not suffice to generate the points randomly, for then their
density would be proportional to the volume, and so would miss thin structures.
I found three papers on this topic, all with Lydia Kavraki and her (former
advisor) Jean-Claude Latombe of Stanford University as coauthors. I can't
promise to read all three, but I'll browse enough to have something to report
on this crucial technical topic. Also I promise to review the PRM algorithm in
sufficient detail for newcomers to follow.
Lunch:
Please reply to gtewari@cs.smith.edu specifying your intention to attend. We'll
order lunch from State Street Deli, whose menu is pinned to the bulletin board
in McConnell 209; a generic sandwich is also possible. Orders will be due
Thursday afternoon at 2:30PM.
[Posted Monday 4/16/2001]
Geetika
Tewari
Time:
Friday 13 Apr 01, 12:10-1:00PM
Location: McConnell 403A (Seminar Room)
Dear
Computer Science Students and Faculty,
This
is the first announcement for this Friday's Computer Science Research Lunch.
The details for the lunch, its location, etc. are below. Here are Joe's comments:
I
see two directions to proceed after our discussion last week: backwards in time
to other research on aspects of protein folding and dynamics, or sideways in
time :-) into the interesting tangent of generating random points in
configuration space. It makes sense to pursue the former first. Unfortunately,
doing this well requires serious library research I don't have the time to do
now. I have found and read one paper on polymer dynamics using cellular
automata and Monte Carlo simulations. I will report on this work by Yaneer
Bar-Yam, in his book Dynamics of Complex Systems. Several other
papers I'd like to read might take more time to retrieve, so I don't want to
promise anything beyond what I have in hand at the moment.
Lunch:
Please reply to gtewari@cs.smith.edu specifying your intention to attend. We'll
order lunch from State Street Deli, whose menu is pinned to the bulletin board
in McConnell 209; a generic sandwich is also possible. Orders will be due
Thursday afternoon at 2:30PM.
[Posted Monday 4/9/2001]
Joseph
O'Rourke
Here
are Joe's comments:
We
will start exploring protein folding, via a paper I recently ran across
entitled "Using Motion Planning to Study Protein Folding Pathways."
[URL: http://citeseer.nj.nec.com/song00using.html.] Their abstract claims that
their "framework enables one to easily and efficiently compute folding
pathways from any denatured starting state to the native fold." I have now
read the paper, and I find it very interesting