※ [本文轉錄自 b875060xx 看板]
作者: ladios (星空、拖鞋、妳我) 看板: b875060xx
標題: Algorithm 考古題
時間: Fri Nov 19 23:25:45 1999
Algorithms Mid-term Exam April 19, 1999
1. Define the following terms:
1) Randomized algorithm (3%)
2) Las Vegas algorithm (3%)
3) Monte Carlo algorithm (3%)
4) ~O(g(n)) (6%) p.s. '~' is on the top of 'O'
2. T(n) <= 2T(n/2) + cn log(n)
Prove: T(n) = O(n(log(n))^2) (10%)
3. The closest-pair problem is to find the two points that are closest
together among a set of points in the plane. Informally describe a
divide-and-conquer algorithm to solve this problem.
The time complexity of your algorithm may satisfy the recurrence
relation in problem 2. (15%)
4. Sketch the process of a greedy algorithm in solving the job sequencing
problem below.
(p1, p2, p3, p4, p5, p6, p7) = (3, 5, 20, 18, 1, 6, 30)
(d1, d2, d3, d4, d5, d6, d7) = (1, 3, 4, 2, 2, 1, 2) (10%)
5. Here is a resource allocation problem:
3 projects, 3 units of resource,
N(i, j) = profit resulting from allocating j units of resource
to project i.
N(1, 1) = 1, N(1, 2) = 2, N(1, 3) = 3
N(2, 1) = 2, N(2, 2) = 2, N(2, 3) = 3
N(3, 1) = 2, N(3, 2) = 3, N(3, 3) = 3
1) Represent the problem as a multistage graph. (10%)
2) Write the recurrence relation for the multistage graph problem and
solve the problem in part 1) step by step. (10%)
6. Show how you use set approach dynamic programming to solve the following
0/1 knapsack problem step by step and give your answer to the problem.
m = 20
(u1, u2, u3, u4) = (10, 15, 6, 9)
(p1, p2, p3, p4) = ( 2, 5, 8, 1) (10%)
7, Let A and B be matrices of dimension m*n and n*p respectively. The
product C = A*B an m*p matrix, can be computed using mnp multiplications.
Let M1*M2*...*Mr be a chain of matrix products, where Mi, 1 <= i <= r,
has dimension D(i-1)*D(i) (i.e. D(i-1) rows and D(i) columns). Let Mij
denote the product Mi*Mi+1*...*Mj and C(i, j) be the cost of obtaining
an optimal product sequence for Mij. Observe that C(i, i) = 0,
1 <= i <= r, and that C(i, i+1) = D(i-1)D(i)D(i+1), 1 <= i < r.
1) Give the recurrence relation for C(i, j), i < j (10%)
2) Sketch (or describe) how to solve the recurrence relation for C(1, r).
Your algorithm should be of complexity O(r^3). (10%)
--
有看不懂的地方請告訴我，加油囉！
--
_ _ _
| | | (_)
| | __ _ __| |_ ___ ___
| |/ _` |/ _` | |/ _ \/ __|
| | (_| | (_| | | (_) \__ \
|_|\__,_|\__,_|_|\___/|___/
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: ntucst.csie.ntu.edu.tw
--
狐狸說：「你為你的玫瑰耗掉很多時間，
你的玫瑰才變得如此重要！」
「人類已忘掉這個真理，可是你千萬別忘記。
你對自己馴服的東西永遠有責任，你該為你的玫瑰負責。」
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: ntucsa.csie.ntu.