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