Contents

• Models of computation
  • Introduction
  • Mathematical preliminaries
    • Sets
    • Relations and Functions
    • Principle of Mathematical Induction
    • Problems
  • A functional model of computation
    • The primitive expressions
    • Substitution of functions
      • Substitution using let
    • Definition of functions using conditionals
    • Functions as inductively defined computational processes
    • Recursive processes
    • Analysis of correctness and efficiency
      • Correctness
      • Efficiency
      • Efficiency, Why and How?
      • In the long run: Asymptotic analysis and Orders of growth
    • More examples of recursive algorithms
    • Scope rules
    • Tail-recursion and iterative processes
      • Correctness of an iterative process
    • More examples of iterative processes
    • Problems
  • The Imperative model of computation
    • The primitives for the imperative model
      • Variables and the assignment instruction
      • Assertions
      • The if then else instruction
      • The while do instruction
      • Functions and procedures in the imperative model
    • Problems
  • Step-wise refinement and Procedural Abstraction
    • Step-wise refinement
      • Executable specifications and rapid-prototyping
      • Examples of step-wise refinement
    • Procedural abstraction using higher-order functions
      • Functions as input parameters
      • Polymorphic functions
      • Constructing functions using lambda ()
      • Functions as returned values
    • Problems
  
  
• Data-directed programming
  • Abstract Data Types
    • Building the Rational data-type (pairs)
    • Rational data-type in ML
      • signature, datatype and module
    • Rational data-type in Java
      • Interfaces, Classes and Objects: Basics of Object Oriented Programming
    • Problems
  • Programming with Lists
    • Lists
    • The data-type in ML
    • The data-type in Java
      • Sharing of lists and garbage collection
      • List programming in Java
    • Problems
    • Appendix: The Int class
  
  
• About this document ...