Organization Of The Study And Application Of Algorithms

Computational Abstractions

  • Control Abstractions
    • Loop 
    • Recursion
  • Data Abstractions 
    • Data Abstraction Components
      • Structure of Data
      • Operations on Data
    • Linear Data Abstractions 
      • Array
      • Stack 
      • Queue
      • Linked List 
    • Tabular Data Abstractions 
      • Hashing
    • Recursive Data Abstractions
      • Binary Search Tree 
      • Red Black Tree
      • Heap
    • Graph Abstraction
      • Model: Objects with binary relation defined on pairs


Computational Complexity

  • Time Complexity
  • Space Complexity  


    Algorithmic Paradigms

    • Dynamic Programming
      • Recursively define solution to problem in terms of solution to limited number of subproblems.
        • What could be the penultimate subproblems? (Work backwards.)
        • Subproblems having same structure as the original problem, only being smaller in size. 
        • Prove – defining solutions in terms of solutions to subproblems is optimal.
      • Compute and store the results of subproblems in memory so that you don’t have to recompute them. Then use the stored results to compute solution to the problem. 
    • Divide & Conquer
      • Divide the problem into subproblems (dividing up inputs into parts) and solve the subproblems recursively. 
      • Combine the results of solutions of subproblems.
    • Greedy
    • Backtracking
      • If you can define the space of all possible solutions, you can search the space for solutions systematically through backtracking. 
      • In backtracking, you generate one element at a time towards the solution and backtrack whenever you meet a dead-end.  


    Application Domains


    Design algorithms using 

    • Domain Knowledge
    • Computational Abstractions & Algorithmic Paradigms 

    Number Theory

    • Domain Knowledge: Prime, GCD etc.
    • Computational Abstractions & Algorithmic Paradigms: Loop, Recursion etc.

    Combinatorics

    • Domain Knowledge: Binomial Co-efficient, etc.
    • Computational Abstractions & Algorithmic Paradigms: Loop, Table, Dynamic Programming etc.

    String Processing

    Linear Programming


    Matrix Algorithms

    Computational Geometry

    • Domain Knowledge: Properties of geometric objects
    • Computational Abstractions & Algorithmic Paradigms: Stack, etc.

    Polynomials & Fast Fourier Transform