Algorithm Design Manual
Common mistake is to use pseudocode to dress up an ill-defined idea so that it looks more formal.
For correctness of algorithms
- Set of allowed input instances
- Required properties of algorithm’s output.
Tips for design
- Narrowing the set of allowable instances until there is correct and efficient algorithm. e.g. Restrict graph problem from general graph down to trees or 2d to 1d.
- Traps in specifying output requirements:
- Not correctly specifying what best measure is.
- Creating compound goals which are hard to reason and solve.
- Find counter examples:
- Think small and simple.
- Think exhaustively.
- Hunt for the weakness. e.g [ Words like always and so on.]
- Go for a tie if algorithms are greedy.
- Take extremes: high and low, up and down, few and many, near and far.
- Boundary errors in inductive proofs.
Defining Problem Names
- Permutation: Arrangement, Tour, Ordering or Sequence
- Subsets: Cluster, COllection, Committee, Group, Packaging or Selection.
- Trees: Hierarchy, Dominance Relationship, Ancestor/Descendant Relationship or Taxonomy.
- Graphs: Network, Web, Circuit or Relationship.
- Points: Sites, Positions, Data Records or Locations.
- Polygons and Polyhedra: Shapes, Regions, Configurations or Boundaries.
- Strings: Text, Characters, Patterns or Labels.
Ways to think
- Think recursively: Look for big problems that are made from smaller ones of same type. e.g. Remove one node from permutation and it’s permutation of one less element. Removing the root of tree gives collection of small trees.
- Design the programs with efficient data structure in the first place.
Types of data structures by memory continuity
Contiguously-allocated
- Single slabs of memory.
- Arrays, matrices, Heaps and Hash tables.
- Constant access time given the index.
- Space efficiency due to no pointers.
- Memory Locality helps a lot in cache memories where there will be lots of cache hits.
Linked
- Distinct chunks of memory bound together by pointers
- Lists, trees, Graph Adjacency Lists.
- Complicated Deletions.
Basic Information about Data Structures
- Effective Implementation can be using either arrays or linked lists. Key issue is whether an upper bound on the size of the container is known in advance, thus permitting the use of a statically-allocated array.
- Dictionaries support operations such as:
- Min(D) or Max(D)
- Predecessor(D, k) or Successor(D, k)
- Unsorted doubly linked lists support insertion and deletion in O(1) but search takes linear time in worst case.
- Sorted arrays support binary search but cost of linear time update.
Binary Search Trees
- Basic operations supported by binary trees are searching, traversal, insertion and deletion. The pre-order and post-order traversal make little sense with search trees, but prove useful when rooted tree represents arithmetic or logical expressions. Allocating the node and linking it to tree is constant-time operation after the search has been performed in O(h) time.
- Deletion in binary trees is complicated, worst case complexity takes at most two searches which takes O(h) and constant time for pointer manipulation. It has three cases:
- Having only one child. SOLUTION: Link grandchild to the parent.
- Having two children. SOLUTION: Relabel the node with key of immediate successor in sorted order.
- Balanced search trees have all dictionary operations ( Insert, Delete and Query ) taking O(logn) time.
Trying to sort using specific operations only
- Sort in O(n logn) time using minimum, insert, delete and search.
- Repeatedly find and delete the minimum element to traverse the elements in sorted order.
- Sort in O(n logn) time using only insert and in-order traversal.
- Insert all n elements and do in-order traversal to access the items in sorted order.
- Sort in O(n logn) time using only minimum, successor and insert.
- Start with the minimum element and then repeatedly find the successor to traverse the elements in the sorted order.
Priority Queues
- Supports three primary operations
- Insert(Q, x)
- Find-Minimum(Q) or Find-Maximum(Q)
- Delete-Minimum(Q) or Delete-Maximum(Q)
- Naturally occuring. E.g. Dating Potential Candidates with Desirability Score where you try to Find-Maximum(), spend evening to evaluate them better and maybe update their score.
- Worst time complexity in priority Queue when underlying data structure is
| Array Type/Operation | Delete-Min | Find-Min | Insert |
|---|---|---|---|
| Unsorted Array | O(n) | O(n) | O(1) |
| Sorted Array | O(1) | O(1) | O(n) |
| BST | O(1) | O(1) | O(logn) |
Hashing and Strings
- Practical way to maintain a dictionary and having constant time access.
- Collision is the major setback in hash and can be resolved using:
- Chaining: Having a linked list of items with same hash key. But memory taken to store pointers.
- Open Addressing: Hash table maintained as array [ not bucket ] with each element initialised to NULL. On inserting an item, if spot is taken; takes the next possible place. Here, deleting can get ugly since removing one element might break a chain of operations. Thus, we need to reinsert all the items in the run following the new hole.
- In m-element hash table, Chaining takes O(n+m) time for chaining and O(m) for open addressing since n must be at most m.
Effective String Matching using Hash Tables
- Fundamental operation is substring search.
- Searching by placing the substring over string takes O(nm) time.
- Rabin-Karp algorithm can do it in expected linear time.
- Hash function on both pattern string ‘p’ and m-character substring from ith position of t. Hash values will be same in case of match. Even the false-positives are so rare and can be checked for explicitly easily.
- So, this reduces matching to n-m+2 hash value computations but since hash function takes O(m) time to compute hash function on m-character string, the computation is O(mn) again.
- Catch is we can compute hash of one changed character in string using simple multiplication, addition and subtraction which can be done in constant time. Thus, the O(nm) time complexity reduces to O(n).
Duplicate Detection
- Used by search engines to compare documents.
- Hashing for bids.
Specialized data structures
- String
- Geometric
- Graph
- Set
Pragmatics of Sorting
- What order do we want the items sorted?
- Increasing or Decreasing Order
- Sorting just the key or entire record
- What should we do with equal keys?
- Secondary Keys such as article size OR leave items in same relative order as in the original permutation.
- Algorithms that enforce such requirement are known as Stable.
- Right way to specify such matters is to have proper way to use comparison of records.
Heap Sort
- What happens if we replace unsorted array in Priority Queue implementation with better data structure : Heap or Binary Search Tree? Using such implementation takes O(nlogn) instead of O(n2).
- Heapsort is nothing but implementation of selection sort using right data structure.