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

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

**TA: ** Devendra Shelar

**Moodle**: Slides, Assignments, Solution, Newsgroup etc.

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

**Audit Requirements**:
You have to do all the assignments. There will be at least one assignment per week.

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

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

1: 22/07 |
Logistics, Inroduction, Example Problems: max, finding the common integer in three sorted arrays | logistics |

2: 27/07 |
sorting 4 integers, majority voting | |

3: 29/07 |
Propositional Logic, importance of equivalence, all binary operators in terms of equivalence and disjunction | Cached copy of A Programmer's Introduction to Predicate Logic by H. Conrad Cunningham |

4-5: 3,5/08 |
Propositional Logic, Predicate Calculus | [kal] Ch 1 |

6-7: 10,12/08 |
Qunatification Calculus, Specification Examples | [kal] Ch 3 |

8-9: 17,19/08 |
Guarded Command Language | [kal] Ch 2 |

10-11: 24,26/08 |
GCL, Deriving loopless programs, Taking a conjunct as invariant | [kal] Ch 2, 4.1 |

12: 02/09 |
Linear Search | [kal] Ch 6.1 |

13-14: 07-09/09 |
Multiple solutions to Integer Divison | [kal] Ch 4.1 |

15-16: 21-23/09 |
More efficient Integer Divison | [kal] Ch 5.1 |

17-18: 28-30/09 |
Maximum Segment Sum, Inverted Pairs, Binary Search | [kal] Ch 4.3. Binary search is given in [kal] 6.3, though we followed Wim Feijen's approach. You can also look at Dijkstra's derivation. |

19-20: 5-7/10 |
Quiz and solution discussion : subsegment having maximal credit | [kal] Ex 5 in Ch 4.3 |

21-22: 12-14/10 |
Bounded Linear Search, Array Partitioning, Tail Recursion | [kal] Ch 6.2, 10.0 - 10.2.0, 4.4 |

Tutorial: 17/10 |
Meaning of P(n:=n+1), Program annotation | [kal] Ch 4.3 |

23-24: 19-21/10 |
Tail Recursion - reversing a link list, Post order traversal of a binary tree, Searching by Elimination, Celebrity problem | [kal] Ch 6.4 |

25-26: 26-28/10 |
Diwali Holidays | |

27: 2/11 |
Making post-condition and prec-condition resemble each-other: Saddleback Search, Using tail-invariant when post-condition is an equation: Decomposition in sum of two squares | [kal] Ch 8.0-8.1.1 . 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" |

28: 4/11 |
No class - Schedule for Tuesday, Reading Assignment: Segment Problems | [kal] Ch 7, 8.2 |

29: 9/11 |
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) | Wim Feijen on tail-invariant and Dijkstra on tail-invariant. Note that in the Wim Feijen's problem, there is no choice but to use a tail-invariant. |

30: 11/11 |
Majority Voting, Specifying Minimum Spanning Tree |