vote for next paper (Dec 2 meeting)
Constantin Berzan
Our last meeting of the semester will be on December 2, at 11:30 am in Hallgan.
Please vote for the paper you would like to read:
http://www.doodle.com/ifqvd256pcu8qb2d
I've added a new paper called "Building Watson: An Overview of the
DeepQA Project". As usual, if you have more suggestions, I'd be happy
to add them. You can find all the abstracts below.
Happy Thanksgiving!
-Constantin
==============================================================================
Proof of a Program: Find [17p]
Hoare; 1989
Abstract:
A proof is given of the correctness of the algorithm Find. First, an
informal description is given of the purpose of the program and the
method used. A systematic technique is described for constructing the
program proof during the process of coding it, in such a way as to
prevent the intrusion of logical errors. The proof of termination is
treated as a separate exercise. Finally, some conclusions relating to
general programming methodology are drawn.
http://portal.acm.org/citation.cfm?id=63445 (website of the book in
which the essay is contained)
==============================================================================
Convex partitions with 2-edge connected dual graphs [16p]
Al-Jubeh, Hoffmann, Ishaque, Souvaine, Tóth (Tufts folks!); 2009
Abstract:
It is shown that for every finite set of disjoint convex polygonal
obstacles in the plane, with a total of <em>n</em> vertices, the free
space around the obstacles can be partitioned into open convex cells
whose dual graph (defined below) is 2-edge connected. Intuitively,
every edge of the dual graph corresponds to a pair of adjacent cells
that are both incident to the same vertex.
Aichholzer et al. recently conjectured that given an even number of
line-segment obstacles, one can construct a convex partition by
successively extending the segments along their supporting lines such
that the dual graph is the union of two edge-disjoint spanning trees.
Here we present a counterexamples to this conjecture, with n disjoint
line segments for any n >= 15, such that the dual graph of any convex
partition constructed by this method has a <em>bridge</em> edge, and
thus the dual graph cannot be partitioned into two spanning trees.
http://www.eecs.tufts.edu/~mishaq01/JOCO-2010.pdf
==============================================================================
Plan 9 from Bell Labs [9p]
Pike, Presotto, Thompson, Trickey; 1995
Abstract:
Plan 9 is a distributed computing environment. It is assembled from
separate machines acting as CPU servers, file servers, and terminals.
The pieces are connected by a single file-oriented protocol and local
name space operations. By building the system from distinct,
specialised components rather than from similar general-purpose
components, Plan 9 achieves levels of efficiency, security,
simplicity, and reliability seldom realised in other distributed
systems. This paper discusses the building blocks, interconnections,
and conventions of Plan 9.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.120.8671&rep=rep1&type=pdf
==============================================================================
Induction of Decision Trees [26p]
Quinlan; 1986
Abstract:
The technology for building knowledge-based systems by inductive
inference from examples has been demonstrated successfully in several
practical applications. This paper summarizes an approach to
synthesizing decision trees that has been used in a variety of
systems, and it describes one such system, ID3, in detail. Results
from recent studies show ways in which the methodology can be modified
to deal with information that is noisy and/or incomplete. A reported
shortcoming of the basic algorithm is discussed and two means of
overcoming it are compared. The paper concludes with illustrations of
current research directions.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.167.3624&rep=rep1&type=pdf
==============================================================================
The Hardness of Cache-Conscious Data Placement [11p]
Petrank, Rawitz, 2002
Abstract:
The growing gap between the speed of memory access and cache access
has made cache misses an in uential factor in program eciency. Much
eort has been spent recently on reducing the number of cache misses
during program run. This eort includes wise rearranging of program
code, cache-conscious data placement, and algorithmic modications that
improve the program cache behavior. In this work we investigate the
complexity of nding the optimal placement of objects (or code) in the
memory, in the sense that this placement reduces the cache misses to
the minimum. We show that this problem is one of the toughest amongst
the interesting algorithmic problems in computer science. In
particular, suppose one is given a sequence of memory accesses and one
has to place the data in the memory so as to minimize the number of
cache misses for this sequence. We show that if P != NP, then one
cannot eciently approximate the optimal solution even up to a very
liberal approximation ratio. Thus, this problem joins the small family
of extremely inapproximable optimization problems. The other two
famous members in this family are minimum coloring and maximum clique.
http://www.cs.tufts.edu/~sguyer/classes/comp150-2006/papers/petrank02hardness.pdf
==============================================================================
On the translation of languages from left to right [33p]
Knuth, 1965
Abstract:
There has been much recent interest in languages whose grammar is
sufficiently simple that an efficient left-to-right parsing algorithm
can be mechanically produced from the grammar. In this paper, we
define LR(k) grammars, which are perhaps the most general ones of this
type, and they provide the basis for understanding all of the special
tricks which have been used in the construction of parsing algorithms
for languages with simple structure, e.g. algebraic languages. We give
algorithms for deciding if a given grammar satisfies the LR (k)
condition, for given k, and also give methods for generating
recognizers for LR(k) grammars. It is shown that the problem of
whether or not a grammar is LR(k) for some k is undecidable, and the
paper concludes by establishing various connections between LR(k)
grammars and deterministic languages. In particular, the LR(]c)
condition is a natural analogue, for grammars, of the deterministic
condition, for languages.
http://www.cs.dartmouth.edu/~mckeeman/cs48/mxcom/doc/knuth65.pdf
==============================================================================
Program development by stepwise refinement [13p]
Wirth, 1971
Abstract:
The creative activity of programming - to be distinguished from coding
- is usually taught by examples serving to exhibit certain techniques.
It is here considered as a sequence of design decisions concerning the
decomposition of tasks into subtasks and of data into data structures.
The process of successive refinement of specifications is illustrated
by a short but nontrivial example, from which a number of conclusions
are drawn regarding the art and the instruction of programming.
http://www.ehu.es/~ljrf/AED/2010/practicas/lenguaje_C/StepwiseRefinement_Wirth.pdf
==============================================================================
Garbage Collection in an Uncooperative Environment [17p]
Boehm, Weiser, 1988
Abstract:
We describe a technique for storage allocation and garbage collection
in the absence of significant cooperation from the code using the
allocator. This limits garbage collection overhead to the time
actually required for garbage collection. In particular, application
programs that rarely or never make use of the collector no longer
encounter a substantial performance penalty. This approach greatly
simplifies the implementation of languages supporting garbage
collection. It further allows conventional compilers to be used with a
garbage collector, either as the primary means of storage reclamation,
or as a debugging tool.
Our approach has two potential disadvantages. First, some garbage may
fail to be reclaimed. Second, we use a ‘‘stop and collect’’ approach,
thus making the strategy unsuitable for applications with severe
real-time constraints. We argue that the first problem is, to some
extent, inherent in any garbage collection system. Furthermore, based
on our experience, it is usually not significant in practice. In spite
of the second problem, we have had favorable experiences with
interactive applications, including some that use a heap of several
megabytes.
http://www.hpl.hp.com/personal/Hans_Boehm/spe_gc_paper/preprint.pdf
==============================================================================
Automated re-invention of six patented optimal lens systems using
genetic programming [8p]
Koza, 2005
Abstract:
This paper describes how genetic programming was used as an invention
machine to automatically synthesize complete designs for six optical
lens systems that duplicated the functionality of previously patented
lens systems. The automatic synthesis was done "from scratch"-that is,
without starting from a pre-existing good design and without
pre-specifying the number of lenses, the physical layout of the
lenses, the numerical parameters of the lenses, or the non-numerical
parameters of the lenses. One of the six genetically evolved lens
systems infringed a previously issued patent; three contained many of
the essential features of the patents, without infringing; and the
others were non-infringing novel designs that duplicated (or improved
upon) the performance specifications contained in the patents. One of
the six patents was issued in the 21st-century. The six designs were
created in a substantially similar and routine way, suggesting that
the approach used may have widespread utility. The genetically evolved
designs are instances of human-competitive results produced by genetic
programming in the field of optical design.
http://portal.acm.org/citation.cfm?id=1068337
==============================================================================
Demonstrating the Evolution of Complex Genetic Representations: An
Evolution of Artificial Plants [12p]
Toussaint, 2003
Abstract:
A common idea is that complex evolutionary adaptation is enabled by
complex genetic representations of phenotypic traits. This paper
demonstrates how, according to a recently developed theory, genetic
representations can self-adapt in favor of evolvability, i.e., the
chance of adaptive mutations. The key for the adaptability of genetic
representations is neutrality inherent in non-trivial
genotype-phenotype mappings and neutral mutations that allow for
transitions between genetic representations of the same phenotype. We
model an evolution of artificial plants, encoded by grammar-like
genotypes, to demonstrate this theory.
http://www.springerlink.com/content/ad524w1bvpvbjyh7/fulltext.pdf
==============================================================================
You and Your Research
Hamming (transcribed), 1986
Abstract:
At a seminar in the Bell Communications Research Colloquia Series, Dr.
Richard W. Hamming, a Professor at the Naval Postgraduate School in
Monterey, California and a retired Bell Labs scientist, gave a very
interesting and stimulating talk, You and Your Research to an overflow
audience of some 200 Bellcore staff members and visitors at the Morris
Research and Engineering Center on March 7, 1986. This talk centered
on Hamming's observations and research on the question ``Why do so few
scientists make significant contributions and so many are forgotten in
the long run?'' From his more than forty years of experience, thirty
of which were at Bell Laboratories, he has made a number of direct
observations, asked very pointed questions of scientists about what,
how, and why they did things, studied the lives of great scientists
and great contributions, and has done introspection and studied
theories of creativity. The talk is about what he has learned in terms
of the properties of the individual scientists, their abilities,
traits, working habits, attitudes, and philosophy.
http://www.cs.virginia.edu/~robins/YouAndYourResearch.pdf
==============================================================================
Flapjax: A Programming Language for Ajax Applications
Meyerovich, Guha, Baskin, Cooper, Greenberg, Bromfield, Krishnamurthi, 2009
Abstract:
This paper presents Flapjax, a language designed for contemporary Web
applications. These applications communicate with servers and have
rich, interactive interfaces. Flapjax provides two key features that
simplify writing these applications. First, it provides event streams,
a uniform abstraction for communication within a program as well as
with external Web services. Second, the language itself is reactive:
it automatically tracks data dependencies and propagates updates along
those dataflows. This allows developers to write reactive interfaces in
a declarative and compositional style.
Flapjax is built on top of JavaScript. It runs on unmodified browsers
and readily interoperates with existing JavaScript code. It is usable
as either a programming language (that is compiled to JavaScript) or
as a JavaScript library, and is designed for both uses. This paper
presents the language, its design decisions, and illustrative examples
drawn from several working Flapjax applications.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.154.5404&rep=rep1&type=pdf
==============================================================================
Junior: The Stanford Entry in the Urban Challenge
Montemerlo et al., 2008
Abstract:
This article presents the architecture of Junior, a robotic vehicle
capable of navigating urban environments autonomously. In doing so,
the vehicle is able to select its own routes, perceive and interact
with other traffic, and execute various urban driving skills including
lane changes, U-turns, parking, and merging into moving traffic. The
vehicle successfully finished and won second place in the DARPA Urban
Challenge, a robot competition organized by the U.S. Government.
http://robots.stanford.edu/papers/junior08.pdf
==============================================================================
Training a Multilingual Sportscaster: Using Perceptual Context to Learn Language
Chen, Kim, Mooney, 2010
Abstract:
We present a novel framework for learning to interpret and generate
language using only perceptual context as supervision. We demonstrate
its capabilities by developing a system that learns to sportscast
simulated robot soccer games in both English and Korean without any
language-specific prior knowledge. Training employs only ambiguous
supervision consisting of a stream of descriptive textual comments and
a sequence of events extracted from the simulation trace. The system
simultaneously establishes correspondences between individual comments
and the events that they describe while building a translation model
that supports both parsing and generation. We also present a novel
algorithm for learning which events are worth describing. Human
evaluations of the generated commentaries indicate they are of
reasonable quality and in some cases even on par with those produced
by humans for our limited domain.
http://www.jair.org/media/2962/live-2962-4903-jair.pdf
==============================================================================
Building Watson: An Overview of the DeepQA Project
Ferrucci, Brown, Chu-Carroll, Fan, Gondek, Kalyanpur, Lally, Murdock,
Nyberg, Prager, Schlaefer, Welty, 2010
Abstract:
IBM Research undertook a challenge to build a computer system that
could compete at the human champion level in real time on the American
TV quiz show, Jeopardy. The extent of the challenge includes fielding
a real-time automatic contestant on the show, not merely a laboratory
exercise. The Jeopardy Challenge helped us address requirements that
led to the design of the DeepQA architecture and the implementation of
Watson. After three years of intense research and development by a
core team of about 20 researchers, Watson is performing at human
expert levels in terms of precision, confidence, and speed at the
Jeopardy quiz show. Our results strongly suggest that DeepQA is an
effective and extensible architecture that can be used as a foundation
for combining, deploying, evaluating, and advancing a wide range of
algorithmic techniques to rapidly advance the field of question
answering (QA).
http://www.cs.uwaterloo.ca/~jhoey/teaching/cs486/AIMagzine-DeepQA.pdf
==============================================================================