O'Reilly logo

Design and Analysis of Algorithms by Himanshu B. Dave, Parag H. Dave

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

 

 

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required