Lectures on Software: Distances, Invariants and Recursion

This lecture (part of a general lecture series on various aspects of software, see here for a blog article announcing it)  is available on YouTube in four segments:

  • Start here with Part 1 (18:07).
  • Part 2 is here (16:04).
  • Part 3 is here (11:53).
  • Part 4 is here (19:41).

It explores an important and widely used algorithm, explains why it works (through the notion of loop invariant), investigates the connection between the iterative and recursive versions, and extends the discussion to dynamic programming algorithms.

The supporting code is available at

https://github.com/EiffelSoftware/Meyer_lectures/tree/main/Levenshtein_and_recursion

Here is the reference material cited one of the final slides:

  • Survey on the loop invariants of important algorithms, cited in part 2: se.ethz.ch/~meyer/publications/methodology/invariants.pdf
  • Gérard Berry’1976 paper, cited in part 4: several versions (PDF) available by searching for “Gerard Berry Bottom-up computation of recursive programs” without the quotes. Note that my Touch of Class textbook has a detailed discussion of bottom-up computation of recursive programs (in its chapter on recursion).
  • Touch of Class introductory textbook: here at amazon.com ($28.89), search other Amazon country sites for “Touch of Class Meyer”.
    The book’s own page is touch.ethz.ch (sample chapters etc.). (Note: many links are currently broken on that page, I am working to have them restored.)
  • And of course:

 

 

 

 

VN:F [1.9.10_1130]
Rating: 8.0/10 (1 vote cast)
VN:F [1.9.10_1130]
Rating: +1 (from 1 vote)
Lectures on Software: Distances, Invariants and Recursion, 8.0 out of 10 based on 1 rating
Be Sociable, Share!

Comments are closed.