Skip to content

Chapter 3: Divide and Conquer

3.1 Merge Sort

Analysis

Iterative Version

space inefficiency

difficulty in initially correct binary search implementations

3.3 Integer Multiplication

Grade School Multiplication

Divide and Conquer Multiplication

3.4 Base Conversion

Recursive Implementation

Iterative Implementation

3.5 Closest Pair of Points

3.6 Closest Pair: A Divide-and-Conquer Approach

Introduction

Closest Pair in the Plane

Summary and Analysis of the 2-D Algorithm

Improving the Algorithm

3.7 Towers Of Hanoi Problem

Rules

Solution

3.8 Footnotes