Lecture notes for Week 2: Recursion

1. MergeSort Analysis (continued).

2. Lab remarks.

3. Recursion.

Textbook portions covered

Engineering Algorithms...(Clowes “online book”)

Chapter 2

Announcements

• Lecture notes now available.

Remarks on Lab 1

1. Good: In Lab 1 many students are trying to implement mySort(...) themselves (instead of “cutting and pasting” some C implementation they found).

2. Bad: Alas, some are coding mySort(...) directly with no abstract algorithm clearly identified.

3. Remarks: Recall that:

   • ELE428 is fundamentally a theory course.

Analysis of MergeSort (continued)

Announcements

• NONE

Introduction to Recursion

Covered most of Chapter 2 in Engineering Algorithms...(Clowes “online book”); i.e.:

• What is recursion? (divide and conquer)
• Addition example (add with counting and no loops)
• How it works
• Tail recursion
• Example: Fibonacci numbers
• Example: Towers of Hanoi
• Example: Counting ways to make change

Engineering Algorithms...(Clowes “online book”)

• 2.2
• 2.3
• 2.4
• 2.5
• 2.10
• 2.12
• 2.16
• 2.20