Rajmohan Rajaraman

Online Computation

Thursday, January 29


This seminar will concern problems that require computing with incomplete information.  In particular, the input to the  problem is given one piece at a time, and upon receiving an input, the algorithm must take an action without the knowledge of future inputs. Algorithms operating under these environments are called online algorithms, and arise in various resource allocation scenarios ranging from paging in a virtual memory system to perhaps more lucrative pursuits such as stock portfolio selection.

The seminar will be divided into two parts.  The first part will be a brief introduction to the area, including a presentation of competitive analysis, which is a formal framework for analyzing online algorithms.  In the second part of the seminar, we will focus on an online computation problem that arises in the domain of job scheduling.  Traditionally, scheduling policies have been devised to optimize performance metrics based on the "response time" of a job, which is the amount of time a given job spends in the system.  For many applications, alternative performance metrics based on the "stretch" of a job are more appropriate.  The stretch of a job is the ratio of the response time of the job to its processing time.  We will discuss the motivation behind stretch-based metrics and consider online scheduling policies that attempt to optimize these metrics.

Talk slides



Ken Baclawski

Ontology Development

Thursday,  February 5

Ontologies are emerging as an important tool for dealing with very large, complex and diverse sources of information.  It has also been recognized for some time that ontologies are advantageous for software development.  However, given  that ontologies are themselves a form of software, it is important that appropriate attention be paid to developing them.  In particular, ontologies must be consistent, provide sufficient coverage of the target domain and be developed at the appropriate level of detail.  While there are many ontology development tools, there are very few ontology development methodologies, and those that have been proposed do not address these issues adequately.  This is part of a general tendency in computer science to develop programs without designs or even requirements.  Because ontologies are closely related to modern object-oriented software design, it is natural to adapt existing object-oriented software development methodologies for the task of ontology development.  In this talk, ontology development is compared with software development in general.  While a number of features of object-oriented software development methodologies are especially well suited to ontology development, it is also the case that they sometimes conflict with modern ontology languages.  However, these conflicts can be reconciled, and the conclusion is that object-oriented software development methodologies show promise as a basis for ontology development methodologies.


Harriet Fell

Speech -- What's in it? 

Detecting Non-Linguistic Information in Vocal Emissions

Thursday,  February 12

Speech recognition focuses on the automatic recognition of words by a machine and natural language processing on machine understanding and/or generation of human language.  We study other information that is present in speech and other vocal emissions.  Our programs identify landmarks, points in an utterance around which listeners extract information about the underlying distinctive features, ala Ken Stevens' acoustic model of speech.  Applications include analysis of babbles to detect medical information, babble feedback for infants, and detection of emotion in speech.


Carole Hafner

Computers and Common Sense Reasoning

Thursday,  February 26

This talk will define "common sense reasoning", consider why a capability for common sense reasoning would be an advantage for computer systems, and introduce three major computational frameworks for modeling common sense: plan recognition, case-based reasoning and qualitative physics.



Will Clinger

Programming Languages: Some of the Questions

Thursday,  March 11

What kind of research questions arise in programming language design, specification, and implementation?

I will illustrate with concrete examples from my own research. For each example I will explain: What was the problem? How did it arise? What nature of solution was proposed? What kind of problems arose from the solution?

The examples will include floating point arithmetic, macros, compiler optimization and correctness, concurrency, and garbage collection.


Viera Proulx

Computer Science Education Research

Thursday,  April 1


Karl Lieberherr

Aspects of Security

Thursday,  April 8

Security regards the protection of valuable information against different kinds of threats, such as stealing, modifying, destroying etc. We will survey aspect-oriented approaches for dealing with security.