Algorithms

Basic rules of complexity definition for removing terms:

  1. Multiplicative constants can be omitted: 14n2 becomes n2.
  2. n^a dominates n^b if a > b: for instance, n^2 dominates n.
  3. Any exponential dominates any polynomial: 3^n dominates n^5 (it even dominates 2^n).
  4. Likewise, any polynomial dominates any logarithm: n dominates (log n)^3. This also means, for example, that n^2 dominates n* log n.

Techniques to think of counter examples:

  1. Think small
  2. Think exhaustively: All possibilities by adding to general cases
  3. Hunt for the weakness: understand the problem statement and try to find loopholes
  4. Go for a tie: Attacking greedy procedures
  5. Extreme examples:

Searching for solution to problem needs you to know first the type of problem it falls into:

  1. Permutations: They are likely the object in question whenever your problem seeks an “arrangement,” “tour,” “ordering,” or “sequence.”

  2. Subsets are likely the object in question whenever your problem seeks a “cluster,” “collection,” “committee,” “group,” “packaging,” or “selection.”

  3. Trees: Hierarchial relations whenever your problem seeks a “hierarchy,” “dominance relationship,” “ancestor/descendant relationship,” or “taxonomy.”

  4. Graphs: relationships between arbitrary pairs of objects Graphs are likely the object in question whenever you seek a “network,” “circuit,” “web,” or “relationship.”

  5. Points: whenever your problems work on “sites,” “positions,” “data records,” or “locations.”

  6. Polygons: working on “shapes,” “regions,” “configurations,” or “boundaries.”

  7. Strings: dealing with “text,” “characters,” ,“patterns,” or “labels.”

Some intuitions behind runtime :

  1. n! will be useless after n > 20

  2. For upto n=10 all algorithms look similar.

  3. 2^n is useless after 40

  4. n^2 is hopeless after a million

  5. linear and nlogn are useful upto a billion

  6. logn is useful for any number that comes up.

Types of function classes based on O(n) rule:

  1. Constant time

  2. Logarithmic time

  3. Linear

  4. Superlinear

  5. Quadratic

  6. Cubic

  7. Exponential

  8. Factorial

Know that changing the base of logarithm has very less impact on time complexity of solution.

Different types of logs: natural, binary, common(base 10) in historical times.

Harmonic numbers sum result in logarithm.

Exponentiation can be done faster using logarithm to convert it to problem of simple multiplication.

Multiplication of matrices requires 3 loops so it’s complexity is n^3.

Advanced type of function classes for complexity analysis:

  1. Inverse ackerman’s function alpha(n): Used in analysis of Union Field Data Structures

  2. Loglogn

  3. logn / loglogn : grows even slower than logn

  4. log^2(n): The “log squared” function typically arises in the design of intricate nested data structures, where each node in (say) a binary tree represents another data structure, perhaps ordered on a different key.

  5. Sublinear polynomials: root(n) and so on.

  6. n^(1+epsilon) : amazing type, highlighted now for reference

Limits and dominance:

f(n) dominates g(n) if lim(n→∞) [g(n)/f(n)] = 0

e.g. 2n^2 is greater than n^2 but doesn’t dominate.

n^3 will though dominate n^2.

For any two polynomials, namely that n^a dominates n^b if a > b

Exponential with higher base dominates. e.g. 3^n over 2^n

A more advanced dominance order:

n! » c^n» n3» n2» n^(1+eps)» n log n» n» √n» log^2(n)» logn» log n/ log log n» log log n» α(n)» 1

Data structures:

Basically two types based on how they are stored in memory: Contiguous: Arrays, matrices, heaps, Hash tables

Pointers: Lists, trees, graphs and adjacent lists

Arrays:

Constant time given the index

Space efficiency

Memory locality: A common programming idiom involves iterating through all the elements of a data structure.

Disadv:

Can’t change size dynamically

Dynamic arrays:

Multiply the memory allocated into 2 times, copy the old one to the lower end of new block and operate.

Main disadv:

Copying the contents of the memory : It will take log2 n doublings until the array gets to have n positions. However, most elements do not suffer much upheaval. Indeed, the (n/2 + 1)st through nth elements will move at most once and might never have to move at all.

Thus, each of the n elements move only two times on average, and the total work of managing the dynamic array is the same O(n) as it would have been if a single array of sufficient size had been allocated in advance!

Questions to answer before sorting:

  1. Order of sorting
  2. Sorting just the key or the entire records
  3. What to do with equal keys? : Leave as the original permutation or resort to some another form of sorting criterion as secondary.
  4. What about non numerical data?