- Control Abstractions
- Data Abstractions
- Data Abstraction Components
- Structure of Data
- Operations on Data
- Linear Data Abstractions
- Linked List
- Tabular Data Abstractions
- Recursive Data Abstractions
- Binary Search Tree
- Red Black Tree
- Graph Abstraction
- Model: Objects with binary relation defined on pairs
- 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.
- 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.
Design algorithms using
- Domain Knowledge
- Computational Abstractions & Algorithmic Paradigms
- Domain Knowledge: Prime, GCD etc.
- Computational Abstractions & Algorithmic Paradigms: Loop, Recursion etc.
- Domain Knowledge: Binomial Co-efficient, etc.
- Computational Abstractions & Algorithmic Paradigms: Loop, Table, Dynamic Programming etc.
- Domain Knowledge: Properties of geometric objects
- Computational Abstractions & Algorithmic Paradigms: Stack, etc.
Polynomials & Fast Fourier Transform