Introducing "Theory" in the Second Programming Course

Traditionally, the first two programming courses have emphasized basic techniques and skills - the details of a programming language, basic problem solving and program development, "structured programming", the manipulation of simple data structures and files, basic sorting and searching algorithms, etc. They have placed little or no emphasis on such "advanced" or "theoretical" material as rigorous speicifaction and verification, formal language definition, automata, or complexity anlaysis. Their approach, in other words,is similar to that taken by elementary calculus courses, which teach the mechanics of differentiation and integratiojjn without bringing in foundation material and technically rigorous treatments. The reasoon for avoiding theory in an elecmentary calculus course is quite legitimate: for most students, rigorous treantment is not useful enough to justifu spending time on it at the expense of manioulative skills. In this paper, we shall argue that this reasoning does apply to programming.