Skip to main content

CS303: Algorithms

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.
- Unit 3 Learning Outcomes Page
- 3.1: Introduction to Divide and Conquer Algorithms
  - University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani's "Divide-and-Conquer Algorithms" URL
    Read Chapter 2 of S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani's book Algorithms.
- 3.2: Recurrences in Algorithms
  - Massachusetts Institute of Technology: Dr. Erik Demaine's "Introduction to Algorithms" Page
    Watch this lecture to learn about the basics of the algorithm.
- 3.3: Recursion
  - Wikipedia: "Recursion" URL
    Read this article to learn about the mathematical concepts behind the idea of recursion.
  - Divide and Conquer Assignment URL
    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.