Algorithms

Generate pre-defined outputs on basis of previously programmed rules which are hard-coded in the system.
Rule-based Algorithms have fixed result and the result doesn't change or evolve based on the data.
Typically in the form of if-then expressions.

Rule-based system

Set of facts: Domain-specific knowledge - Database
Set of rules: Rules engine which makes up the knowledge base
Inference engine; Capable of deriving conclusions.

Paradigms

Backtracking

Used for problems where you have to explore all possible combinations and there are no two ways about it.

Although a trial-and-error method, backtracking systematically builds up the solution.

DFS on Decision trees

If you model these problems as a decision Trees, you can think of the backtracking algorithm as a form of DFS on these trees.

You follow a path deeply until you reach a dead-end
You come back and follow alternate paths

Backtracking algorithm structure

Backtracking algorithms usually involve the following

Base case: If a valid solution is found, return or store it.
Recursive case:
- Try making a choice
- if the choice leads to a valid solution, recursively continue exploring.
- if the choice leads to a dead-end, undo the choice (backtrack) and try the next alternative.


function BACKTRACKING(solution, choices):

	if solution is a complete and valid solution:
		process the solution (e.g., store, print, or count it)
		return

	for each choice in choices:
		if choice is valid according to constraints:
			make the choice (add choice to current solution)
			BACKTRACKING(solution with choice, remaining choices)
			undo the choice (backtrack)
	
# Example driver function to initialize the algorithm

function SOLVE_PROBLEM():
	solution = [] # start with an empty solution
	choices = get_initial_choices() # get all possible initial choices
	BACKTRACKING(solution, choices)

Dynamic Programming

Dynamic Programming can be applied in algorithmic problems where:

the problem requires you to find some optimal Result (Max/min/count).
the problem can be broken down into miniature versions of itself (subproblems).

💡 The method was invented by Richard Bellman in 1950 who also coined the term "Dynamic Programming". The programming part doesn't have anything to do with computer programming. He used programming to refer to 'planning and decision making'. Dynamic just refers to the ever-changing nature of the problems. The mathematical approach used by him applies in solving algorithmic problems as well.

He intentionally chose a misleading name to hide the fact that he was doing mathematical research. The secretary of defence at the time developed a fear and hatred for the word "research". Keeping a generic name made it hard for anyone to disapprove.

It is typically easier to start with top-down approach, and then move on to optimize it using bottom-up.

Top-down / Recursive

You can think of top-down approach as a combination of #Backtracking and #Memoization.

You create a decision tree and perform a recursive DFS on each choice. To optimize it, we memoize the results of the subproblems while building up to the final decision which breaks the recursion (base case).

Bottom-up / tabulation

The bottom-up approach starts with base-case for one data point (mostly the last, sometimes the first element). After that, optimal result for each data point is an aggregate or sum of the optimal result up until that point. We automatically get the final optimal result once we iterate over the whole data set, since each result derives from the previous.

Greedy Method

Greedy method is used in problems where we need to find an optimal solution. But it does not guarantee optimal solution. Basically, it is useful in scenarios where there could be multiple right answers or solutions.

Makes locally optimal choice => Globally optimal result..

Techniques

Recursion

Caching

Memoization

Used when you see same information coming up and getting processed again and again. The result of such processing is stored, so that, when the same input is encountered again, we can simply refer to the cache.

Pre-computation

Performing certain computations on the input beforehand and caching them for later use.

Might seem similar to memoization. The difference is that here we are performing computations on input, while in memoization we cache the results.

Two Pointer

Any algorithm involving use of two pointers/index variables to traverse over a data structure.

You take two pointers and move them until you find the expected result.

There are many variants of this approach since the approach is only about taking two pointers. It only gets more concrete when we dig deeper.

Categorizing on basis of how the pointers move:

Running from both ends of an array
Slow & Fast Pointers
Running from beginning of 2 arrays / Merging 2 arrays
Split & Merge of an array / Divide & Conquer

Patterns

Algorithmic patterns aren't necessarily a problem themselves, but can be applied to various situations.

#Caching Patterns

When you need to store some info of a previously seen value -> it should be retrievable in O(1) time. This is how its usually done.

Key-value

Many times in algorithmic problems, we want to store state against a key value. An obvious way which comes to mind is using a hashmap. But there can be multiple ways of doing it.

1. Hashtable/dictionary (key-value data structures)

Values(state) which you want to maintain can simply be stored against a key in such data structures.

💡In addition to identifying if an element exists in a dataset, hashmaps can also be used to identify if the dataset contains any duplicate simply by comparing the size of hashmap with the original dataset.

var containsDuplicate = (nums) => new Set(nums).size != nums.length;

2. Array

While not the first thing which comes to mind when thinking of a key-value pairs, arrays can be used in cases where the number of keys are going to be limited.

For example, in cases where the keys are ASCII characters, you can simply create an array of size 128 and store the state against the index corresponding to ASCII value of the character in the array.

If keys are alphabets, the array size would be 52.

Usage examples — String#Sorting character array/string using an integer array

3. BITs

List of values

If its just the values which you need to store you can use a HashSet. It works similar to hash table but has no key-value pairs. Just the keys for quick lookup.

Usage example -> you want to check a string was encountered before or not.

Result corresponding to each index of input

In such cases, you'd usually create an array and store results corresponding to each index in that array. Later the array can be traversed or result for any index can be retrieved to get the optimal/desired result.

Last (few) results

Sometimes in such problems, you would need to store result up until that point. In most cases, it is the last two results.

In that case, you don't need to waste space by storing result for each index. Just take 1-2 variables which will store the last results which you need to look at.

Pre-computation Patterns

Prefix Sum

A pre-computation strategy, where you preprocess and store the sum upto each element before hand, so that, when required in the actual computation, these sums can be quickly queried.

For example:

Array: [1,2,3,4,5,6,7]
Prefix Sum Array: [1,3,6,10,15,21,28]

#Two Pointer Patterns

Slow and fast pointers

Specific pattern of two pointer algorithms where one pointer moves faster than the other.

The movement of fast could be n times that of the slow pointer, where n is any positive integer. Or the slow pointer could be started late from the first node.

Use cases

To detect cycle in a linked list: If there is a circular track and one car is moving faster than the other, the two cars are bound to cross at some point.
To find middle element of a list: When the fast pointer going at 2x of slow pointer reaches the end - slow pointer will be at the middle element of the list.
To find $n^{th}$ element from the end in a list: Start the slow pointer once the fast pointer reaches the $n^{th}$ element and then move both at the same speed. By the time, the fast pointer reaches the end, slow pointer will be at nth element from the end.

Sliding Window

For finding subarrays/substrings with a specific criteria.

Use Two pointers: start and end to represent a window
Move end to find a valid window
When a valid window is found, move start to find a smaller(better) window.