SU - 程式學習筆記

Queues Queue A queue is an abstract data type , like a stack. A collection of entities that are maintained in a sequence . First in First out (FIFO) (Source: Data Structures & Algorithms in Java 2nd Edition ) Implements a Queue: class Queue { private int maxSize; private long[] queArray; private int front; private int rear; private int nItems; // constructor public Queue(int s) { maxSize = s; queArray = new long[maxSize]; front = 0; rear = -1; nItems = 0; } // put item at rear of queue public void insert(long j) { // deal with wraparound if(rear == maxSize-1) { rear = -1; } queArray[++rear] = j; // increment rear and insert nItems++; // one more item } // take item from front of queue public long remove() { long temp = queArray[front++]; // get value and incr front // deal with wraparound if(front == maxSize) { front = 0; } nItems--; // one less item return ...

Stack Stack A stack is an abstract data type that serves as a collection of elements. Last in First out( LIFO ). Push , which adds an element to the collection. Pop , which removes the most recently added element that was not yet removed. (Source: Stack (abstract data type) - Wikipedia ) Implements a Stack: class StackX { private int maxSize; // size of stack array private long[] stackArray; private int top; // top of stack // constructor public StackX(int s) { maxSize = s; // set array size stackArray = new long[maxSize]; // create array top = -1; // no items yet } // put item on top of stack public void push(long j) { stackArray[++top] = j; // increment top, insert item } // take item from top of stack public long pop() { return stackArray[top--]; // access item, decrement top } // peek at top of stack public long peek() { return stackArray[top]; } // true if stack is empty public boolean isEmpty() ...

Question: input array: output array: Solution: Bubble Sort: Strategy: Compare two players If the one on the left is taller, swap them Move one position right When you reach the first sorted player, start over at the left end of the line Code: public void bubbleSort() { int out, in; for(out=nElems-1; out>1; out--) { for(in=0; in<out; in++) { if( a[in] > a[in+1] ) { swap(in, in+1); } } } } private void swap(int one, int two) { long temp = a[one]; a[one] = a[two]; a[two] = temp; } Efficiency: O(N 2 ) Selection Sort: Strategy: Making a pass through all the players and picking the shortest one This shortest player is then swapped with the player on the left end of the line, at position 0 The next time pass down the row of players, start at position 1, and, finding the minimum, swap with position 1 This process continues until all the players are sorted Code: public void selectionSort() { in...

Transaction: In software, all-or-nothing operations are called transactions. Transactions allow you to group several operations into a single unit-of-work that either fully happens or fully doesn’t happen. ACID: Atomic: Transactions are made up of one or more activities bundled together as a single unit of work. Atomicity ensures that all of the operations in the transaction happen or that none of them happen. Consistent: Once a transaction ends (whether successful or not), the system is left in a state that is consistent with the business that it models. Isolated: Transactions should allow multiple users to work with the same data, without each user’s work getting tangled up with the others. Therefore, transactions should be isolated from each other, preventing concurrent reads and writes to the same data from occurring. Durable: Once the transaction has completed, the results of the transaction should be made permanent so that they will survive any sort of system crash...

Interface vs Data Structure Interface Data Structure specification representation what data can store how to store data what operations are supported algorithms to support operations problem solution Two main interfaces Sequence Interface Set Interface Sequence Interface Sequences maintain a collection of items in an extrinsic order, where each item stored has a rank in the sequence, including a first item and a last item. By extrinsic, we mean that the first item is ‘first’, not because of what the item is, but because some external party put it there. Sequences are generalizations of stacks and queues, which support a subset of sequence operations. Operation Description Container(general type) build(X) given an iterable X, build sequence from items in X len() return the number of stored items Static(the number of items doesn’t change) iter_seq() return the stored items one-by-one in sequence order get_at(i) return th...

什麼是演算法(Algorithm) ? 演算法是一種處理程序(procedure)，透過輸入參數(input)來，經過一系列的程序，來得到 一個 輸出(output)結果。(ex: 像是數學上的函數(function)，料理的食譜……等等。) 演算法的正確性(Correctness): 如何判斷這個演算法是正確的，可以透過數學上的歸納法(induction)來進行驗證，因為演算法是一種處理程序，不管輸入的值為多少，都只會回傳一個結果，若輸入相同的值，其結果也必定相同，所以對於驗證演算法的正確性來說，只要輸入定義內的值，其返回的結果都成立，其就是一個正確的演算法。 演算法的效率(Efficiency): 由於演算法是一種處理程序，對於相同的問題，事實上是可以有多種演算法來處理，然而哪種演算法才是最好的，其所需探討的就是演算法的效率，演算法的效率取決於電腦的性能與輸入的資料量大小，其中一般在探討效率都著重於輸入的資料量大小，意即對於相同的問題，且相同的資料量大小中，哪種演算法的處理時間最短，花費的時間最短，即是最優的演算法。 漸進符號(Asymptotic Notation): 漸進符號是一種用來表示演算法效率的方法，其中有三種符號，而一般以O(Big-O Notation)來表示。 Notation 簡單描述 O(Big-O) 表示上界(upper bounds) Ω(Big-Omega) 表示下界(lower bounds) Θ(Big-Theta) 表示介於上界與下界(tight bounds) 一些常見的O(f(n)): input Constant Logarithmic Linear log-linear Quadratic n O(1) O(log n) O(n) O(n log n) O(n 2 ) (Source: Daniel Miessler )

GET: GET方法是Idempotent Methods，意即使用者不論向伺服器(Server)發出多少次相同的請求(Request)，伺服器回傳的結果都不會變。 GET沒有message body，其表單(form)參數是直接串接在URL之後(以?區隔)。 (Source: Head First Servlets and JSP ) POST: 與GET相反，POST 不是 Idempotent Methods，使用者對伺服器發出多次相同的請求，雖然是相同請求，但對伺服器來說都是不同的請求。即如果使用者在進行下單服務時，不小心重新整理，會導致伺服器發生重複下單的情況。 POST有 message body，故表單上的參數會被寫入其中。 (Source: Head First Servlets and JSP )