This book constitutes the refereed proceedings of the 35th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2009, held in Spindleruv Mlyn, Czech Republic, in January 2009.

The 49 revised full papers, presented together with 9 invited contributions, were carefully reviewed and selected from 132 submissions. SOFSEM 2009 was organized around the following four tracks: Foundations of Computer Science; Theory and Practice of Software Services; Game Theoretic Aspects of E-commerce; and Techniques and Tools for Formal Verification.