COMP 1002 Unit 7 overview

In this unit we will introduce a powerful method for creating sequences, functions and sets: recursion. Recursion allows us to build up our objects of interest step by step, by stating how to make new elements and values out of what we have so far. This is one of the most common concepts in computer science, which you will encounter over and over in your programming career. We will look at a variety of recursive definitions and recursively defined objects, from sequences of numbers to algorithms, from fractals to grammars.

We will also talk about complexity of computation, and growth rates of functions, a central notion in algorithm design and analysis. And we encounter a new proof technique, structural induction, which lets us prove properties of recursively defined objects.

Readings

Most of the material in this unit is covered in section 5.3 in the textbook. Recurrences are introduced in section 2.4, and covered in great detail in section 8.1. For the growth of functions, see section 3.2. Context-free grammars are in section 13.1.

Learning objectives

Here you will learn to both interpret given recursive definitions of sequences, functions and sets, and write your own. You will practice describing sets of strings using grammars, constructing grammars for sets, determining which strings are generated by a given grammar, and showing how to derive strings from a grammar using parse trees.

You will also learn about closed form of recurrences, and practice estimating growth rate and comparing functions using big-O notation. Additionally, you will learn to write proofs of properties of recursively defined objects using structural induction. As with other proof techniques, you will be expected to do proofs by structural induction similar to ones in this unit on the final exam.

Vocabulary

You need to know the meaning of the following terminology (and respective notation):