Please enable JavaScript.

Coggle requires JavaScript to display documents.

CSE373 (Chapter 2 (2.2 Merge Sort (Cost and improvements (We can reduce…

- - - - Resorting
      - Reheaping
  - - - Firstly, build a heap from an unordered array (this step only need to percolate down)
        
        Details: Start from the parent nodes (array.length / 2, which get ride off the leaf nodes), and percolated down with i--
      - Secondly, from N >> 1 (index), swap the root with each node start from the end of the implemented array, and then percolate down.
      - In the end the array will be sorted (depends on the way you define a heap: max to min or min to max)
  - - - O(N^2) ~ O((N-1)N/2 + N)
      - N exchange in the array
      - Pro: minimum exchange (retain the original order) [stable sorting method]
    - - O(N^2 / 2)
      - Best case N-1 check (from 1 -> N) and 0 exchange.
  - - - First copy out an auxiliary array
      - Handle four cases
        
        Left half exhausted / Right half exhausted
        
        Left > Right OR Right > Left
    - - Set two pointers in both left and right set, and choose elements one by one.
    - - Divided by two until low >= hight
    - - Proof: SO answer why O(NlogN) ≈ O(N^2)
    - - We can reduce the running time to be linear for arrays that are already in order by adding a test to skip the call to merge() if a[mid] is less than or equal to a[mid+1]. With this change, we still do all the recursive calls, but the running time for any sorted subarray is linear
      - The memory cost: auxiliary array
      - Addressing improvements that decrease running time just by a constant factor may not otherwise be worthwhile. You need to test the effectiveness of specific improvements by running experiments, as we indicate in exercises throughout.
    - - One of the most interesting improvement is just to use linked-list to link 1,2,4,8,16... arrays to gether
    - - ■ Mergesort is not optimal with respect to space usage.
        ■ The worst case may not be likely in practice.
        ■ Operations other than compares (such as array accesses) may be important.
        ■ One can sort certain data without using any compares.
  - - - Invariant: for index i (left) and j (right), all the items on the left of i are smaller than the pivot, and all the items in the right side of j are greater than the pivot.
      - When any thing "illegal" was found on both boundaries, exchange the i and j items.
        
        This step preserve the invariant.
      - The last step is to change the j-th item and the lowest index item.
      - First shuffle the array! (make sure the array is unsorted)
    - - Cutoff
        
        When there are still 5-15 elements in the array, use Insertion sort.
        
        if (hi <= lo + M) { Insertion.sort(a, lo, hi); return; }
      - Three way partitioning
        
        larger / equal / less
  - - - Select the k-th smallest item (in the left) by partitioning can be linear time
    - - Priority Queue is very handy in choosing Min and Max items
- - - - java: input is .class file (run)
      - more: print file contents
      - javac: input is .java file (compile)
    - - Write function to analysis the performance
    - - Just use the ADT and see if it act normally
  - - - provide access to the values for instance methods to operate them
      - create objects to hold data type values
      - declare variables
    - - accessible through an import statement
      - in the standard Java library
      - .java in the same directory
    - - hashCode()
      - compareTo()
      - equals()
      - toString()
  - - - for (Node x = first; x != null; x = x.next) { }
    - - To implement an iterator
        
        import java.util.Iterator; is needed
      - You need to set the element to be null to let Java's garbage collector recognize the useless elements
      - When the Array is full, double the space
      - When the usage of the Array is less than a quarter, half the Array
    - - a = (Item[]) new Object[cap];
    - - Check size
      - get item
      - Check empty
      - Add item
      - Generate object
    - - This kind of <Item> can help you to handle any kind of primitive type variables, and the auto-wrapper make the saving and extracting data much easier.
    - - A program that interprets the computation specified by a given string and performs the computation to arrive at the result.
    - - Only add and iterator... (FILO order, which is the same as Stack)
    - - Specify an API
      - Develop client code with reference to specific applications.
      - Describe a data structure that can serve as the basis for the instance variables in a class that will implement an ADT that meets the specification in the API.
      - Describe algorithms
      - Analyze the performance characteristics of the algorithms.
  - - - System.currentTimeMillis();
    - - The cost of executing each statement
      - The frequency of execution of each statement
    - - g(N) ~ f(N) >> g(N)/ f(N) ≈ 1 as N grows
    - - Develop an input model, including a definition of the problem size.
      - Identify the inner loop
      - Define a cost model that includes operations in the inner loop
    - - UP
        
        Used in adding, just swap the parents if the current node is smaller than the parent
      - DOWN
        
        Deletion: after deleted the root, take the bottom left node to the root place and swap with the child that is smaller
      - What is a good data structure for a PQ pair?: just node
    - - Make an input generator
      - Double size each time
      - Record the convergence ratio (Print out)
      - In most of the time the ration is limited to 2^b
      - Moore's Law
        
        The speed and the memory of computers in the world will double every 18 months, or x10's faster for every 5 years.
    - - Typical usage
        
        1 byte
        
        boolean
        
        byte
        
        2 bype
        
        char
        
        4 byte
        
        int
        
        float
        
        padding
        
        8 byte
        
        long
        
        double
        
        references
        
        String
        
        16 byte
        
        overhead
      - Be careful when you call other methods in a recursive function, because each call might generate large amount of memory cost for the references.
      - Not all optimizations are to hard code
        
        But don't optimize too early if it takes too much time.
  - - - Find is O(1) because it's just index assigning, but the union is slow: O(N^2)
    - - Why find is 2N+1 runtime? And what is the runtime for union???
- - - - size(x) = size(left) + size(right) + 1
    - - For a successful search, the recursion terminates when the key was found.
      - For an unsuccessful search, the recursion terminates when the null was reached.
    - - Q: How to insert in the middle of the tree?
        
        A: Because insert is always to the bottom, and different trees can have different structure, you just need to insert with normal recursion, and don't need to worry about the subtrees.
        
        The key point is that to reset links and increment counts on the way up.
    - - External path length
        
        Sum of the path length to all the leaves
      - Internal path length
        
        Sum of the path length to each parent node
      - The search and insertion in a BST is about 1.39 * lg(N), which is worth, because in a Binary Search, the insertion is commonly linear O(N).
      - Good thing is that the number of nodes in each subtree is accessible.
      - Delete a node in the middle of a tree (4 steps)
        
        Save the node to be delicate in t
        
        Set x to be it's successor min(t.right). [Because max(t.left) < min(t.right), which means use the min(t.right) as a successor will preserve the properties of a BST
        
        x.right = deletMin(t.right) # make the x/min(t.right) to the new node that replace the hole generated by the deletion of the original node, and remove the x from the t.right as the same time: because the returned value of delectMin is a tree without the minimum node.
        
        x.left = t.left # where t is the old (deleted node) and x is the new (successor) node
      - The deleteMax() method is the same as deleteMin() with right and left interchanged.
      - The average height of a BST built from random keys was shown to be logarithmic by J. Robson in 1979, and L. Devroye later showed that the value approaches 2.99 lg N for large N.
  - - - This algorithm makes big matrix multiplication much faster!
      - The key to understand this is that, we want to only store those non-zero elements, and useing Hash table of key-value pairs to make this possible
      - BST >> Hash table >> non-zero values
  - - - Perfect case
        
        A perfectly balanced 2-3 search tree is one whose null links are all the same distance from the root.
        
        The splitting methods listed in the book will always guarantee that the 2-3 tree is balanced
        
        The only case that a tree will in crease it's height by one is: "3 node root" >> 3 "2 nodes"
        
        "2 Node" can be extended into a "3 node", which can preserve the tree property.
        
        Proposition F:Search and insert operations in a 2-3 tree with N keys are guaran- teed to visit at most lg N nodes.
        
        Proof: the height of a 2-3 tree is between floor(log3 N) = floor[(lg N)/(lg 3)] (if the tree is all 3-nodes) and floor(lg N) (if the tree is all 2-nodes)
      - Def of 2-3 tree
        
        Empty (null)
        
        2-node
        
        3-node
    - - The red link is used to represent the "3-node", and it always lean left
      - The black link is just like a normal BST link, and it preserve the properties of a "perfect" 2-3 tree.
      - A RB-BST is both a 2-3 tree and a BST, which is both balanced and can be searched effectively.
      - The color variable in the Node class is the link color from this link to it's parent
      - Rotation returned Node should point back to the original Node
        
        h = rotateLeft(h);
        
        What are the cases that we will need to rotate the 3-nodes?
        
        When the expanding of a 3-node is in the right side of the original 2-node. Then you can use rotateLeft to preserve the Red-blake tree properties.
        
        How to understand the rotation process for 2-node? (especially the case of three ordered red links)
        
        A:
        
        ■ If the right child is red and the left
        child is black, rotate left.
        ■ If both the left child and its left
        child are red, rotate right.
        ■ If both children are red, flip colors.
      - Properties of red-black BSTs
        
        The height of a red-black BST with N nodes is no more than 2 lg(N)
        
        The worst case is a 2-3 tree that is all 2-nodes except that the leftmost path is made up of 3-nodes.
        
        The average length of a path from the root to a node in a red-black BST with N nodes is ~1.00 lg N.
        
        In a red- black BST, the following operations take logarithmic time
        in the worst case: search, insertion, finding the minimum, finding the maximum,
        floor, ceiling, rank, select, delete the minimum, delete the maximum, delete, and
        range count.
  - - - Hash function
        
        Separate chaining
        
        Linear probing
        
        Java provides the hashCode() function for every data type, the returns a 32-bit integer
        
        You must override both hashCode() and equals() if you need to hash with a user-defined type.
        
        consistent (equal keys must produce the same hash value) / efficient to compute / uniformly distribute keys
      - Collision resorlution
        
        Linear Probing
        
        Some key points
        
        Never let the hash table full (always between 1/8 and 1/2 for the N/M ratio)
        
        Deletion need to re-put all the remaining elements from the deletion spot to the next null spot.
        
        The more insertion will cause more clustering, and this will slow down the performance
        
        Quadratic Probing
        
        The incrementation just need to be a quadratic function, and not necessarily to be b^2
        
        You can use "-1" data to represent empty, and "-2" data to represent delected (this spot can be reused, just don't stop when search)
        
        The usage of the Hash Table must be less than 1/2 ot prevent clustering
  - - - Because when lo=hi=mid, lo++ index will always give you the value that is larger than the key value you are finding
- - - - Self-loop and parallel are allowed in CS applications for graphs
    - - Just the weight of the edge
    - - DFS
        
        Long and winding approach (use stack)
        
        Direct and comprehensive approach (use queue)
        
        Always find the shortest path
    - - If G = (V, E) be a non-directed graph with vertices V = {V1, V2,…Vn} then the total degree is sumDegree() = 2 * |E|
  - - - Pre-order: Queue
      - Post-order: Queue
      - Reverse-post-order: Stack
  - - - Edge
        
        WeightedEdge
        
        MST
    - - Runtime: O(E log E)
      - Space: O(E)
  - - - In conclusion, if you put all shortest paths together, you don't necessarily get a tree.
- - - - public foo(int i) throws fooException {}