### Unit 3: Divide and Conquer Method

In this unit, we will examine a popular technique called divide-and-conquer that is used in solving computer science problems. This technique solves the problem by breaking up the problem into smaller problems of same type and then recursively solving these smaller problems and combining their answers. We will also look into analysis of these algorithms through the use of recursion techniques.

**Completing this unit should take you approximately 10 hours.**

Upon successful completion of this unit, you will be able to:

- Explain methods for solving recurrences useful in describing running times of recursive algorithms.
- Describe divide-and-conquer recursive technique for solving a class of problems.

### 3.1: Introduction to Divide and Conquer Algorithms

Read Chapter 2 of S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani's book

*Algorithms*.

### 3.2: Recurrences in Algorithms

Watch this lecture to learn about the basics of the algorithm.

### 3.3: Recursion

Read this article to learn about the mathematical concepts behind the idea of recursion.

Complete all questions in this assignment. There are two questions on the divide-and-conquer strategy. The first one involves a search strategy, whereas the second one involves a multiplication strategy. You can check your answers against the Answer Key.