bmkapron@theory.utoronto.ca (Bruce Kapron) (01/20/89)
Time: Tuesday, January 24, 1989. 3pm EST Location: GB420 Speaker: Armin Haken Title: A connectionist network that takes exponential time to find a stable state, under any update order Summary: A family of symmetric connection networks is presented with the following bad habit: Starting at a certain configuration, more than 2**(n**1/4) steps are needed to reach a stable state, no matter what order the unhappy nodes are updated. Here n is the size of the explicit description of the network. The networks are designed to implement binary counters.
bmkapron@theory.utoronto.ca (Bruce Kapron) (01/27/89)
Time: Tuesday, January 31 1989. 3pm EST. Location: GB420 Speaker: Hazel Everett Recognizing the Visibility Graphs of Spiral Polygons Given a simple polygon its visibility graph is defined as follows: the vertices of the graph correspond to the vertices of the polygon and two vertices in the graph are adjacent if the line segment between them lies entirely within the polygon. Visibility graphs are important in the solutions to such problems in robot motion planning as finding shortest paths in polygonal scenes and have been the focus of much research effort in recent years. The recognition problem for visibility graphs is given a graph determine whether it is the visibility graph of a simple polygon. Little is known about the complexity of this problem. In this talk I present a linear time recognition algorithm for the visibility graphs of spiral polygons. This constitutes the first non-trivial recognition algorithm for the visibility graphs of a restricted class of polygons.
bmkapron@theory.utoronto.ca (Bruce Kapron) (02/20/89)
Student Seminar Speaker: Murray Sherk Time and place: Tuesday, February 21, 3:00pm, GB420. Basic Outline: In 1983, Sleator and Tarjan introduced an efficient form of self-adjusting search tree called a splay tree. I show how to extend the idea of splaying so it applies to k-ary search trees as well as binary search trees. There are several problems encountered in doing this and I'll explain them a bit as I give my solutions. Consider the following: Let s be a sequence of search requests. Assume you know s and want to minimize the cost of doing s. You get to pick any search tree you want, but you are not allowed to change it during the sequence. The tree you pick will be a static optimal tree for sequence s. In order to find the static optimal tree, you have to know s in advance. For some sequences, the cost of s in the static optimal tree can be a factor of logn better than the cost of s in a balanced tree (such as an AVL tree). Surprisingly, splay trees do "as well" as static optimal trees but are completely online (i.e. have no knowledge of s). They can also get completely unbalanced, yet do "as well" as balanced trees when we allow insertions and deletions. I'll talk about amortized analysis and splay tree efficiency. Then I'll show how to extend splaying to k-ary search trees -- meaning we can now get a self-adjusting version of the ever-popular B-tree data structure. No prior knowledge of splay trees or amortized analysis is required, but you should know what a binary search tree is. Even if you don't follow all of the analysis, the definitions of the data structures are easy to understand and well worth knowing.