Morris' Blog

2013-11-16 18:08:21Morris

[高等演算法][作業二] 討論

留言 0 收藏 0 推薦 0

前略

3. Given an integer (not necessary a decimal number) with n digits, we want to remove m ( n)
digits from this number such that the resulting number is as large as possibe. Design an O(n)
time algorithm to solve it.
4. Let x1, x2, … , xn be a sequence of integers and k be another given integer. Design an algorithm
to find a subsequence xi , xi+1, …, xj (of consecutive elements) such that the sum of the numbers
in it is exactly k if there does exist such a subsequence.
5. 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.
6. Given an undirected graph G, a vertex subset I is called an independent set of G if for every
pair of vertices u and v in I, uv  E(G). The independent set problem is to find an independent
set with maximum size. Design a linear time algorithm to solve the problem on undirected
trees. Can you extend your algorithm to solve the weighted case? (That is, each node is
associated with a positive weight, and you are asked to find an independent set with maximum
weight sum.)
7. 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.
8. 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)).
9. 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.
10. Design an algoritm to solve Problem 10154 “Weights and Measures” in the web site:
http://acm.uva.es/problemset/.