Basic Algorithms Notes

Data Structures & Algorithms
  Performance/Complexity
    Performance
      The amount of CPU/memory/disk usage
    Complexity
      Definition
        How well an algorithm scales
        How an algorithm behaves as the size of the problem increases
      Big O Notation
        Order of magnitude of the number of operations required to perform a function
        Growth relative to the size of the problem
        Common orders in order from best to worst
          O(1)
            Constant time
            Performance isn't affected by the size of the problem
            Could still be slow, just stays slow
            Example
              Array lookup
              Grabbing something from memory
          O(log N)
            logarithmic time
            Usually requires your algorithm to somehow discard large portions of input set, so algorithms of this kind usually have searching of some kind
            Usually log base 2
            Trick
              To calculate log base 2 of a number, work out number of binary digits needed to store that number
              Example
                log base 2 of 300 = 9, as it takes 9 binary digits to express the number 300
          O(N log N)
            proportional to size of problem and the logarithmic time
          O(N)
            linear time
            Example
              As you add more customers in grocery line, time for each one stays the same
          O(N^2)
            quadratic time
            Example
              Every person in a group meets every other person
          O(N!)
            factorial time
  Data Structures
    Lists
      Ordered collection of elements supporting random access to each element
      Preserve insertion order
      Array Lists
        Uses array to hold values
        Pros
          Implementation very simple
          Fastest implementation for indexed and sequential access
        Cons
          Each time you insert element, you have to shift any higher elements one position through physical copying
          Same issue with deletion
          Dynamically increasing size of list requires creating new array and copying elements over
          So, performance for insertions and deletions not as good
      Linked Lists
        Chain of elements in which each element has a reference to the next (and optionally previous) element
        Doubly-linked list goes in both directions
          Can access either end with equal performance
        Pros
          Insertion and Deletion are much simpler than array list
            Only have to update elements to and from the elements around the affected element
            So cost is almost neglible
        Cons
          For large lists, traversal time can be a performance issue
        Sentinel trick
          Also called Null Object Pattern/Null Object
          Technique for simplifying an algorithm by adding a special object to one or both ends of a data structure to avoid writing special code that handles boundary conditions
          Allows you to avoid having to check for 'null' all the time
          Next and Previous fields of sentinel point to start and end of linked list
          First and last elements themselves reference the sentinel object as their previous and next elements, respectively
        Trick for increasing getting a particular element's performance
          If desired position falls in first half of list
            Start searching from beginning
          Otherwise
            Start searching from end
          Cuts actual performance time in half
    Queues
      You only ever get the head of a queue
        The head of the queue differs based on the kind of queue you are dealing with
      Producer
        Anything that stores data in a queue
      Consumer
        Anything that retrieves data from a queue
      Bounded Queues
        Have limits placed on the number of items that can be held at any one time
      Unbounded Queues
        Free to grow in size
      Queue operations
        enqueue
          store a value in the queue
        dequeue
          retrieve the value from the head of the queue
      First In First Out (FIFO)
        Order of retrieval same as order of insertion
        First value to go in is first value to come out
        Calling dequeue() will always give you the element that has been waiting longest
        Implementation
          Using a list as underlying storage is best option
            Linked list better than array list since size will probably grow and shrink
      Blocking Queues
        Useful in multi-threaded environment
        All access to data correct synchronized
        A blocking queue
          When attempt is made to store item beyond queue limit, queue will block until space is available
          If dequeue() is called and nothing available, will block thread until item is available
          Good for pool of workers who want tasks to perform
        Implementation
          In general, keep same external API as standard Queue, just wrap it with a synchronized version that internally composes non-blocking version
          Internally, use mutual exclusion semaphor (mutex) (a common object) as synchronization point for all operations to block on
          Java
            syncronized(_mutex)
              while we are at max size
                try{ _mutex.wait() } catch(){}
              _queue.enqueue(value)
              _mutex.notifyAll()
      Priority Queues
        Special type of queue that provides access to the largest element contained within it (could be smallest)
          More general form of queue
          FIFO queue could use comparator that is based on time since insertion
          LIFO queue could use comparator that is based on time of insertion
        Unsorted List Priority Queue
          Keep as unsorted list
          Just search through for largest item each time
          Enqueue
            O(1)
          Dequeue
            O(n)
          Good if not too many calls to dequeue, since so simple
        Sorted List Priority Queue
          Keep list in sorted order so always ready to get largest
          Deuque will be very fast
            Just removes last item from the list
          Enqueue does all the hard work
            Can just use insertion sort, because insertion sort works well on list that is mostly sorted already and we are just adding one item
        Heap-ordered Priority Queue
          Heaps
            A binary tree structure in which each element is larger than its two children - known as the heap condition
            The largest item is sitting at top of tree
              other elements are not sorted and are not of interest
            Trick for storing heaps
              Logically a tree structure, but we store as a list
              To navigate tree structure stored as list (we numbered each node, starting from 0 at root):
                The left child of the item at index X is at index (2X + 1)
                The right child of the item at index X is at index (2X + 2)
                The parent of the item at index X is at index ((X - 1) / 2); item 0 has no parent
          Adding new items
            Just add to end
            Heap condition no longer applies though
              Must swim element to the top to restore
                Swimming
                Exchanging an item with its parent if the parent is smaller, and continuing until the top of the heap is reached or a parent is found that is equal to or larger than the item doing the swimming
          Deleting largest item
            Just grab root
            Swap in value at bottom right of the tree (i.e. last position of list)
            Heap condition now violated
              Must sink value down
                Sinking
                Process of repeatedly exchanging an item with the larger of its children until the heap condition is restored or the bottom of the tree is reached
          Adds and removes items from queue in O(log N)
    Stacks
      A stack is a list with access restricted to one end
      Operations
        Pop
          Deletes and retrieves top-most element
        Push
          Pushes a new element on to the stack
        Peek
          Returns but does not delete top of the stack
      Implementation
        Just use a list
          Compose using a LinkedList implementation
      Some use cases
        MRU (Most Recently Used) list
        parsing programming languages
        Undo-Redo
        Tower of Hanoi
        RPN (Reverse Polish Notation) calculator
        reversing list of values
        XML processing
        screen flow management (back/forward button in browser)
    Trees
      Binary Search Trees
        Binary search algorithms suffer when lots of adds or deletes
        Can achieve O(log N) search time of binary search tree while being easy to add and delete things
        Leaf nodes
          Have no children
        Binary tree has two children
          All children to left must have smaller values
          All children to right must have larger values
        Average search time is proportional to its height: O(h)
          For balanced tree the height is O(log N)
          If unbalanced, can lead to worst-case search time of O(N)
        Minimum
          Node with smallest value
          Follow left links starting from root to find smallest value
          Leftmost node in the tree
        Maximum
          Node with largest vlue
          Follow right-hand links from root to find largest value
          Rightmost node in the tree
        Successor
          One with the next largest value in the tree
            Finding
              Two cases
                If node has right child, then successor is minimum of that
                If node has no right child, search back up the tree until you find first "right-hand turn"
                Keep looking up tree until you find a node that is the left-child, then use its parent
        Predecessor
          Node with the next smallest value
          Finding
            Two cases
              If node has left child, then take its maximum
              If node has no left child, work up the tree until you find a left-hand turn
                Keep looking up tree until you find a node that is the right-child, then use its left-most child if present, or just it if no left-most child
        Search
          Start at root node and follow links left or right as appropriate (whether value is smaller or larger, respectively) until you find appropriate value or none
        Insertion
          If search returns nothing, then add to tree as root node
          If nonrandom data added, then tree will degenerate into a linked list, and height of the tree, and average search time, because O(N)
          Must use a tree that does re-balancing
            Red-Black trees
            AVL trees
            Splay trees
            B-Trees
        Deletion
          three cases to consider. Node to be deleted will reflect one of the following:
            No children (a leaf), in which case just remove it
            One child, in which case you replace deleted node with its child
            Two children, in which case you swap the node with its successor and try again with case 1 or 2
          Can unbalance a tree
        In-order Traversal
          Visits the values in a binary search tree in sorted order
            Useful for printing out or processing values in order
            Recursive algorithm
              Traverse the left subtree of the node
              Visit node itself
              Traverse right subtree
            Iterative algorithm
              Start with the minimum of the tree and visit it and each successor node until there are no more
        Pre-order Traversal
          First visits the root node, then each of the subtrees
          Recursive algorithm
            Visit the node itself
            Traverse left subtree
            Traverse right subtree
          Iterative algorithm complex and requires stack
        Post-order Traversal
          Visits the root node after each of the subtrees
          Recursive Algorithm
            Traverse left subtree
            Traverse right subtree
            Visit the node itself
          Iterative algorithm complex and requires stack
        Balancing
          Balancing restores desired characteristics of tree
          Difficult thing is detecting imbalance in first place
          AVL Tree
            Track the height of each subtree
              If two siblings ever differ in height by more than one, tree has become unbalanced
            To correct
              rotating nodes to remove the imbalance
              Working up tree from inserted/deleted node to the root, rotating nodes as necessary
              Four different types of rotation, single or double rotation, left/right version
                Special table not reproduced here on which to do
          Red-Black Tree
      Ternary Search Trees
        Overview
          Specific for storing and retrieving strings
          Like a binary search tree, so each node has reference to smaller and larger values
          However, each node doesn't have entire value, just one letter
          Also has a reference, hence ternary, to a subtree of nodes containing any letters that follow it in the word
          A node must indicate whether it is a word ending, so we can differentiate partial from full real matches
        Performance
          Compares fewer individual character comparisons with an equivalent binary search tree
            Because words that share common prefix are compressed
          Efficient at quickly discarding words that don't exist in the tree, because terminates if no matching prefix found
          If size of alphabet is M (such as A-Z), then to find a word of length M results in O(N log M).
            In practice, performance much better due to common prefixes and Zipfs law
          Unbalanced tree devolves to O(NM) comparisons
        Searching for a word
          Perform a binary search starting with the first letter of the word for which you are searching
          Start at root and follow links left and right as appropriate
          Once you find a matching node, move down one level to its reference child and start again, this time with the second letter
          Continues until you find all the letters, in which case you have a match, or run out of nodes
        Inserting a word
          Add extra leaf nodes for any letters that don't already exist
          Store word endings if a letter is an ending
        Prefix searching
          Ternary search trees useful for finding all words with a common prefix
          Perform standard search just using prefix
            Then perform in-order traversal looking for every end-of-word marker
            In order traversal on Ternary search tree
              Having found last node in prefix
                Traverse left subtree of the node
                Visit the node itself
                Traverse the node's reference children
                Traverse the right subtree
        Pattern matching
          Can be used to match wildcard patterns in a word
          Each time you come across a wild card, rather than looking for a node with a matching letter you instead visit each node as if it was a match
      B-Trees
        Overview
          Great if data exists on disk with large indexes
          For managing indexes on secondary storage
          Contains nodes. Each node contains not one, but multiple keys, up to some defined maximum, usually determined by the size of a disk block
          Keys in node are stored in sorted order, with an associated child node holding keys that sort lower than it
            Every non-leaf node containing k keys must have k+1 children
        Performance
          Height is lower of a B-Tree, so fewer node traversals and therefore fewer disk I/Os
          Order of magnitude better than binary search tree
        Lookups
          search must make a choice between multiple children
            Start at root node
            Scan through key list, on each key doing similar routine as binary search tree
            Follow link to children from key entry if appropriate
        Inserting
          Start at root and search all the way down until you reach a leaf node
          Insert value in order
          If key threshold is exceeded (it becomes full), split it into two condes, each containing half the keys from the original
          The "middle" key from the original node is then moved up to the parent and inserted in order with a reference to the newly created node
          Repeat if new parent node also full
          Whenever the root node is split, a new node is created and becomes the new root
        Deletion
          Complex with lots of edge cases - not delved into here
    Hashing
      O(1) lookup
      hash function takes a value and produced a hash value
        used to locate position within hash table
      collisions - different values hashing to same address
        Can increase address space to avoid collisions
          Increased amount of wasted space
        Prime numbers for hash table size better than non-primes
          Choose prime close to hash table size
        perfect hashing algorithm - one that produces no collisions at all
          very hard to find
        CRC is a good hash algorithm
          Add each letter -- working value is multiplied by 31 before eaching each letter
            elvis - ((E * 31 + L) * 31 + V) * 31 + I) * 31 + S)
          Take remainder after dividing hash value by the table size (the modulus) - use a close prime - generates final address
            ELVIS % 11
      Linear Probing
        Collisions still occur
        On detecting a collision, searches linearly for the next available slot and uses that
        If reach end, just wrap before start
        If table full, must resize and just use linear search
        Works well for sparsly populated hash tables
        As table members increase though, searching and performance degrade from O(1) to O(N)
      Bucketing
        Use buckets to store more than one item
        Each bucket holds zero or more items that hash to the same value
        Tension between number of buckets, performance, and space taken up
        When to resize number of buckets?
          monitor load factor
            ratio of stored values to available buckets
          set a threshold load factor that will trigger a resize
          Load factor of 0.75 or 75% is good tradeoff between space and time.
    Sets
      Collection that hold only distinct values; guarantees that an item will not be added more than once
      Set operations between two sets
        Union
          Another set containing all values from both (no duplicates)
        Intersection
          Values in common
        Difference
          Values that are not in common
      List Set
        Use a simple list
          Linked list
        Simple, add and delete perform in O(N), okay for small amounts of items
      Hash Set
        Lots of values and ordering not important, then this is good choice
      Tree Set
        Guarantees ordering of data while keeping set semantics
        O(log N)
    Maps
      Also known as dictionaries, lookup tables, associative arrays
      Mapping between key and value
      Each key/value pair is an entry
      List Map
        Just use a list; simple, but not efficient
        O(N)
      Hash Map
        Use a hashtable
        Each bucket is just a list map
        If good hash function, O(1) can be achieved
      Tree Map
        When you want a predictable ordering of the keys
        Backed by a binary search tree
        O(log N)
  Algorithms
    Sorting
      All sorting algorithms composed of
        Comparing items to determine whether they are out of order
        Moving items into sorted position
        Advantages and disadvantages of sorting algorithms are based on how many times these fundamental operations need to be performed and how expensive these operations are in performance terms
      Stability
        If a sorting algorithm maintains the relative order of items with a common sort key, it is said to be a stable algorithm
      Basic
        Bubble Sort
          Performance
            O(N^2)
            Best case is O(N) if list is already sorted
          Algorithm
            Repeatedly step through the list
            Compare two items at a time and swap them if they are in the wrong order
            Pass through list is repeated until no swaps are needed, which means list is sorted
          Analysis
            Pretty awful - never use in practice
            Stable
        Selection Sort
          Performance
            O(N^2)
          Algorithm
            Find the minimum value in the list
            Swap it with the value in the first position
            Repeat the steps above for remainder of the list (starting at the second position)
          Analysis
            Pretty awful - never use in practice
            Not stable
        Insertion Sort
          Performance
            O(N^2), but see Analysis section below for real-world performance
            Best case is O(N) if list is already sorted
          Algorithm
            Maintain two parts of your list to sort
              On the left is the sorted portion
              On the right is the unsorted portion
            Starting in the unsorted portion, grab the first value
            Find the area in the sorted section where it belongs and insert it
            Repeat at beginning of unsorted section now
          Analysis
            Simple to implement
            Efficient on (quite) small data sets
            Efficient on data sets which are already substantially sorted: it runs in O(n + d) time, where d is the number of inversions
              Therefore good for adding something new to a dataset that is already sorted
            More efficient in practice than most other simple O(N^2) algorithms such as selection sort or bubble sort: the average time is (N^2)/4 and it is linear in the best case
            Stable
            In-place (only requires a constant amount O(1) of extra memory space)
            It is an online algorithm, in that it can sort a list as it receives it.
          Implementation
            Pseudocode/Java
              sort(List list)
                List results = new LinkedList()
                Iterator it = list.iterator()
                Object current
                for(current = it.first(); it.hasNext(); current = it.next())
                int slot = results.size()
                while(slot > 0)
                if current comes before (is smaller) than results.get(slot - 1)
                break
                slot--
                results.insert(slot, current)
              We scan from end of the list in terms of the already sorted portion. Big advantage when it comes to sorting already sorted or near-sorted lists. Also maintains stability.
      Advanced
        Shellsort
          Idea
            Arrange data sequence in two-dimensional array
            Sort the columns of the array
            Repeat steps over and over with narrower array (i.e. less columns)
            Continue until just one column
          Implementation
            We don't actually have two-dimensional array
            Instead, one-dimensional array and just have a 'step' value to grab every k-th element, which simulates a column
              Also known as a 'gap'
            Then, do an insertion sort on this 'column'
            Sensitive to choosing 'gap' value
              Best known is 1, 4, 10, 23, 57, 132, 301, 701
                Start with larger gaps, than work down
              You can compute these yourself
                nextgap = round(gap * 2.3)
              Pseudocode (Java)
                public static void shellSort(int[] a)
                for (int increment = a.length / 2; increment > 0; increment = (increment == 2 ? 1 : (int) Math.round(increment / 2.2)))
                // could just delegate to an insertionSort method that takes a gap factor
                for (int i = increment; i < a.length; i++)
                for (int j = i; j >= increment && a[j - increment] > a[j]; j -= increment)
                int temp = a[j];
                a[j] = a[j - increment];
                a[j - increment] = temp;
          Performance
            Worst case O(N log^2 N)
              Worse than optimal comparison sort, which is O(N log N)
            Not stable
        Quicksort
          Idea/Algorithm
            Divide and conquer approach to divide a list into two lists
            Pick an element, called a pivot, from the list
            Reorder the list so that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
            Recursively sort the sub-list of lesser elements and the sub-list of greater elements
              Base case is sub-lists with 0 or 1 elements
            Issue is that the above requires O(N) of an extra array
              Can seriously impact performance in real-world due to extra memory usage
            An in-place version is possible
          Implementation of in-place version
            Pseudocode
              function partition(array, left, right, pivotIndex)
                pivotValue := array[pivotIndex]
                swap( array, pivotIndex, right) // Move pivot to end
                storeIndex := left - 1
                for i from left to right-1
                if array[i] <= pivotValue
                storeIndex := storeIndex + 1
                swap( array, storeIndex, i)
                swap( array, right, storeIndex+1) // Move pivot to its final place
                return storeIndex+1
              function quicksort(array, left, right)
                if right > left
                select a pivot index (e.g. pivotIndex := left)
                pivotNewIndex := partition(array, left, right, pivotIndex)
                quicksort(array, left, pivotNewIndex-1)
                quicksort(array, pivotNewIndex+1, right)
          Performance
            Average case is O(N log N)
            Can devolve to a worse case of O(N^2) though
              Choosing the pivot point is the most important thing
            In real world, on real architectures, fastest comparison versus other O(N log N) algorithms
            Not stable
        Mergesort
          Idea
            Divide the unsorted list into two sublists of about half the size
            Divide each of the two sublists recursively until we have list sizes of length 1, in which case the list itself is returned
            Merge the two sublists back into one sorted list
              Most work happens in merge
          Implementation
            Pseudocode
              function mergesort(m)
                var list left, right, result
                if length(m) ≤ 1
                return m
                else
                var middle = length(m) / 2
                for each x in m up to middle
                add x to left
                for each x in m after middle
                add x to right
                left = mergesort(left)
                right = mergesort(right)
                result = merge(left, right)
                return result
            function merge(left,right)
              var list result
              while length(left) > 0 and length(right) > 0
                if first(left) ≤ first(right)
                append first(left) to result
                left = rest(left)
                else
                append first(right) to result
                right = rest(right)
              if length(left) > 0
                append rest(left) to result
              if length(right) > 0
                append rest(right) to result
              return result
          Performance
            O(N log N)
            stable
    Searching/Matching
      Binary searching
        Technique for locating items in a sorted list
        Runs in O(log N) time because data is sorted
        Basic technique
          Continually divide data in half, progressively narrowing down the search space until you find a match or there are no more items to process
        Algorithm
          Start in the middle of the list
          Compare the search key with the item at the current location
          If search key is current location, return
          If search key is less than the item at current location, then value must be in left half - divide the list and use left half, repeating
          If search key is greater than the item at current location, value must be in right half - divide the list and use that, repeating
        Recursive Binary Searcher
          Just algorithm above
        Iterative Binary Searcher
          Recursive search code, for each time it recurses, does little more than modify one of the upper and lower index variables
          This means you can get rid of recursion and use a while loop, simply modifying the upper and lower index variables
          Pseudocode
            function search(List list, Object key)
              lowerIndex = 0
              upperIndex = list.size() - 1
              while (lowerIndex <= upperIndex)
                index = lowerIndex + (upperIndex - lowerIndex) / 2
                if(key == list.get(index)
                return value
                else if (key is less than list.get(index))
                upperIndex = index - 1
                else
                lowerIndex = index + 1
              if we didnt find anything
                return null
              else return index
          Optimization
            Continue searching only while you belive there is a chance that the search key might exist
            When reach point in the list where the search key would sort before the current item, terminate loop
        Performance
          Binary search is O(log N), while linear search is O(N)
          Actual performance is excellent as long as you are using a data structure that performs index-based lookup
          If using linked list, continual traversal of list kills you
        Binary Insertion
          Maintains data in sorted order
          Don't want to perform sort after every insertion
          Only difference with binary searching is that you find position and then insert
          Performance is O(log N!) - (notice the factorial)
            Because you want to be using index-based data structure, must recopy everything to right for insertion, which can become overhead on large datasets
      String searching
        Find one strings within another
        Brute Force
          Just scan through text, at each position looking for target word
          Simple
          O(NM), where N is length of text and M is length of pattern
        Boyer-Moore Algorithm
          Many moves in brute-force are redundant
          Can skip through string faster because it doesn't even have characters in pattern
          How many places to skip when you find a mismatch?
            Each time you encounter a failed match, you search the pattern for the last (rightmost) occurence of the offending character and proceed according to the bad-character heuristic:
              If the character exists within the pattern, you shift right enough places to align the character in the pattern with the one in the text
              If the character doesn't exist within the pattern, you shift right enough places to move just beyond it
              Whenever above two propose negative shift, just move right one before returning to Boyer-Moore algorithm
          Performance
            If text does not have pattern, then entire length of pattern can be skipped each time, leading to best-case running time of O(N/M), where N is length of text and M is length of pattern
            In actuality performs twice or four times faster than brute force version
              The longer the pattern, the better the performance
          Implementation
            Create a last occurrence table (only good for ASCII -- for larger languages not good) so you don't have to scan pattern each time for location
              Have an array of 26 positions (alphabet), fill each one with -1 by default; for a given position, representing that letter, put the location in the pattern of its rightmost location if present
            For search method
              Scan text from left to right (s)
                For the letter in the text, scan the pattern from right to left to find portion that doesn't match (i)
                If we made it to the far left, we have a match -- return
                Else, nice trick:
                s += Match.max(i - lastOccurence[c], 1)
                s is the index in the text to search
                i is location of last mismatch
                lastOccurence[] is the lookup table
                Automatically encapsulates rules of algorithm in that one line
        String Match Iterator
      String matching
        Soundex
          Phonetic encoding algorithm
            Takes strings and converts similar sounding words into same encoded value
          Others
            Metaphone and Double-Metaphone
          Algorithm (English only)
            Process string from left to write
            Apply transformation to each letter
            Produces 4-letter code of form LDDD, where L is a letter and D is a digit from 0 to 6
            Rules:
              All characters processed as upper case
              Always use first letter
              Drop all other characters if they are A, E, I, O, U, H, W, Y
              Translate remaining letters as follows:
                B, F, P, V = 1
                C, G, J, K, Q, S, X, Z = 2
                D and T = 3
                L = 4
                M and N = 5
                R = 6
              Drop consecutive letters having same code
              Pad with zeros if necessary
          Performance
            O(N)
          Implementation
            Have a CHARACTER_MAP that maps the rules above that we can quickly use
              char[] CHARACTER_MAP = "01230120022455012523010202".toCharArray()
              Useful for quick lookup
            Scan through string, map first letter to result, then do lookup for each letter -- don't copy over matches that are the same number; pad with zeros if not length of 4
        Levenshtein Word Distance
          Soundex not good at finding large typing errors
          Levenshtein Word Distance also known as edit distance
          Compares words for similarity by calculating the smallest number of insertions, deletions, and substitutions to transform one string into another
          Choose some limit, such as 4, below which the distance between the two words is short enough to consider
          Each operation is assigned a cost, and the smallest distance is the set of changes with the smallest total cost
          Make a table
            One word on top (target word), one along the left (source word)
            Have cell 0 at 0,0 - run the numbers along the first row and column as well
            Calculate values for cells in the grid. Value for each cell from following formula:
              min(left diagonal + substitution cost, above + delete cost, left + insert cost)
            Cost for insertion and deletion always one, but cost for substitution is only one when the source and target characters don't match
            Value in bottom-right cell of grid shows minimum distance
            Now you can walk from upper-left to bottom-right to get edit sequence
              Move diagonally is a substitution
              Move right an insertion
              Move down a deletion
          Performance
            O(MN), where M is source and target is N
              Not really good enough for a spell checker
    Computational Geometry
      Basic geometry
        Pythagoras' theorem
          a^2 + b^2 = c^2
        Formula for line
          y = mx + b
          m is slope, b is point at which line cuts y axis
        Slope
          How steep it is
          Rise
            Vertical distance (y-axis)
          Travel
            Horizontal distance (x-axis)
          Slope is ratio of rise to travel
          Slopes can be negative
          Vertical line has slope of infinity
      Finding intersection point
        Line one
          y = mx + b
        Line two
          y = nx + c
        Equation
          x = (c - b) / (m - n)
        Solve, then plug x back in to get y
        If one of the lines is vertical, then you can just plug y in directly to other formula
      Finding closest pair of points
        Dumb approach is O(N^2) - compare every point with other point
        Plane Sweep algorithm better
          Considers each point in order from left to right in the coordinate system
          Make a single pass, or sweep, across the two-dimensional plane containing the points, remembering the currently known smallest distance and the two points that are separated by that minimum distance
          The point being considered as sweep progress is placed at right edge of a rectangular box called the drag net
          Width of drag net has a width of d, which is length of shortest known distance -- width is behind box being considered
          Now we check distance of point on sweep line with all other points under the drag net to see if they make a smaller distance
          If closer pair found, we proceed with smaller drag net until every point processed
        Implementation
          Points need to be sorted acording to their coordinates
            place them in a set, so no duplicates, and if same x then consider y when sorting (just make a custom comparator)
          Then scan with algorithm