1. Home
  2. Flashcards
  3. Preview

CSC_Final algorithms

  1. GreedyReversalSort(Image Upload 1 )
    Image Upload 3
  2. BreakpointReversalSort(Image Upload 4 )
    Image Upload 6
  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)
    Image Upload 8
  6. Image Upload 10
    Image Upload 12
  7. Image Upload 14
    Image Upload 16
  8. Image Upload 18
    Image Upload 20 Image Upload 22
  9. Image Upload 24
    Image Upload 26 Image Upload 28
  10. Image Upload 30
    Image Upload 32
  11. Sorting by DCJ rearrangements
    can be solved in polynomial time
  12. Reversal Distance Problem
    Image Upload 34
  13. Complexity of sorting by reversals is
    NP hard
  14. PatternMatching(p,t) brute force
    Image Upload 36
  15. BreakPoint Reversal Sort
    Image Upload 38
  16. ImprovedBreakpointReversalSort(pi)
    Image Upload 40
  17. BruteForceMotifSearch
    Image Upload 42
  18. MedianStringSearch (DNA, t,n,l)
    Image Upload 44
  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