# Coursera - Princeton Algorithms - Part 1 of 2

01 Oct 2015Algorithms (Part I) - Princeton

`Week1 Union Find`

`Week2 Stacks, Queues, Bags`

- loitering - references to objects that are no longer used
- stack implmented as array
- resizing array at 1/4 and 1/2 full
- constant amortized time overall

- queues - linked list and array implementation
- generics - used for linked list - Stack
s = new Stack (); - make stack implementation Iterable
- sorting
- Java using a callback by implementing a Comparable interface
- selection sort
- find smallest, swap w/ I, increment I => N*N/2 compares

- insertion sort
- compare 2 elements
- everything to the left of the current element is swapped until smaller than left element => N*N/4 compares
- linear time for partially sorted arrays

- shell sort
- h-interleaved sorting, good approach for 3x + 1 increments => N ^ 3/2
- last sort is basically 1-interleaved which is in fact insertion sort

- shuffle swap
- knuth shuffle swap I and random number < I

- convex hull = smallest area that encloses the points
- Graham scan

`Week 3 Sorting methods`

- Merge sort
- copy initial array (can be optimizeds), then each compare each half array and put smallest element in initial array, by incrementing either i (index in 1st half) or j (index in the 2nd half)
- N log_2 N
- uses 2 x N memory
- too complicated for small arrays
- Bottom up merge: 2 for loops which merge subarrays from 2 elements to N/2
- is stable
- computational complexity
- for mergesort, upper bound == lower bound => optimal regarding complexity, not optimal regarding space
- Comparators -> implements Comparable; Comparator -> alternate sorting

- Quick sort
- in place sorting
- is not stable
- 1.39 N log N (avg); N * N /2 worst case
- insertion sort still preferred for small arrays

- shuffle: swap i and r, where r is a random between 0 and length(array)
- stable sort: insertion sort and merge sort
- not-stable sort: quicksort, selection sort and shell sort - long distance exchanges of elements (keys) with equal values
- mergesort
- makes N/2 * lg N to N * lg N compares

- quicksort
- average case is 1.39 * N * lg N => 39% more comparisons than mergesort
- does less data movements, thus is faster than mergesort
- in -place, no extra space as compared to mergesort
- not stable
- extra: 3way partitioning, all items equal in a partition

- quickselect: linear time
- java Arrays.sort() implemented using quicksort for primitive types or mergesort for objects
- 3way quicksort + randomized => linear sorting for a broad class of apps (from linearithmic)
- not quadratic when more equals keys

- heapsort: N * lg N, in-place in worst case, not stable, poor use of cache memory (worst case 2N log N)
- priority queues
- complete binary tree: tree balanced except for lowest level
- binary heap, can be implemented in an array, root is @ A[1], A[0] empty
- implicit implementation as a tree

- sorting used in variety of situations

`Week 4 - Priority Queues`

- priority queues used in A* search, data compression huffman, bayesian spam filter
- min or max PQ
- binary heap
- using complete binary tree (all levels but last are full) height is log N
- largest key is root of tree (for max heap variant)

- heap sort
- N log N worst case sorting time, in place sorting
- bad for caching, not stable

- using complete binary tree (all levels but last are full) height is log N
- symbol tables
- in simple implementation (ibnary search, array) linear operations for insert
- we can create an ordered Symbol Table by adding Comparable (Key Comparable
)

- BST (Binary Search Tree)
- binary tree in symmetric order
- tree shape depends on order of insertion
- if random distinct keys are inserted then number of compares is 2 log N (ln)

- search and insert are linearithmic 1.39 log N
- inorder traversal gives us keys in ascending order
- Hibbard deletion - special if it has 2 nodes, replace with minimum from right subtree
- after lots of deletions, tree becomes less balanced
- sqrt(N) for deletions

- Binary Search Tree (BST) - explicit implementation as tree: key, value, reference to left / right sub-tree - smaller/greater - search and insert are 1.39 lg N for BST in average case, and N in worst case - deletion takes sqrt(N)

`Week 5 - Balanced Sort Trees`

- 2-3 trees
- (2-3 tree): tree can have either 2 or 3 leaves and node can have 1 or 2 keys,
- with middle leaf key value being between the the 2 keys
- insertion we temporarily create 4 leaves/3 nodes node for which the middle element goes up the tree
- there might be cases when height increases if top node is already a 3 node

- all transformations maintain symmetry and perfect balance
- 18-30 max height for billions of nodes
- all operations are c * log N, constant time - c, depends on implementation (c lg N, so base 2)

- (2-3 tree): tree can have either 2 or 3 leaves and node can have 1 or 2 keys,
- Red Black BST
- LLRB - Left Leaning Red-Black BST
- search works the same as in the BST
- rotate left operations to move a right-leaning RED link and make it lean left
- rotate right and flip colors (when 2 RED links are coming out of the same node)
- search/insert/delete 2* lg N, max height 2 * lg N

- B-tree
- generalized version of 2-3 tree
- allow up to M-1 keys per node
- when node is full we split it
- at most log M/2 N for search

- Java: TreeMap and TreeSet are implemented using RedBlack-tree
- in databases, filesystems B trees
- Hash Tables
- each type of data depends on type of data
- hashCode returns 32bit int, equal() and hashCode() should be equal
- for String - each char * 31 (or a small prime number) + prev_value
- if array, use for each element to get the hashCode
- make it positive ( & 0xffffâ€¦) and do % M (where M is the size of the array)