Note to self

1-1. [3] Show that a + b can be less than min(a, b). a = -2 , b = -3 1-2. [3] Show that a × b can be less than min(a, b). a = -2, b = 3 1-3. [5] Design/draw a road network with two points a and b such that the fastest route between a and b is not the shortest route. a ----------- c ----------- b \ / \--------- d ---------- / a->c->b 只要三十分鐘。距離比較遠。 a->d->b 比較近，但因為塞車，花35分。 1-5. [4] The knapsack problem is as follows: given a set of integers S = {s1, s2, . . . , sn},  and a target number T, find a subset of S which adds up exactly to T. For example,  there exists a subset within S = {1, 2, 5, 9, 10} that adds up to T = 22 but not  T = 23. Find counterexamples to each of the following algorithms for the knapsack problem. That is, giving an S and T such that the subset is selected using the algorithm does not leave the knapsack completely full, even though such a solution exists. (a) Put the elements of S in the knapsack in left to right order if

I - 1. Introduction to Algorithm Design        An algorithm is a procedure to accomplish a specific task. An algorithmic problem is specified by describing the complete set of instances it must work on and of its output after running on one of these instances.  //透過完整的instances且用輸入輸出描述整個算法 Robot Tour Optimization Input: A set S of n points in the plane. Output: What is the shortest cycle tour that visits each point in the set S? 很直覺得想法是用每次尋找距離最近的那個點，但這個方法有以下的問題： 我們會發現這個方法不是最佳解，如果0作為起點，此算法將會一直"左右左右"走。 書中提到第二個想法，每次重複地連接一組端點成edge，這一組pair是其中兩點最近的edge，終止條件是形成了一個cycle。最後再連接兩組終點形成一個cycle。 這是著名的travel salesman problem，暴力解方法是每次從起點去尋找其他n-1個點的可能，所以是(n-1)! OptimalTSP(P)     d = ∞      For each of the n! permutations Pi of point set P        If (cost(Pi) ≤ d) then d = cost(Pi) and Pmin = Pi        Return Pmin 1.2 Selecting the Right Jobs Problem: Movie Scheduling Problem Input: A set I of n intervals on the line. Output: What is the largest subset of mutually non-overlapping intervals wh