NiNi's Den

Advance-Algorithm::homework2

Word count: 443Reading time: 3 min
2017/11/15 Share

Continue…

3. Given an integer (not necessary a decimal number) with n digits, we want to remove $m (\le n)$ digits from this number such that the resulting number is as large as possibe. Design an $O(n)$ time algorithm to solve it.

Example :
n = 5612398752 (decimal)
When m = 2, answer should 62398752
When m = 3, answer should be 6398752
It’s easy to find out that we should care about most significant digit.

Algorithm :

4. Given a 2-dimensional nn array (or matrix) of 0/1 integers, design a linear time algorithm to find a sub-square (a sub-square matrix with consecutive indices in both dimensions) with the largest size such that all the elements in the sub-square are equal to 1.

5. Use the standard divide-and-conquer stratege to solve the max substring sum problem discussed in Unit 4; i.e. divide the given sequence evenly and then solve the two subproblems recursively. Is it still possible to solve the problem in linear time?

6. Let x1, x2, … , xn be a sequence of real numbers (not necessarily positive). Design an algorithm to find a substring xi , xi+1, …, xj such that the product of the numbers in it is maximum over all substrings. The product of the empty substring is defined as 1.

7. Given a sequence of real numbers x1, x2, …, xn (not necessarily positive), n  1, and an integer L, 1  L  n, design an algorithm to find a substring xi, xi+1, …, xj such that its length ji+1 L and the sum of the numbers in it is maximum over all substrings with length not greater than L. Your algorithm should run in O(n) time (note: not O(nL)).

8. Given a sequence of objects where each object is associated with a value and a weight, design an algorithm to find a subsequence such that its corresponding value sequence is increasing and its weights’ sum is maximized.

9. Design an algoritm to solve Problem 10154 “Weights and Measures” in the web site: http://acm.uva.es/problemset/.

10. Given a 2-dimensional nn matrix M of real numbers, design an efficient algorithm to find a sub-rectangle such that the sum of the numbers in it is maximal over all sub-rectangles of M. Here, each sub-rectangle is an n1n2 (1 n1, n2  n) matrix with consecutive indices of rows and columns.

#####11. Given a sequence of integers, and k another integer, design an algorithm to find a substring such that the sum of the numbers in it is exactly k if there does exist such a substring.


Original Author: Terrynini

Original link: http://blog.terrynini.tw/en/Advance-Algorithm-homework2/

Publish at: November 15th 2017, 2:58:55

Copyright: This article is licensed under CC BY-NC 4.0

CATALOG
  1. 1. 3. Given an integer (not necessary a decimal number) with n digits, we want to remove $m (\le n)$ digits from this number such that the resulting number is as large as possibe. Design an $O(n)$ time algorithm to solve it.
  2. 2. 4. Given a 2-dimensional nn array (or matrix) of 0/1 integers, design a linear time algorithm to find a sub-square (a sub-square matrix with consecutive indices in both dimensions) with the largest size such that all the elements in the sub-square are equal to 1.
  3. 3. 5. Use the standard divide-and-conquer stratege to solve the max substring sum problem discussed in Unit 4; i.e. divide the given sequence evenly and then solve the two subproblems recursively. Is it still possible to solve the problem in linear time?
  4. 4. 6. Let x1, x2, … , xn be a sequence of real numbers (not necessarily positive). Design an algorithm to find a substring xi , xi+1, …, xj such that the product of the numbers in it is maximum over all substrings. The product of the empty substring is defined as 1.
  5. 5. 7. Given a sequence of real numbers x1, x2, …, xn (not necessarily positive), n  1, and an integer L, 1  L  n, design an algorithm to find a substring xi, xi+1, …, xj such that its length ji+1 L and the sum of the numbers in it is maximum over all substrings with length not greater than L. Your algorithm should run in O(n) time (note: not O(nL)).
  6. 6. 8. Given a sequence of objects where each object is associated with a value and a weight, design an algorithm to find a subsequence such that its corresponding value sequence is increasing and its weights’ sum is maximized.
  7. 7. 9. Design an algoritm to solve Problem 10154 “Weights and Measures” in the web site: http://acm.uva.es/problemset/.
  8. 8. 10. Given a 2-dimensional nn matrix M of real numbers, design an efficient algorithm to find a sub-rectangle such that the sum of the numbers in it is maximal over all sub-rectangles of M. Here, each sub-rectangle is an n1n2 (1 n1, n2  n) matrix with consecutive indices of rows and columns.