Design and Analysis of Algorithms

Chapter 9

Abstract Algorithms-1-Divied-and-Conquer

Objectives

After reading this chapter, you should understand:

• Abstract Algorithms: Control Abstraction
• Divide and Conquer Strategy : its applicability
• How Divide and Conquer algorithms can be analysed
• How to decide on choosing the Divide and Conquer strategy
• Various Real World Problems where Divide and Conquer is most Useful
• Limitations of the Divide and Conquer strategy

Chapter Outline

9.1 Introduction

9.2 A Multiplication Algorithm

9.2.1 Analysis of the Multiplication Algorithm

9.3 Application to Graphics Algorithms

9.3.1 Introduction to Triangulation

9.3.2 Convex Hulls

9.4 Where D&C Fails

9.4.1 Characteristics of Problems for which D&C is Unsuitable

9.5 Timing Analysis

 

 

Summary ∣ Key ...