This book explains the development of theoretical computer science in its early stages, specifically from 1965 to 1990. The author is among the pioneers of theoretical computer science, and he guides the reader through the early stages of development of this new discipline. He explains the origins of the field, arising from disciplines such as logic, mathematics, and electronics, and he describes the evolution of the key principles of computing in strands such as computability, algorithms, and programming. But mainly it's a story about people - pioneers with diverse backgrounds and characters came together to overcome philosophical and institutional challenges and build a community. They collaborated on research efforts, they established schools and conferences, they developed the first related university courses, they taught generations of future researchers and practitioners, and they set up the key publications to communicate and archive their knowledge. The book is a fascinating insight into the field as it existed and evolved, it will be valuable reading for anyone interested in the history of computing.

To examine, analyze, and manipulate a problem to the point of designing an algorithm for solving it is an exercise of fundamental value in many fields. With so many everyday activities governed by algorithmic principles, the power, precision, reliability and speed of execution demanded by users have transformed the design and construction of algorithms from a creative, artisanal activity into a full-fledged science in its own right. This book is aimed at all those who exploit the results of this new science, as designers and as consumers. The first chapter is an overview of the related history, demonstrating the long development of ideas such as recursion and more recent formalizations such as computability. The second chapter shows how the design of algorithms requires appropriate techniques and sophisticated organization of data. In the subsequent chapters the contributing authors present examples from diverse areas - such as routing and networking problems, Web search, information security, auctions and games, complexity and randomness, and the life sciences - that show how algorithmic thinking offers practical solutions and also deepens domain knowledge. The contributing authors are top-class researchers with considerable academic and industrial experience; they are also excellent educators and communicators and they draw on this experience with enthusiasm and humor. This book is an excellent introduction to an intriguing domain and it will be enjoyed by undergraduate and postgraduate students in computer science, engineering, and mathematics, and more broadly by all those engaged with algorithmic thinking.

The papers containedin this volume were presentedat the 5th IFIP InternationalC- ference on Theoretical Computer Science (IFIP TCS), 7-10 September 2008, Milan, Italy. TCS is a bi-annual conference.The ?rst conferenceof the series was held in Sendai (Japan, 2000), followed by Montreal (Canada, 2002), Toulouse (France, 2004) and Santiago (Chile, 2006).TCS is organizedby IFIP TC1 (Technical Committee 1: Fo- dations of Computer Science) and Working Group 2.2 of IFIP TC2 (Technical C- mittee 2: Software: Theory and Practice). TCS 2008 was part of the 20th IFIP World Computer Congress (WCC 2008), constituting the TC1 Track of WCC 2008. The contributed papers were selected from 36+45 submissions from altogether 30 countries. A total of 14+16 submissions were accepted as full papers. Papers in this volume are original contributions in two general areas: Track A: Algorithms, C- plexity and Models of Computation;and Track B: Logic, Semantics, Speci?cation and Veri?cation. The conference also included seven invited presentations, from Luca Cardelli, Thomas Ehrhard, Javier Esparza, Antonio Restivo, Tim Roughgarden, Gr- gorz Rozenberg and Avraham Trakhtman. These presentations are included (except one) in this volume. In particular, Luca Cardelli, Javier Esparza, Antonio Restivo, Tim Roughgarden and Avraham Trakhtman accepted our invitation to write full papers - lated to their talks.

The papers containedin this volume were presentedat the 5th IFIP InternationalC- ference on Theoretical Computer Science (IFIP TCS), 7-10 September 2008, Milan, Italy. TCS is a bi-annual conference.The ?rst conferenceof the series was held in Sendai (Japan, 2000), followed by Montreal (Canada, 2002), Toulouse (France, 2004) and Santiago (Chile, 2006).TCS is organizedby IFIP TC1 (Technical Committee 1: Fo- dations of Computer Science) and Working Group 2.2 of IFIP TC2 (Technical C- mittee 2: Software: Theory and Practice). TCS 2008 was part of the 20th IFIP World Computer Congress (WCC 2008), constituting the TC1 Track of WCC 2008. The contributed papers were selected from 36+45 submissions from altogether 30 countries. A total of 14+16 submissions were accepted as full papers. Papers in this volume are original contributions in two general areas: Track A: Algorithms, C- plexity and Models of Computation;and Track B: Logic, Semantics, Speci?cation and Veri?cation. The conference also included seven invited presentations, from Luca Cardelli, Thomas Ehrhard, Javier Esparza, Antonio Restivo, Tim Roughgarden, Gr- gorz Rozenberg and Avraham Trakhtman. These presentations are included (except one) in this volume. In particular, Luca Cardelli, Javier Esparza, Antonio Restivo, Tim Roughgarden and Avraham Trakhtman accepted our invitation to write full papers - lated to their talks.

This volume contains the proceedings of ICALP 89, held at Stresa, Italy, July 11-15, 1989. ICALP 89 is the 16th International Colloquium on Automata, Languages and Programming in a series of meetings sponsored by the European Association for Theoretical Computer Science (EATCS). It is a broadly based conference covering all aspects of theoretical computer science including topics such as computability, automata theory, formal language theory, analysis of algorithms, computational complexity, mathematical aspects of programming language definition, logic and semantics of programming languages, foundations of logic programming, theorem proving, software specification, computational geometry, data types and data structures, theory of data bases and knowledge based systems, cryptography, VLSI structures, parallel and distributed computing, models of concurrency and robotics.

This book is an up-to-date documentation of the state of the art in combinatorial optimization, presenting approximate solutions of virtually all relevant classes of NP-hard optimization problems. The well-structured wealth of problems, algorithms, results, and techniques introduced systematically will make the book an indispensible source of reference for professionals. The smooth integration of numerous illustrations, examples, and exercises make this monograph an ideal textbook.