Scribd
Upload
2 views2 pages

All Algorithm Design Techniques and Algorithms Bas

The document outlines major algorithm design techniques including brute force, divide-and-conquer, decrease and conquer, transform and conquer, greedy, dynamic programming, and backtracking. Each technique is suited for specific problem types and is exemplified by classic algorithms such as merge sort, Dijkstra's shortest path, and the N-Queens problem. The document serves as a comprehensive overview of these techniques and their applications in algorithm design.

Uploaded by

bittuthehacker
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
2 views2 pages

All Algorithm Design Techniques and Algorithms Bas

The document outlines major algorithm design techniques including brute force, divide-and-conquer, decrease and conquer, transform and conquer, greedy, dynamic programming, and backtracking. Each technique is suited for specific problem types and is exemplified by classic algorithms such as merge sort, Dijkstra's shortest path, and the N-Queens problem. The document serves as a comprehensive overview of these techniques and their applications in algorithm design.

Uploaded by

bittuthehacker
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

all algorithm design techniques and algorithms

based on those design techniques


Major algorithm design techniques include divide-and-conquer, greedy, dynamic programming,
and others like brute force and backtracking. Each technique applies to specific problem types,
with classic algorithms exemplifying their use.

Brute Force
Generates all possible solutions and checks validity, suitable for small inputs. [1]
Examples: Selection sort, bubble sort, naive string matching, traveling salesman
(exhaustive). [2] [3]

Divide and Conquer


Divides problems into independent subproblems, solves recursively, and combines results. [4] [1]
Examples: Merge sort, quicksort, binary search, Strassen's matrix multiplication, closest pair
of points. [1] [2]

Decrease and Conquer (Reduce Size)


Reduces instance size by constant or fixed factor, solves smaller instance, extends solution. [2]
Examples: Insertion sort, binary search (iterative), DFS/BFS graph traversal, Euclid's GCD. [2]

Transform and Conquer (Instance Simplification)


Transforms problem for easier solving via instance simplification, representation change, or
reduction. [3] [2]
Examples: AVL trees (representation), Gaussian elimination (simplification), heapsort. [5]

Greedy
Makes locally optimal choices at each step, hoping for global optimum. [4] [1]
Examples: Prim's/MST Kruskal's spanning tree, Dijkstra's shortest path, Huffman codes,
fractional knapsack, activity selection. [1]
Dynamic Programming
Solves overlapping subproblems with optimal substructure, using memoization or tabulation. [4]
[1]

Examples: Fibonacci (memoized), 0/1 knapsack, longest common subsequence, matrix


chain multiplication, Bellman-Ford. [4]

Backtracking / Branch and Bound


Systematically explores solution space, prunes invalid paths; branch-and-bound adds bounding
for optimization. [3] [5]
Examples: N-Queens, subset sum, 8-puzzle, traveling salesman variants. [2]
⁂

1. [Link]
2. [Link]
3. [Link]
4. [Link]
5. [Link]
6. [Link]
7. [Link]
8. [Link]
9. [Link]
10. [Link]
11. [Link]
12. [Link]
13. [Link]
14. [Link]
15. [Link]

You might also like