Exercises for Week 12

Exercise 00

1. The index of concepts for this week is in a separate chapter. Peruse it and make sure that its entries make sense to you (otherwise, click on them to check them out).
2. The lecture notes start with updates (Chapter Lecture Notes, updates). Make sure to check them out regularly, as they reflect the development of the lecture.
3. Do take the time to peruse the lecture notes of this week and to reproduce their OCaml content.

Mandatory mini-projects

• Mini-project: Depth-first and breadth-first traversals
• Mini-project: Indexing data structures (except for imperative lists and for anything that has to do with exceptions)

Exercise 15

Characterize the effect of Foo_maker, Bar_maker, and Baz_maker in the resource file for the present lecture note.

Exercise 16

In a binary tree, every leaf is connected to the root of this tree by a “path”. This path has a length: for example, in a tree that consists of one leaf, the path from the root to this leaf has length 0.

1. Implement a function that computes the length of the longest path and the length of the shortest path in that tree.
2. Implement a function that computes the length of the longest path in that tree. Is there another name for this length?
3. Implement a function that computes the length of the shortest path in that tree. Is structural recursion the most efficient way to implement this function?

Resources

• The OCaml code for the present lecture note (latest version: 03 Nov 2022).

Version

Moved the practical exercise to Week 10 [24 Mar 2023]

Created [10 Jan 2023]