• Given a series n matrices compute A1*A2*...*An . Determine where to place parentheses to minimize the number of multiplications.
  • The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, the length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is 6 and LIS is {10, 22, 33, 50, 60, 80}. Use dynamic programming to design an effective algorithm for LIS
  • Given a set of integers, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum.
  • Prove that edit distance is metric (that is, it is nonnegative, zero only if the words are equal, symmetric and satisfies the triangle inequality)
  • Show a way to reduce memory use of the Knuth's algorithm to O(m+n)
  • Extend the algorithm to also output edit distance.  Try to do that also for the O(m+n) variant.
Последнее изменение: среда, 13 мая 2020, 21:31