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

1. Bubble Sort 氣泡排序法（bubble sort）是排序演算法（sorting algorithm）中較簡易的一種。 其運作的原理是藉由逐次比較相鄰的兩筆資料，並依照排序條件（由大至小或由小至大）交換資料直到排序完成為止。 FOR( i=n to 0) do:        FOR (j = 0 to n-1 ) do:             if (A[j] > A[j+1])                 SWAP(A[j], A[j+1]) 2. Selection Sort FOR(i=0 to n) do:     FOR(j = i+1 to n) do:           if (A[i] > A[j]):               SWAP(A[i], A[j]) 每次產生最小的在序列的最左邊。 3. Merge Sort 4. Bucket Sort 5. Quick Sort

自己想到遞迴的解法，但效能不是說很好。 讓head->next = func(head->next)，如果下一個和當前一樣就return func(head->next)，

首先先用兩個指針來維護此Linked List，一個叫做pre、一個叫做cur。 而temp就是每次處理的對象，要將往前指，所以temp是cur->next。 cur做的是每一次的遍歷，遍歷目標在temp下一個。 temp下一個就是尾巴，尾巴就是pre->next。 pre做的是就是複雜尾巴的部分，每次結束把temp給他。而pre->next就是temp。 另外一個方法是：一開始用TempList儲存處理的對象(一開始尾巴是NULL)，遍歷head。 尾巴等於tail，TempList assign給tail。TempList 等於頭，頭等於頭->next。TempList下一個等於tail。一直循環直到head == NULL

2. 白板題給一個 8-bit size的值求最高位元是在第幾個bit 3. SET BIT(n) = 1, CLEAR BIT(n) = 0 寫function 把某個數的第x個bit改成1或0 (改成1直接用or、改成0用mask 之後and) 4. 判斷是否是2的次方 5. 判斷一整數是偶數還是奇數     return x & 1; //回傳1odd, 0 even; 6. 請擷取出Input中的第七個bit值?     return (x & 64(1000000)) >> 6;     return (x >> 6) & 1 7. 請擷取出Input中的第N個bit值?     int Get_N_bit(int x, int n){          return (x >> (n-1)) & 1     } 8. 計算有幾個位元是 1    for (; n !=0; n >>= 1) if (n&1 == 1) ++i int  count_bits2(unsigned  int  n) {        int  i= 0 ;        for  ( ; n !=  0 ; n >>=  1 )            if  (n &  1 )               ++i;        return  i;   }