# 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
• 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

• 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

By tahsinversion2