Advance-Algorithm::homework2

Algorithm

Word count: 420Reading time: 2 min

 2017/11/15

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 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.

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 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)).

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 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.

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.