In the regular Monday seminar of the G²OAT group, Petr Š'tastný (FIT) will talk about symbolic execution, a program analysis technique that examines possible program states to provide insight into program behavior. Developing a symbolic execution mechanism for a particular language is often time-consuming for developers, especially with respect to the performance optimizations required to keep analysis runtimes reasonable.
Abstract
Can we construct heaps with interesting beyond-worst-case properties? And how can we use them for algorithm design? We will discuss a particular heap property -- the working set property -- and its applications for Dijkstra's algorithm and the problem of sorting numbers under partial information.