problem 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.
problem 4
Given a 2-dimensional nn 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.
problem 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?
problem 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.
problem 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 ji+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)).
problem 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.
problem 9
Design an algoritm to solve Problem 10154 “Weights and Measures” in the web site: http://acm.uva.es/problemset/.
problem 10
Given a 2-dimensional nn 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 n1n2 (1 n1, n2 n) matrix with consecutive indices of rows and columns.
problem 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.