The Data Structures and Algorithms Specialization on Coursera teaches various ways to develop and design algorithms. This repo is a collection of algorithms I have developed by one of these techniques.
Greedy algorithms work by choosing a safe step and repeating the safe step till the problem is solved.
These algorithms divide the problem into smaller non-overlapping sub-problems. The base case of these sub-problems is usually the most obvious solution for the smallest input. MergeSort is an example.
Dynamic Programming is a mathematical approach for breaking down the given problem into smaller overlapping sub-problems. The way to this approach is to develop a brute force solution and then optimize it using one of these techniques:
Cache the output of the recursive function for given set of changing inputs.
Creates a table in memory and computes the result iteratively. The next larger result is computed using the previously computed smaller results.
The following algorithms were covered in the course material:
- Discrete Knapsack
- Fractional Knapsack
- (More soon..)