Morris' Blog

2013-11-16 18:14:19Morris

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

留言 0 收藏 0 推薦 0

1. Given a 2-dimensional nn matrix of 0/1 integers, design a linear time algorithm to find a subrectangle
with the largest size such that all the elements in the sub-rectangle are equal to 1.
2. Improve the space utilization in the algorithm of solving the 0/1 knapsack (sum-of-subsets)
problem discussed in the class.
3. Solve each of the following variations of the 0/1 knapsack problem (sum-of-subsets):
a) Pack items of given sizes in a given-sized knapsack fully, but there is an unlimited supply
of each item.
b) The assumptions are the same as in v1 (n items, unlimited supply, fixed-sized knapsack),
but now each item has an associated value. Design an algorithm to find how to pack the
knapsack fully, such that the items in it have the maximal value among all possible ways to
pack the knapsack.
c) The assumptions are the same as in v2 (n items with sizes and values, unlimited supply,
fixed-sized knapsack, and the goal of maximizing the value), but now we are not restricted
to filling the knapsack exactly to capacity. We are interested only in maximizing the total
value, subject to the constraint that there is enough room for the chosen items in the
knapsack.
4. Design an algoritm to solve Problem 10482 “The Candayman Can” in the web site:
http://acm.uva.es/problemset/.
5. Design an algoritm to solve Problem 10261 “Ferry Loading” in the web site:
http://acm.uva.es/problemset/.
6. Solve the even partition problem: Given a list of n positive integers, partition the list into two
sublists, each of size n/2 or n/2, such that the difference between the sums of the integers in
the two sublists is minimized.
7. Given a set of n sticks of various lengths, design an algorithm to determine if it is possible to
join them end-to-end to form a square.
8. Suppose you have one machine and a set of n jobs a1, a2, … , an to process on that machine.
Each job aj has a processing time tj, a profit pj, and a deadline dj. The machine can process only
one job at a time, and job aj must run uninterruptedly for tj consecutive time units. If job aj is
completed by its deadline dj, you receive a profit pj, but if it is completed after its deadline, you
receive a profit of 0. Give an algorithm to find the schedule that obtains the maximum amount
of profit. For each of the following special case, is it possible to find a more efficient algorithm
(comparing to the general case.)?
a) Each job has the same processing time.
b) Each job has the same profit.
c) Each job has the same deadline.
9. Given a weighted directed acyclic graph (DAG; a directed graph is acyclic if it contains no
directed cycles), and a pair of vertices u and v, design an algorithm to find a longest and a
shortest path from u to v. Here, the length of a path is defined as the sum of weights of edges in
the path.
10. Given a weighted directed graph G=(V, E), design an algorithm to detect if G contains a
negative cycle. Moreover, if G contains no negative cycles, design an algorithm to find a cycle
in G of minimum weight.