Scribd
Upload
5 views14 pages

ADA CH 1

The document outlines various algorithmic techniques including brute force, dynamic programming, backtracking, divide and conquer, greedy algorithms, and branch and bound. Each algorithm has its own approach to problem-solving, such as exhaustive searching, breaking down problems, and optimizing solutions. Additionally, it describes the heap data structure, emphasizing its properties and implementation.

Uploaded by

rishabh yaduwanshi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
5 views14 pages

ADA CH 1

The document outlines various algorithmic techniques including brute force, dynamic programming, backtracking, divide and conquer, greedy algorithms, and branch and bound. Each algorithm has its own approach to problem-solving, such as exhaustive searching, breaking down problems, and optimizing solutions. Additionally, it describes the heap data structure, emphasizing its properties and implementation.

Uploaded by

rishabh yaduwanshi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Brute force algorithm:

• The general logic structure is applied to design an algorithm.

• It is also known as an exhaustive search algorithm that searches all the possibilities to
provide the required solution.

Such algorithms are of two types:

• Optimizing : Finding all the solutions of a problem and then take out the best solution or it
will terminate if the best solution is known.

• Sacrificing: As soon as the best solution is found, then it will stop.

Dynamic programming algorithm

A dynamic programming algorithm (also known as dynamic optimization algorithm) remembers the
past result and uses them to find new result means it solve complex problems by breaking it down
into a collection of simpler subproblems, then solving each of those subproblems only once ,and
storing their solution for future use instead of recomputing their solutions again.

Backtracking:

Backtracking is an algorithmic technique that solves the problem recursively and removes the
solution if it does not satisfy the constraints of a problem.

Divide and conquer algorithm

Divide and conquer consist of two parts first of all it divides the problems into smaller subproblems
of the same type and solve them solve them recusively and then combine them to to form the
solution of the original problem

Greedy algorithm

Greedy algorithm is an algorithm that solves the problem by taking optimal solution at the local level
(without regards for any consequences) with the hope of finding optimal solution at the global level.

Greedy algorithm is used to find the optimal solution but it is not necessary that you will definitely
find the optimal solution by following this algorithm.

Branch and Bound Algorithm:

• The branch and bound algorithm can be applied to only integer programming problems.

• This approach divides all the sets of feasible solutions into smaller [Link] subsets are
further evaluated to find the best solution
Heap

A heap is a data structure that stores a collection of objects (with keys), and has the following
properties:

 Complete Binary tree

 Heap Order

It is implemented as an array where each node in the tree corresponds to an element of the
array.

HEAP ORDER PROPERTY

For every node v, other than the root, the key stored in v is greater or equal (smaller or equal for max
heap) than the key stored in the parent of v.

You might also like