Tom's crazy CS Lab

1. A person has some candies that are of different weight and wants to divide them evenly between 3 children, so that they don't get jealous at each other. He wants to know how bad the fairest distribution is, i.e. what is the minimum difference in the candies weight, of the kid getting the candies of the most total weight and the kid getting the least. For example, assume that he gives the three children candies of weight a>=b>=c, respectlively. The badness of this distribution is a-c. Try your best to solve this problem and analyze the time efficiency of your algorithm.
   
2. Let x1, x2, ..., xn be a sequence of real numbers ( not necessarily positive ) . Design an algorithm to find a subsequence xi, x(i+1), ..., xj ( of consecutive elements ) such that the product of the numbers in it is maximum over all subsequences of consecutive elements. The product of the empty subsequence is defined as 1.
   
3. Give an algorithm to solve the following version of 0/1 knapsack problem. There are n items with different sizes and values, and each item is unlimited supplied. The size of knapsack is K. We are interested in maximizing the total value, subject to the constraint that there is enough room for the chosen items in the knapsack.
   
4. Let T be an undirected tree. The distance between two vertices in T is the length of the path connecting these two vertices ( neighbors have distance 1 ). The diameter of T is the maximal distance over all pairs of vertices. Design an algorithm to find the diameter of the given tree. Assume that T is given in the adjacency list representation.
   

書報討論心得報告

講演主題：數位攝影

主講人：趙樹人

　　我以一個資工人的角色來參加這次的書報，除了來看資訊科技在不同領域的應用情形，也從使用者的角度來得到一些反饋的資訊。資工的知識原本就是一種工具知識，本身不是目的，而是方法。所研究與製作的東西，最終產物其實資工人很少親身接觸，而趙老師算是資工科技的最終受惠者與重度使用者。

　　趙老師以感性的囗吻，講述一個令人為之動容的故事，讓在場的我們了解『紀錄』的意義和重要性。一個偉大的研究學者因為勤於研究，最後雖然獲得成功，但週圍的親友卻缺乏他存在的證明，讓後人惋歎。『紀錄』，或許才是人生令一個重要的意義。

Tom (碩專班)

• 報告

　　這篇文章常識從使用者與文件之間進行的互動 ( 閱讀 & 組織 ) 來自動化建立文件對使用者興趣的價值評估上。

　　作者指出，過去採用讓使用者直接輸入對某份文件的評價的方式，雖然得到的結果較為準確，卻因為人性始終是懶惰的，得到的有效數據往往過於稀少。因為大部分的人發現做這種幫文件打分數的動作，對他們本身並無利益，受惠的往往是後人，所以非常容易放棄，來自一個使用者，被評價過的文件數量遠低於該使用者閱讀過的文件數量。於是，怎樣不經由要求使用者進行評價的動作，直接讓系統經由使用者的閱讀活動，文件組織活動，來自動評比每份文件對該使用者的興趣的價值高低，就是這篇論文要探討的重點。如果這個目的達到，文件資源的評價系統將可更廣泛實施在許多文獻上。

　　這篇論文要利用使用者進行文件歸類的活動來推測文件的價值，相對於對單一文章深入地閱讀，文件分類牽連到：

Tom ( 碩專班 )

• 報告