| 作者 |
 台湾大学博士班入学考试试题 (转贴) -- 借本试题做海归黄埔军校入学考试, 高人大比武现在开始! |
 |
| 所跟贴 |
台湾大学博士班入学考试试题 (转贴) -- 借本试题做海归黄埔军校入学考试, 高人大比武现在开始! -- 安普若 - (3376 Byte) 2003-9-28 周日, 11:57 (1675 reads) |
安普若
[博客]
[个人文集]
头衔: 海归元勋
声望: 大师
性别: 
加入时间: 2004/02/21
文章: 26038
来自: 中国美国的飞机上
海归分: 4196257
|
|
|
作者：安普若 在 海归黄埔军校 发贴, 来自【海归网】 http://www.haiguinet.com
國立台灣大學 八十七 學年度 博士班入學考試試題
科目：計算機理論
1. (25 points) (1) Starting at point 0, you can either move one unit to the right, one unit to the left, or stay put. What is the number of ways you can reach the point m after n moves, where 0 < m < n. (For simplicity, you may assume m + n is even here.) (2) Write down a “compact” rational function in x (a generating function, so to speak) such that the coefficient of xm (m = ..., -2, -1, 0,1, 2.... ) is precisely the answer to (1)
2. (25 points) (1) Take an economy in which an asset price moves in the following manner. At a price of p, an integer, it has probability 1/2 of moving to p + 1 and probability 1/2 of staying at p. Suppose the price starts at 0 at time zero. What is its expected price, E, at time n? (2) If you have $1 at time zero, is there a way to invest in the above-mentioned asset so that you end up with more than E dollars on the average at time n? Argue your points. Note that you have a total of n decisions to make and your strategy should be such that it does not know future prices.
3. (25 points) Briefly explain why the lower bound for various sorting techniques based only on comparisons between input elements is Ω(nlogn). (Hint: Use Stirling's approximation n! > (n/e)n, where e @ 2.71828....) Then, informally describe a sorting algorithm that needs time in an order strictly less than 0(nlogn).
4. (25 points) Consider the problem of making change for n cents using the least number of coins.
(a) (5 points) Give a greedy algorithm to make change for the coin system consisting of quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (I cent). Prove that your algorithm yields an optimal solution.
(b) (10 points) Do you think that the above greedy algorithm always works for any coin system. (where a coin system is a set of coins with different values)? Why? If yes, prove your answer. If not, characterize some properties of the coin system that would invalidate the greedy algorithm.
(c) (10 points) Suppose our coin system has a set of coins with the following values: c0, cl...., ck for some integers c > I and k > 1. Show that the greedy algorithm always yields an optimal solution.
作者：安普若 在 海归黄埔军校 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
 |
|
| |
|
|
|
您不能在本论坛发表新主题, 不能回复主题, 不能编辑自己的文章, 不能删除自己的文章, 不能发表投票, 您 不可以 发表活动帖子在本论坛, 不能添加附件不能下载文件, |
|
|
