The two-volume set LNCS 4051 and LNCS 4052 constitutes the refereed proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006, held in Venice, Italy, in July 2006.This is Volume I (LNCS 4051), presenting 61 revised full papers together with 1 invited lecture that were carefully reviewed and selected from 230 submissions. Those papers have a special focus on algorithms, automata, complexity and games and are organized in topical sections on graph theory, quantum computing, randomness, formal languages, approximation algorithms, graph algorithms, algorithms, complexity, data structures and linear algebra, graphs, game theory, networks, circuits and regular expressions, fixed parameter complexity and approximation algorithms.Volume II (LNCS 4052) comprises 2 invited papers and 2 additional conference tracks with 24 papers each - rigorously selected from numerous submissions - focusing on algorithms, automata, complexity and games as well as on security and cryptography foundation respectively. The papers are organized in topical sections on zero-knowledge and signatures, cryptographic protocols, secrecy