Course objective: To introduce students to algorithmic and computational thinking, and programming in the small. The course will address the following issues:
1. Problem formulation in a precise and concise fashion and independent of language considerations.
2. Design of simple algorithms from the problem specification – their correctness and analysis of efficiency.
3. The intermediate steps in the design of a program from an algorithm through a process of step-wise refinement. Language dependent considerations may be used in this process, but not elsewhere.
The emphasis throughout the course will be on the analysis required while designing correct and efficient algorithms. The course is intended to teach a student a systematic process of design - beginning with problem formulation from an informal specification, through convincing arguments to algorithms, the analysis of their correctness and efficiency, and finally arriving at programs through a process of stepwise refinement. A programming language bias will be avoided and programs will be developed in both imperative and functional styles.
Pre-requisite: The course will expect familiarity with class 12 level mathematics (sets, relations, functions, basic logic and truth tables, basic counting and the principle of mathematical induction), but not necessarily with programming.
Coverage: Concept of an algorithm; recursion and principle of mathematical induction; correctness of algorithms; efficiency of algorithms time and space measures; algorithms to programs; specification, top-
down development and step-wise refinement; the notion of state and finite state machine; imperative programs; correctness and loop invariants; basic algorithm design techniques; encapsulation, abstractions
and modularity; basics of object-oriented programming; basic logic, soundness and completeness, example of a propositional resolution; an example of concurrency; an intro to numerical computation.
The course will be programming language independent, and will involve programming in multiple programming languages, in both functional and imperative styles.
