Department Colloquium / Seminar

This semester (Pranvere 2010), CSEE will organize a seminar on Wednesdays at 15:30-17:00 in room C 310.

The seminar group is a collection of students and professors that meets weekly to discuss various
Computer Science topics but is mainly focused on algorithms. During each meeting a member of the group
gives a 1-1.5 hour lecture. Typically, we present recent results found in conference proceedings, journals, from
our own research, or by visiting researchers.

Any student or professor with an interest in such topics is encouraged to attend. Meanwhile, if you have a talk
you wish to present, send me an email at [email protected] with the title and an abstract.

1.Wednesday, Apr 7, 2010 Nicola Corriero -  C 310, 15:30
Title:  Embedded System and GNU/Linux

Embedded system can be defined as information processing systems embedded into enclosing products such as cars, telecomunications or fabrication equipment. Embedded system are considered to be the most important application area of information technology during the coming years. Due to this expectation, the terms post-PC era was coined. During the talk will explain the components and the problems of these systems.


2.Wednesday, Mar 17, 2010 Benjamin Justus -  C 310, 15:30
Title: Addition Chains and Efficient Computer Arithmetics

Addition chains are sequences of operations that lead from 1 to a certain target integer by adding two prior computed values. They serve as an important concept for the efficient computation of powers in different contexts. In applications, they arise in cryptograpy and computer arithmetics.  We will survey known results and open problems in the area.


3.Wednesday, Mar 10, 2010 -  Ervin Ruci -  C 310, 15:30
Title: Generating Simple Polygons 

Given a set of points in the plane we want to compute all simple polygons that can be formed using these points as vertices. The counting problem for simple polygons is quite difficult. It is open wether or not we can compute the number of simple polygons with a given vertex set in time bounded by a polynomial of n. One can generate permutations at random and check for simplicity. The worst case for this  approach occurs when the points are in convex position. only 2n of the n! permutations correspond to the  convex hull which is the only simple polygon. In general, for a given vertex set we would like to count  and to enumerate only those permutations that correspond to simple polygons. We know of no efficient  enumeration procedure for simple polygons and no polynomial-time algorithm for counting the number of 
simple polygons on a given vertex set.  In this talk I explain various approaches on this problem, using geometric duality as the main tool.