That depends a good deal on where you want to get to,' said the Cat.

**Schedule**: Lecture Slot 11 in SIC 301 Kresit

**Instructor:** Om Damani ** Office hours**: Fri 5-6

**Moodle**: Slides, Assignments, Solutions, Reference Materals, Newsgroup etc.

** Pre-requisites** Background in Propositional Logic and Quantifiers

**Audit Requirements**:
You have to pass the course.

1. [Kal] Anne Kaldewaij, Programming: The Derivation of Algorithms, Prentice Hall International, 1990.

Sr. No: Date | Topic | Resource |
---|---|---|

1-2: 08-11/01 |
Logistics, Inroduction, Example Problems: specifying max, finding all elements of an array satisfying certain condition | logistics |

3-5: 15-25/01 |
Propositional Logic, Quantifier Calculus | Ch. 1 and Ch. 3, cached copy of A Programmer's Introduction to Predicate Logic by H. Conrad Cunningham |

6: 29/01 |
Hoare Triple, Weakest Precondition, The Guarded Command Language - Skip, Assignment | Ch 2-2.2 |

7: 01/02 |
The Guarded Command Language - Catenation | Ch 2.3 |

8: 05/02 |
The Guarded Command Language - Selection | Ch 2.4 |

9-11: 08-15/02 |
The Guarded Command Language - Repetition, loop invariant | Ch 2.5-2.7 |

12: 26/02 |
Program Derivation: Taking a conjunct as guard, 4-tuple sort, integer sq. root, linear search | Ch 4.0-4.1, 6.1 |

13-14: 01-05/03 |
Replacing constant by variable, divmod, more efficient divmod, exponentiation, Binary Search | Ch 4.2, 5.1, 6.3 |

15: 08/03 |
Quiz | |

16: 12/03 |
Strengthening invariants, Fibonacci, maxsegsum | Ch 4.3 |

17: 15/03 |
Tail invariants | Ch 4.4 |

18-19: 19-22/03 |
Bounded Linear Search, Array Partitioning, more on Tail invariants | [kal] Ch 6.2, 10.0 - 10.2.0, 4.4 |

20: 26/3 |
Majority Voting | |

21: 2/4 |
Tail Recursion - reversing a link list, Post order traversal of a binary tree, | - |

22-23: 5/4 |
Searching by Elimination, Making post-condition and prec-condition resemble each-other: Saddleback Search | [kal] Ch 8.0-8.1.0 . Note that in class we did a non-tail recursive formulation of the saddleback search - the saddleback search discussion in book is based on the concept of "Using tail-invariant when post-condition is an equation" |

24: 9/4 |
When tail-invariant is better/needed; when repetition guard is not a conjunct of post-condition but is calculated as a sufficient condition for implying the post-condition (along with invariant), TestAllTrue, Using tail-invariant when post-condition is an equation: Decomposition in sum of two squares | Dijkstra on tail-invariant, Ch 8.1.1 |

25: 12/4 |
All pair shortest path in a graph | - |