Scribd
Upload
57 views7 pages

Online Instructions For Chapter 3: Decrease-And-Conquer: Algorithms Analysis and Design (CO3031)

This document provides online instructions for Chapter 3 on decrease-and-conquer strategies from the course Algorithms Analysis and Design. The chapter outlines decrease-and-conquer and its variations, and covers insertion sort, graph traversal algorithms, topological sorting, and generating permutations as examples of the technique. It is instructed by Dr. Vo Thi Ngoc Chau at Ho Chi Minh City University of Technology, Faculty of Computer Science and Engineering.

Uploaded by

Trần Quốc Khang
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
57 views7 pages

Online Instructions For Chapter 3: Decrease-And-Conquer: Algorithms Analysis and Design (CO3031)

This document provides online instructions for Chapter 3 on decrease-and-conquer strategies from the course Algorithms Analysis and Design. The chapter outlines decrease-and-conquer and its variations, and covers insertion sort, graph traversal algorithms, topological sorting, and generating permutations as examples of the technique. It is instructed by Dr. Vo Thi Ngoc Chau at Ho Chi Minh City University of Technology, Faculty of Computer Science and Engineering.

Uploaded by

Trần Quốc Khang
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 7

Ho Chi Minh City University of Technology

Faculty of Computer Science and Engineering

Online Instructions for


Chapter 3: Decrease-and-conquer

Algorithms Analysis and Design


(CO3031)

Instructor: Dr. Vo Thi Ngoc Chau


Email: chauvtn@hcmut.edu.vn

Semester 2 – 2019-2020
Course Outline
 Chapter 1. Fundamentals
 Chapter 2. Divide-and-Conquer Strategy
 Chapter 3. Decrease-and-Conquer Strategy
 Chapter 4. Transform-and-Conquer Strategy
 Chapter 5. Dynamic Programming and Greedy
Strategies
 Chapter 6. Backtracking and Branch-and-Bound
 Chapter 7. NP-completeness
 Chapter 8. Approximation Algorithms
2
Ho Chi Minh City University of Technology
Faculty of Computer Science and Engineering

Online Instructions for


Chapter 3: Decrease-and-conquer

PART 1

Semester 2 – 2019-2020
Chapter 3.
Decrease-and-Conquer Strategy

 3.1. Decrease- and-conquer strategy

 3.2. Insertion sort

 3.3. Graph traversal algorithms

 3.4. Topological sorting

 3.5. Generating all permutations from a set

4
3.1. Decrease- and-conquer
strategy

 Decrease-and-conquer strategy is based on


exploiting the relationship between a solution to
a given instance of a problem and a solution to a
smaller instance of the same .

 Three major variations of decrease-and-conquer:

 decrease by a constant

 decrease by a factor

 variable-size decrease
5
3.1. Decrease- and-conquer
strategy
problem of size n Problem of size n

decrease decrease

subproblem subproblem
of size n-1 of size n/2

Solution to the Solution to the


conquer subproblem conquer
subproblem

Solution to the Solution to the


original problem original problem

Decrease (by one)-and-conquer Decrease (by half)-and-conquer


Figure 5.1, [2], pp. 158. Figure 5.2, [2], pp. 159. 6
Algorithms Analysis and Design
(CO3031)

 Chapter 3. Decrease-and-conquer
 3.1. Decrease- and-conquer strategy

 3.2. Insertion sort

 3.3. Graph traversal algorithms

 3.4. Topological sorting

 3.5. Generating all permutations from a set

You might also like