Seminars: Summer 2003
July. 24: Susan H. Rodger
Title: Learning Computer Science Concepts via Interactive Visualizations
Location and time: Shaffer 2 11:00 am
Abstact: At Duke University we use interactive visualizations to aid the learning process in a wide-range of courses including CS0, CS1, CS2 and Mathematical Foundations. We present two software tools we have developed, JAWAA and JFLAP, and show how we use them in teaching computer science concepts. JAWAA is a scripting language for creating animations easily over the web. JAWAA includes primitives, easy creation of data structures and operations on these structures, and an editor for easy creation of complex objects. We have used JAWAA in all four courses mentioned above. JFLAP is a comprehensive software tool for experimenting with concepts in a formal languages and automata theory course that is currently used around the world in over 40 countries. With JFLAP one can explore the concepts of automata, grammars, parsing, L-systems, and the conversion of one representation of a language to another. For example, one can enter in a regular expression, convert it to an NFA, then a DFA, then a minimum state DFA and then back to a regular expression. We will describe how JFLAP and JAWAA aid in visualizing and interacting with computer science concepts.
June. 4: Roger Wattenhofer
Title: Routing in Ad-Hoc Networks
Location and time: Shaffer 303 11:00 am
Abstact: In this talk I present two recent results in the area of ad-hoc routing. In the first part I discuss the only local (thus practical in a mobile ad-hoc network environment) dominating set construction with non-trivial worst-case guarantees. Having a small dominating set is an important stepping stone for reactive ad-hoc routing algorithms such as AODV or DSR. In the second part of the talk I present GOAFR, a geometric (a.k.a. geographic, location- or position-based) routing algorithm. Simulations show that GOAFR is the most efficient geometric routing algorithm; in addition, GOAFR is also the only algorithm that is asymptotically optimal in the worst case. It is widely believed that understanding ad-hoc routing will lead to a deeper understanding of routing in general.
The first part is joint work with Fabian Kuhn; the second part with Aaron Zollinger and Fabian Kuhn.
Bio: Roger Wattenhofer received his doctorate in computer science in 1998 from ETH Zurich, Switzerland. From 1999 to 2001 he was in the USA, first at Brown University in Providence, RI, then at Microsoft Research in Redmond, WA. Currently he is an assistant professor at ETH Zurich. Roger Wattenhofer's research interests include a variety of algorithmic aspects in networking and distributed computing; in particular, peer-to-peer computing and ad-hoc networks.
June. 3: Adam Meyerson
Title: Approximation Algorithms for Time-Dependent TSP
Location and time: Shaffer 100 11:00 am
Host: Baruch Awerbuch
Abstact: Joint work with Avrim Blum and Shuchi Chawla (CMU) And David Karger and Maria Minkoff (MIT) And Terran Lane (University of New Mexico)
Consider a robot which delivers various packages. The robot needs to visit a series of locations, and the quality of the path selected is determined by the timeliness of the deliveries. We can assume that the robot recieves a reward for each package delivered, where the reward is determined by the package identity and the delivery time. Our goal is to find a path which maximizes the total reward.
In this talk, we consider two different functions relating reward to time. In the Orienteering problem, the rewards are fixed until a specified time, at which point all rewards drop to zero. This is the problem of maximizing the number of destinations visited before a specific deadline. In the Discounting problem, the reward decays exponentially with time. This model is frequently considered in the realm of Markov decision processes. For each of these two functions, we describe the first constant approximation algorithms.
