Key Concepts Flashcards
Infix, Postfix and Prefix of expressions
an expression has operands and operators. If we depict them in a tree with a parent node bing operator and children node being operands, e.g. A+B , then we traverse the tree
1) pre-order: we get prefix representation + A B
2) In-order: we get infix representation A+B
3) post-order: we get postfix representation: A B +
How are Recursive and FILO Stack are related
1) call stack is a “stack ADT” and Recursive calls is realized using stack.
2) expression evaluation is done via stack ADT
Thus in a recursive call, consider the call as an “operator”, the input and the result are the operand.
For example, for a max(a, b) function, let’s consider ‘max’ as an operator:
Thus, max([1,2,3,4.5, 6]) = max([max(1,2,3]), max([4,5,6})
T(n) = 2(T(n/2)) + 1; = O(n)
Recursive:
T=max([1,2,3,4.5, 6]) = max([max(1,2,3]), max([4,5,6})
Stack
T=max(1, max(2, max(3, max(4, max(5, 6)))));
then we can see operator ‘max’ is pushed onto operator stack 5 times –> recursive depth is 5
In single-linked list what are the special considerations?
==============================
OPTION 1: always keep H & T mod of N
Baseline: H(dequeue), T(enqueue) only increments
use size to indicate full/empty instead using H/T relationship (easier for both array or linked list impl)
N is capacity
Enqueue: T = (T+1)%N
Dequeue: H = (H+1)%N
Queue to be empty: H’s next position is T (H+1)%N=T
Queue to be full: T’s next free slot is (T+1)%N=H
so
T=H where H!=null means full
T=H where H is null means empty
=================================
OPTION 2: let H & T grow forever, but do the MOD
when accessing elements.
Enqueue: T = (T+1)
Dequeue: H = (H+1)
Start T=-1, H=0
Queue to be empty: H > T (H grows more)
Queue has 1 element H=T
Queue to be full: T-H+1 == N (T grows more)
Java LinkedList<> Iterator::next() keeps track of lastReturned
hasNext() {
lastReturned->next != null;
}
next() {
lastReturned = lastReturned->next;
return lastReturned;
}
In hasNext() which is faster?
hasNext() {
return cursor < size;
}
hasNext() {
return lastReturn->next != null;
}
Java uses
hasNext() {
return cursor < size;
}
When writing code involving linked lists, we must always be careful to properly handle
the exceptional cases (when the linked list is empty, when the list has only one or two nodes) and the boundary cases (dealing with the first or last items). This is usually much trickier than handling the normal cases.
1.3 ■ Bags, Queues, and Stacks 165
Queue and Linked Lists
Queue: Linked List (FIFO)
Dequeue (double-ended queue) Double Linked List (both ends can add/remove)
Stequeue: (stack-like queue) Linked List (one end can add/remove, the other end can only add)
Tilda Notation/Approxation ~f(n)
~f(n) is that f(0) is approximate the Running time T(n) dropping lower order terms and constant factor
Tilda Notation/approximate is an alternate form of O(f(n))
Function and order of growth
constant 1 logarithmic log N linear N ***linearithmic*** N log N quadratic N ^ 2 cubic N ^ 3 exponential 2 ^ N
-
Pointer/Address width and Padding
In 32-bit system, pointers are 4-byte integers aligned on 4-byte boundary. Thus if you malloc() 1 byte, at lest 4 bytes will be allocated with 3 byte padding
In 64-bit system, pointers are 8-byte integers aligned on 8-byte boundary. Thus if you malloc() 1 byte, at lest 7 bytes will be allocated with 7 byte padding
in C (char*) pointer can align on byte boundary In Java (byte) primitive type can align on byte boundary
“premature optimization is the root of all evil” By Hoare the inventor of quick sort
Here the “optimization” means trying to optimize lower-order terms or constant factor (which are all too much system dependent)
Going from O(n^3) to O(nlgn) is not “optimization” it is a different algorithm altogether.
In algorithm, watching out for Overflow cases E.g. if adding two (large) number overflows, will your algorithm still work?
Three-sum example
