A note on Useful Algorithmic Strategies Kun-Mao Chao (趙坤茂)



Yüklə 1,05 Mb.
tarix08.08.2018
ölçüsü1,05 Mb.
#61784


A Note on Useful Algorithmic Strategies

  • Kun-Mao Chao (趙坤茂)

  • Department of Computer Science and Information Engineering

  • National Taiwan University, Taiwan

  • WWW: http://www.csie.ntu.edu.tw/~kmchao


Greedy Algorithm

  • A greedy method always makes a locally optimal (greedy) choice.

    • the greedy-choice property: a globally optimal solution can be reached by a greedy choice.
    • optimal substructures


Huffman Codes (1952)



Huffman Codes



An example



Divide-and-Conquer

  • Divide the problem into smaller subproblems.

  • Conquer each subproblem recursively.

  • Combine the solutions to the child subproblems into the solution for the parent problem.



Merge Sort (Invented in 1938; Coded in 1945)



Merge Sort (Merge two solutions into one.)



Merge Sort



Dynamic Programming

  • Dynamic programming is a class of solution methods for solving sequential decision problems with a compositional cost structure.

  • Richard Bellman was one of the principal founders of this approach.



Two key ingredients

  • Two key ingredients for an optimization problem to be suitable for a dynamic-programming solution:



Three basic components

  • The development of a dynamic-programming algorithm has three basic components:

    • The recurrence relation (for defining the value of an optimal solution);
    • The tabular computation (for computing the value of an optimal solution);
    • The traceback (for delivering an optimal solution).


Fibonacci numbers



How to compute F10



Tabular computation

  • The tabular computation can avoid recompuation.



Longest increasing subsequence(LIS)

  • The longest increasing subsequence is to find a longest increasing subsequence of a given sequence of distinct integers a1a2…an .



A naive approach for LIS

  • Let L[i] be the length of a longest increasing subsequence ending at position i.



A naive approach for LIS

  • L[i] = 1 + max j = 0..i-1 {L[j] | aj < ai}



An O(n log n) method for LIS



An O(n log n) method for LIS

  • Define BestEnd[k] to be the smallest number of an increasing subsequence of length k.



Binary search

  • Given an ordered sequence x1x2 ... xn, where x1, and a number y, a binary search finds the largest xi such that xi< y in O(log n) time.



Binary search



Longest Common Subsequence (LCS)

  • A subsequence of a sequence S is obtained by deleting zero or more symbols from S. For example, the following are all subsequences of “president”: pred, sdn, predent.

  • The longest common subsequence problem is to find a maximum-length common subsequence between two sequences.



LCS

  • For instance,

  • Sequence 1: president

  • Sequence 2: providence

  • Its LCS is priden.



LCS

  • Another example:

  • Sequence 1: algorithm

  • Sequence 2: alignment

  • One of its LCS is algm.



How to compute LCS?

  • Let A=a1a2…am and B=b1b2…bn .

  • len(i, j): the length of an LCS between a1a2…ai and b1b2…bj

  • With proper initializations, len(i, j)can be computed as follows.











Longest Common Increasing Subsequence



Yüklə 1,05 Mb.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2024
rəhbərliyinə müraciət

    Ana səhifə