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|
|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||-|