1. Home
  2. Flashcards
  3. Preview

CSC_Final algorithms

  1. GreedyReversalSort( )
  2. BreakpointReversalSort( )
  3. Sorting by unsigned reversals:
    • NP-hard
    • can be approximated within a constant factor
  4. Sorting by signed reversals:
    can be solved in polynomial time
  5. DCJSORT(A,B)
  11. Sorting by DCJ rearrangements
    can be solved in polynomial time
  12. Reversal Distance Problem
  13. Complexity of sorting by reversals is
    NP hard
  14. PatternMatching(p,t) brute force
  15. BreakPoint Reversal Sort
  16. ImprovedBreakpointReversalSort(pi)
  17. BruteForceMotifSearch
  18. MedianStringSearch (DNA, t,n,l)
  19. Building a keyword tree is done in:
    • O(N) time
    • N= kn is length of all the patterns
  20. Building a keyword tree (with naive threading) is done in:
    O(N+nm)
  21. Building a keyword tree (with Aho-Corasick algorithm) is done in:
    O(N+m)
  22. Runtime for a suffix tree
    O(N+m)
Author
saucyocelot
ID
363701
Card Set
CSC_Final algorithms
Description
Algorithms possibly on the final
Updated

  1. Home
  2. Flashcards
  3. Preview