1. BRUTE FORCE
|
* Summary
• Strengths – wide applicability – simplicity – yields reasonable algorithms for some important problems (e.g., matrix multiplication, sorting, searching, string matching) • Weaknesses – rarely yields efficient algorithms – some brute-force algorithms are unacceptably slow – not as constructive/creative as some other design techniques |
2. DIVIDE AND CONQUER
1) Merge Sort ① Split array A[0..n-1] in two about equal halves and make copies of each half in arrays B and C ② Sort arrays B and C recursively ③ Merge sorted arrays B and C into array A |
2) Quick Sort
① Select a pivot (partitioning element) –the first element ② Rearrange the list so that all the elements in the first s positions are smaller than or equal to the pivot and all the elements in the remaining n-s positions are larger than or equal to the pivot (see next slide for an example) ③ Exchange the pivot with the last element in the first (i.e., ) subarray ④ Sort the two subarrays recursively |
4) Multiplication of Large Integers
Consider the problem of multiplying two (large) n-digit integers represented by arrays of their digits such as: A = 12525678901357986429 B = 87654321284820912836 |
5) Closest-Pair Problem
Brute force approach requires comparing every point with every other point • Given n points, we must perform 1 + 2 + 3 + … + n-2 + n-1 comparisons. • Brute force O(n2) • The Divide and Conquer algorithm yields O(n log n) • Reminder: if n = 1,000,000 then • n2 = 1,000,000,000,000 whereas • n log n = 20,000,000 |
7) Convex Hull ① Decompose the set of points in equal parts (Qleft and Qright) ② Solve the sub‐problems respectively on Qleft and Qright ③ Merge both convex hulls Hleft and Hright |
|
3. DECREASE AND CONQUER
|
Decrease by one
–Insertion sort –Graph search algorithms: • DFS • BFS • Topological sorting –Algorithms for generating permutations, subsets Decrease by a constant factor –Binary search –Fake-coin problems –multiplication à la russe –Josephus problem Variable-size decrease –Euclid’s algorithm –Selection by partition -Binary search tree |
4. TRANSFORM AND CONQUER Initial Problem -> New Representation -> Solution
This group of techniques solves a problem by a transformation
1) Presorting : Many problems involving lists are easier when list is sorted.
2) Gaussian elimination : Solve the latter by substitutions starting with the last equation and moving up to the first one.
3) Balanced search trees(ex. AVL, 2-3 Tree)
1) Presorting : Many problems involving lists are easier when list is sorted.
2) Gaussian elimination : Solve the latter by substitutions starting with the last equation and moving up to the first one.
3) Balanced search trees(ex. AVL, 2-3 Tree)
4) Heaps and Heapsort ① Build heap ② Remove root - exchange with last(rightmost) leaf ③ Fix up heap - excluding last leaf Repeat 2, 3 until heap contains just one node. 5) Reductions to graph problems Problem 1 to be solved ---reduction---> Problem2 solvable by algorithm A ----algorithmA---> Solution to Problem2---cleanup---> Solution to Problem 1 6) Linear programming One more example of problem reduction. A Linear Program (LP) is a problem that can be expressed as follows (the so-called Standard Form): –minimize (or maximize) cx –subject to • Ax = b • x >= 0 |