domingo, 7 de abril de 2013

[IT] Card game extra points


  1. Label: "Label all edges heading to the right with a zero and those heading to the left with ones."
  2. Column: "Initialize the first column of M all zero if the first character of the text is not equal to the first character of the pattern."
  3. Binary: "For binary text and a binary pattern"
  4. Rule: "Special rules to save more time by shifting more positions: Bad character rule, Good suffix rule"
  5. Efficient: "Knutt-Morris-Pratt, usually less efficient, but much easier to explain and prove."
  6. Pattern: "
  7. When a substring of the pattern aligns and then there is a mismatch 
  8. at position i, move the pattern i - sp’ i positions to the right.
  9. "
  10. Fuzzy: "
  11. Example: binary input, fuzzy or stuttering output
  12. "
  13. Lossless: "
  14. If all bits of L can be recovered from S, the compression is lossless.
  15. "
  16. Dictionary: "
  17. The dictionary is included in the beginning of the compressed 
  18. file, unless it is implicitly constructed in a standard way
  19. "
  20. Code word: "
  21. Each word is replaced by a (shorter) code word
  22. The code words usually cannot share prefixes
  23. "
  24. Obtain: "
  25. Concatenate the edge labels for the path from the root to a leaf to 
  26. obtain the code word for the symbol at that leaf.
  27. "
  28. Preprocessing: "
  29. The use of shortcut rules generally requires preprocessing.
  30. "
  31. Average: "
  32. Average information content:
  33. "
  34. Logarithm: "
  35. The base of the logarithm is not that crucial; interpret it as units,
  36. base two being the bit (binary digit)
  37. "
  38. Root: "For any leaf i, the labels on the path from the root to that leaf concatenate to exactly the suffix S[i..m]."
  39. Symbol: "
  40. An implicit suffix tree for S is obtained from a suffix tree by 
  41. removing the terminal symbol $ from all edge labels, removing 
  42. any unlabelled edge, and removing subsequently all nodes that 
  43. do not complete at least two children.
  44. "
  45. Equal: "
  46. If the two are equal for a given r and P is of length n, then there is 
  47. a match to P starting at r in T."
  48. Worst case: "
  49. How does this differ from the worst case complexity?
  50. "
  51. Rate: "
  52. The rate of information flow; the maximum value of...
  53. "
  54. Compute: "To compute M( j ), we perform a binary AND on Bit-Shift( j -1) and U ( T ( j ) )."
  55. Correct: "
  56. The probability of correct transmission is denoted as p
  57. "
  58. Optimal: "
  59. Optimal input frequencies
  60. "
  61. Buffer: "
  62. Online compression = the string arrives bit by bit, 
  63. possibly with a limited-capacity buffer
  64. "
  65. Apply: "
  66. We must apply mod p during the computations of the H values 
  67. for this to save us anything at all.
  68. "
  69. Complexity: "
  70. Install and experimentally determine the “typical-case” 
  71. complexity.
  72. "


2 comentarios:

  1. 6 extra en la tercera tarea por el juego de tarjetas de medio curso

    ResponderEliminar
  2. NP en tarea de codificación adaptativa.

    ResponderEliminar