akhanalcs/algorithms

Refeshing Algorithms from MS in Computer Science days.

algorithms

Refreshing Algorithms from Computer Science days.

Helpful links

1. Data Structures and Algorithms in C#

Logarithms

What power do you have to raise the base to, to get another number.

For eg: $log{_2}{16}$ means

• "How many 2s do you multiply together to get 16?" or
• "What power do you have to raise 2 to, to get 16?"

$$\begin{align} log{_2}16&=x \\ 2^x& = 16 \\ x& = 4\end{align}$$

Math formatting reference

Big O Notation

Big O notation tells you the number of operations an algorithm will make.

For eg: In case of Binary search, the running time of the algorithm in Big O notation is $O(\log n)$.

• Algorithm speed isn't measured in seconds, but in growth of the number of seconds.
• Instead, we talk about how quickly the runtime of an algorithm increases as the size of the input increases.
• Run time of algorithms is expressed in Big $O$ notation.
• $O(\log n)$ is faster than $O(n)$, but it gets a lot faster as the list of items you’re searching grows.

Binary Search Algorithm

Binary search, also known as half-interval search, logarithmic search, or binary chop is a search algorithm that finds the position of a target value within a sorted array.

Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.

Binary search runs in logarithmic time in the worst case, making $O(\log n)$ comparisons, where $n$ is the number of elements in the array.

Code example:

algorithms/src/Algorithms/Search/BinarySearcher.cs

Lines 3 to 37 in c8a7b65

	public static class BinarySearcher
	{
	public static int FindIndex(int[] sortedData, int item)
	{
	// Low and high keep track of which part of the list you’ll search in.
	var leftIndex = 0;
	var rightIndex = sortedData.Length - 1;
	// While you haven’t narrowed it down to one element
	while (leftIndex <= rightIndex)
	{
	// Check the middle element
	var midIndex = (leftIndex + rightIndex) / 2;
	var guess = sortedData[midIndex];
	if (guess == item)
	{
	return midIndex;
	}
	// The guess was too high
	if (guess > item)
	{
	rightIndex = midIndex - 1;
	}
	// The guess was too low
	else
	{
	leftIndex = midIndex + 1;
	}
	}
	return -1; // The item does not exist.
	}
	}

Common Big O run times

• $O(\log n)$, also known as log time. Example: Binary search.
• $O(n)$, also known as linear time. Example: Simple search.
• $O(n * \log n)$. Example: A fast sorting algorithm, like quicksort.
• $O(n^2)$. Example: A slow sorting algorithm, like selection sort. Try to remember it like ss so nn -> $n^2$.
• $O(n!)$. Example: A really slow algorithm, like the traveling salesperson. For eg: To go through 5 cities, you have to calculate $5!$ which is $120$. It grows really, really fast. 🤯

Arrays and Linked Lists

Arrays

Sometimes you need to store a list of elements in memory. Suppose you’re writing an app to manage your todos. You’ll want to store the todos as a list in memory. For eg, the todo list is:

• Brunch
• Bocce
• Tea

Storing the todos in array looks like

Now suppose you want to add a fourth task. But the next memory location is taken up by someone else’s stuff.

If you’re out of space and need to move to a new spot in memory every time, adding a new item will be really slow.

Linked Lists

With linked lists, your items can be anywhere in memory. Each item stores the address of the next item in the list. A bunch of random memory addresses are linked together.

You go to the first address, and it says, “The next item can be found at address 123.” So you go to address 123, and it says, “The next item can be found at address 847,” and so on. Adding an item to a linked list is easy: you stick it anywhere in memory and store the address with the previous item.

With linked lists, you never have to move your items.

Insertions and deletions work great in Lists

Lets say you want to add items in a certain order.

With lists, it’s as easy as changing what the previous element points to.

But for arrays, you have to shift all the rest of the elements down.

And if there’s no space, you might have to copy everything to a new location! Lists are better if you want to insert elements into the middle.

Runtimes for common operations on Arrays and Lists

	Arrays	Lists
Reading	$O(1)$	$O(n)$
Insertion	$O(n)$	$O(1)$
Deletion	$O(n)$	$O(1)$

It’s worth mentioning that insertions and deletions are $O(1)$ time only if you can instantly access the element to be deleted. It’s a common practice to keep track of the first and last items in a linked list, so it would take only $O(1)$ time to delete those.

List vs LinkedList in C#

Reference

List<T>	LinkedList<T>
List<T> is essentially just an array (with a wrapper), so random access is efficient.	LinkedList<T> is composed of nodes with each node consisting its value and pointers/reference to the next and previous node. Elements' access is only efficient if it's done consecutively (either forwards or backwards). Random access is relatively expensive since it must walk the chain each time (hence why it doesn't have an indexer).
In most cases, List<T> is more useful. List<T> can only cheaply add/remove at the end of the list because it doesn't require shifting of elements.	Adding or removing elements from a LinkedList<T> can be done quickly at any position given you have a reference to a node close to the operation's location. LinkedList<T> will have less cost when adding/removing items in the middle of the list. For example: LinkedList<int> myList = new LinkedList<int>(); myList.AddLast(1); // We keep a reference to this node LinkedListNode<int> myNode = myList.AddLast(2); myList.AddLast(3); We can insert a new element after the element 2. Since you already have a reference to this Node, you can simply use the .AddAfter method: // This will insert 4 after 2 myList.AddAfter(myNode, 4);
Index-based operations like accessing or updating an element are fast. O(1).	There's no indexed access in LinkedList<T> so random access is relatively expensive since it must walk the chain each time (hence why it doesn't have an indexer). O(n)
For operations which involve adding or removing elements not at the end of the List<T>, it incurs O(n) cost due to shifting of elements.	Since each node points directly to its next node and previous node in a LinkedList<T>, insertions and deletions in known locations can be done in O(1) time.
List<T> requires contiguous memory space and could incur overhead when resizing.	LinkedList<T> nodes can be anywhere in memory, which makes it more efficient when the list grows frequently.
List<T> generally more suited for cases where the size of the list is known in advance, or needs of random access operations are high.	LinkedList<T> is often preferable when you need to frequently add or remove items in the list and the access is mostly sequential.

Selection Sort Algorithm

Suppose you have a bunch of music on your computer. For each artist, you have a play count. You want to sort this list from most to least played, so that you can rank your favorite artists.

One way is to go through the list and find the most-played artist. Add that artist to a new list.

Do it again to find the next-most-played artist.

Keep doing this, and you’ll end up with a sorted list.

Now let's find how long it takes to run. Remember that $O(n)$ time means you touch every element in a list once.

You have an operation that takes $O(n)$ time, and you have to do that $n$ times:

This takes $O(n × n)$ time or $O(n^2)$ time.

Code example:

algorithms/src/Algorithms/Sort/SelectionSorter.cs

Lines 5 to 31 in f833848

	// [3, 2, 1, 5, 4]
	public static void Sort(int[] unSortedData)
	{
	for (var i = 0; i < unSortedData.Length; i++)
	{
	// We start saying that the first item is the smallest
	var smallestIndex = i;
	// And go through the rest of the items by comparing it to the unSortedData[smallestIndex] item
	// If we find a new item that's smaller, we update our index to point to it
	// At the end of this loop, we have smallest item
	for (var j = i + 1; j < unSortedData.Length; j++)
	{
	if (unSortedData[j] < unSortedData[smallestIndex])
	{
	smallestIndex = j;
	}
	}
	// Swap the smallest item with the current item
	(unSortedData[i], unSortedData[smallestIndex]) = (unSortedData[smallestIndex], unSortedData[i]);
	// The above thing is same as below:
	// var temp = unSortedData[i];
	// unSortedData[i] = unSortedData[smallestIndex];
	// unSortedData[smallestIndex] = temp;
	}
	}

Tested using:

algorithms/tests/Algorithms.UnitTests/Sort/SelectionSorterTests.cs

Lines 5 to 20 in 929d1c5

	public class SelectionSorterTests
	{
	[Test]
	public void SelectionSorter_Sorts_Items()
	{
	// Arrange
	int[] unSortedItems = [3, 2, 1, 5, 4];
	int[] sortedItems = [1, 2, 3, 4, 5];
	// Act
	SelectionSorter.Sort(unSortedItems);
	// Assert
	Assert.That(unSortedItems, Is.EqualTo(sortedItems));
	}
	}

Recursion

Suppose you’re digging through your grandma’s attic and come across a mysterious locked suitcase.

Grandma tells you that the key for the suitcase is probably in this other box.

Here's a way to find the key using recursion (pseudocode)

# Every recursive function has two parts: the base case, and the recursive case
def look_for_key(box):
  for item in box:
    # Recursive case: when the function calls itself
    if item.is_a_box():
      look_for_key(item) # <--- Recursion!
    # Base case: when the function doesn't call itself again
    elif item.is_a_key():
      print “found the key!”

Check out the Recursion folder for code examples.

Quicksort

Quicksort is a sorting algorithm. It’s much faster than selection sort $O(n^2)$ and is frequently used in real life. In the worst case, quicksort takes $O(n^2)$ time. In the average case, quicksort takes $O(n * \log n)$ time.

The simplest arrays that a sorting algorithm can handle

Empty arrays and arrays with just one element will be the base case. You can just return those arrays as is—there’s nothing to sort:

def quicksort(array):
  if len(array) < 2:
    return array

An array with two elements is pretty easy to sort too.

Consider an array of 4 elements.

$33$	$10$	$15$	$7$

Remember that you're using D&C, so you want to break down this array until you're at the base case.

First, pick an element from the array. This element is called the pivot. For eg: $33$.

Now find the elements smaller than the pivot and the elements larger than the pivot. This is called partitioning.

Now you have

• A sub-array of all the numbers less than or equal to the pivot
• The pivot
• A sub-array of all the numbers greater than the pivot

The array on the left has three elements. You already know how to sort an array of three elements: call quicksort on it recursively.

quicksort([10, 15, 7]) + [33] + quicksort([])
> [7, 10, 15] + [33] + []
> [7, 10, 15, 33]

Code example:

algorithms/tests/Algorithms.UnitTests/Sort/QuickSorterTests.cs

Lines 5 to 18 in 4215d8c

	public class QuickSorterTests
	{
	[Test]
	public void QuickSorter_Sorts_Items()
	{
	// Arrange
	int[] unSortedData = [3, 2, 1, 5, 4];
	int[] sortedItems = [1, 2, 3, 4, 5];
	// Act
	var result = QuickSorter.Sort(unSortedData);
	// Assert
	Assert.That(result, Is.EqualTo(sortedItems));
	}
	}

Hash Functions

A hash function is a function where you put in a string and you get back a number.

• It needs to be consistent. For example, suppose you put in “apple” and get back “4”. Every time you put in “apple”, you should get “4” back. Without this, your hash table won’t work.
• It should map different words to different numbers. For example, a hash function is no good if it always returns “1” for any word you put in. In the best case, every different word should map to a different number.
• The hash function knows how big your array is and only returns valid indexes. So if your array is 5 items, the hash function doesn’t return 100 … that wouldn’t be a valid index in the array.

Let's create a price catalog using it.

Start with an empty array. You’ll store all of your prices in this array.

Let’s add the price of an apple. Feed “apple” into the hash function.

The hash function outputs “3”. So let’s store the price of an apple at index 3 in the array.

Now you ask, “Hey, what’s the price of an apple?” You don’t need to search for it in the array. Just feed “apple” into the hash function. It tells you that the price is stored at index 3.

The hash function tells you exactly where the price is stored, so you don’t have to search at all!

Good hash function

A good hash function distributes values in the array evenly.

A bad hash function groups values together and produces a lot of collisions.

Hash Table

Hash Table = Hash Function + Array

C# has a type Dictionary<TKey,TValue> which is type-safe and can often be used as an alternative to Hashtable. For example:

Dictionary<string, double> catalog = new();

catalog["apple"] = 0.67;
catalog["milk"] = 1.49;
catalog["avocado"] = 0.99;

foreach(var key in catalog.Keys)
{
    Console.WriteLine($"Key: {key}, Value: {dictionary[key]}");
}

Performance of Hash tables

In the average case, hash tables take O(1) for everything. $O(1)$ is called constant time. It doesn’t mean instant. It means the time taken will stay the same, regardless of how big the hash table is.

   

Comparision of Hash tables to Arrays and Linked Lists

Breadth-first search

The algorithm to solve a shortest-path problem is called breadth-first search.

Breadth�first search runs on graphs. It can help answer two types of questions:

• Question type 1: Is there a path from node A to node B?
• Question type 2: What is the shortest path from node A to node B?

Suppose you’re in San Francisco, and you want to go from Twin Peaks to the Golden Gate Bridge. You want to get there by bus, with the minimum number of transfers. Here are your options:

The shortest route to the bridge is three steps long.

To figure out how to get from Twin Peaks to the Golden Gate Bridge, there are two steps:

1. Model the problem as a graph.
2. Solve the problem using breadth-first search.

Queues

The queue is called a FIFO data structure: First In, First Out. In contrast, a stack is a LIFO data structure: Last In, First Out.

Example 1: Find the mango seller

You want to find the mango seller using breadth-first search.

To implement the graph in code, you can use a data structure that lets you express relationships: a hash table!

Here's how it looks like in Python

graph = {}
graph[“you”] = [“alice”, “bob”, “claire”]
# Notice that in a directed graph like this, you only put names that have arrow directed towards them.
graph[“bob”] = [“anuj”, “peggy”]
graph[“alice”] = [“peggy”]
graph[“claire”] = [“thom”, “jonny”]
graph[“anuj”] = []
graph[“peggy”] = []
graph[“thom”] = []
graph[“jonny”] = []

This is how you'll implement the search

Here's how the search looks like in Python

def search(name):
  search_queue = deque()
  search_queue += graph[name] 
  searched = [] # This array is how you keep track of which people you’ve searched before.
  while search_queue:
    person = search_queue.popleft() 
    if not person in searched: # Only search this person if you haven’t already searched them.
      if person_is_seller(person):
        print person + “ is a mango seller!”
        return True
      else:
        search_queue += graph[person] 
      searched.append(person) # Marks this person as searched
  return False

search(“you”)

Implementation of this in C# looks like below

algorithms/tests/Algorithms.UnitTests/Search/BreadthFirstSearcherTests.cs

Lines 7 to 31 in 2840b0d

	[Test]
	public void BFS_Finds_Mango_Seller()
	{
	// Arrange
	var graph = new Dictionary<string, string[]>
	{
	{ "you", ["bob", "claire", "alice"] },
	{ "bob", ["anuj", "peggy"] },
	{ "alice", ["peggy"] },
	{ "claire", ["jonny", "thom"] },
	{ "anuj", [] },
	{ "peggy", [] },
	{ "jonny", [] },
	{ "thom", [] }
	};
	bool IsMangoSeller(string person) => person.EndsWith('m');
	void ShowMangoSeller(string person) => Console.WriteLine($"{person} is a mango seller!");
	// Act
	var searchResult = BreadthFirstSearcher.Search(graph, "you", IsMangoSeller, ShowMangoSeller);
	// Assert
	Assert.That(searchResult, Is.EqualTo(true));
	}

algorithms/src/Algorithms/Search/BreadthFirstSearcher.cs

Lines 3 to 39 in 2840b0d

	public static class BreadthFirstSearcher
	{
	// check is a delegate that takes a string and returns a bool. It defines what's your basis for the search.
	// action is a delegate that take a string but doesn't return anything. It defines what you want to do when you find something.
	public static bool Search(Dictionary<string, string[]> graph,
	string startVertex,
	Func<string, bool> check,
	Action<string> action)
	{
	// Create a queue and initialize it with the neighbors of the startVertex
	var queue = new Queue<string>(graph[startVertex]);
	// Array supports O(1) lookup time by index.
	// HashSet supports O(1) lookup time to find a value.
	var visited = new HashSet<string>();
	while (queue.Count > 0)
	{
	var currentVertex = queue.Dequeue();
	if (visited.Contains(currentVertex)) continue;
	// Check if it's the vertex you were looking for
	if (check(currentVertex))
	{
	action(currentVertex);
	return true;
	}
	// If you didn't find what you were looking for in the currentVertex, add its neighbors to the queue
	foreach (var vertex in graph[currentVertex]) queue.Enqueue(vertex);
	visited.Add(currentVertex);
	}
	return false;
	}
	}

Running time

If you search your entire network for a mango seller, that means you’ll follow each edge (remember, an edge is the arrow or connection from one person to another). So the running time is at least $O(number of edges)$.

You also keep a queue of every person to search. Adding one person to the queue takes constant time: $O(1)$. Doing this for every person will take $O(number of people)$ total. Breadth-first search takes $O(number of people + number of edges)$, and it’s more commonly written as $O(V+E)$. $V$ for number of vertices, $E$ for number of edges.

Dependency

Arrow is pointed towards a dependency.

It tells you that I can’t eat breakfast until I’ve brushed my teeth. So “eat breakfast” depends on “brush teeth”.

On the other hand, showering doesn’t depend on brushing my teeth, because I can shower before I brush my teeth.

From this graph, you can make a list of the order in which I need to do my morning routine:

1. Wake up	1. Wake up
2. Shower	2. Brush teeth
3. Brush teeth	3. Shower
4. Eat breakfast	4. Eat breakfast

If task A (Shower) depends on task B (Wake up), task A shows up later in the list.

Dependent (Shower) always shows up later because the dependency (Wake up) needs to be resolved first.

Node where the arrow HEAD is pointed to, will always appear first. Like how HEAD is at the top of our body.

Tree

A tree is a special type of graph, where no edges ever point back.

Dijkstra's algorithm (finds the path with smallest total weight)

Compare it to BFS (which finds the path with fewest segments)

Use Dijkstra's algorithm	Use Breadth first search algorithm

Weighted graphs vs Unweighted graphs

To calculate the shortest path in an unweighted graph, use breadth-first search. To calculate the shortest path in a weighted graph, use Dijkstra’s algorithm.

Directed graphs vs undirected graphs

An undirected graph means that both nodes point to each other. That’s a cycle!

With an undirected graph, each edge adds another cycle. Dijkstra's algorithm works even if there is a cycle, as long as it is a positive weight cycle.

Example

Dijkstra’s algorithm has four steps:

1. Find the cheapest node. This is the node you can get to in the least amount of time.
2. Check whether there’s a cheaper path to the neighbors of this node. If so, update their costs.
3. Repeat until you’ve done this for every node in the graph.
4. Calculate the final path.

For eg:

Imagine you have a book, and you want trade it for a piano. Your friends Alex, Amy and Beethoven are willing to trade various items.

How are you going to figure out the path from the book to the piano where you spend the least amount of money?

Parent (When cost updates, you get a parent)	Node	Standing at Book (only neighbors of Book updated) Cost 1	Standing at Poster (only neighbors of Poster updated) Cost 2	Standing at LP (only neighbors of LP updated) Cost 3	Standing at Guitar (only neighbors of Guitar updated) Cost 4	Standing at Drumset (only neighbors of Drumset updated) Cost 5
Book	LP	$5$ 💥 Updated	$5$ ^^^^ C2W 🏆	$5$	$5$	$5$
Book	Poster	$0$ 💥 Updated ^^^^ C1W 🏆	$0$	$0$	$0$	$0$
Poster -> LP	Guitar	$∞$	C1W + $30$ = $30$ 💥 Updated	C2W + $15$ = $20$ 💥 Updated ^^^^ C3W 🏆	$20$	$20$
Poster -> LP	Drumset	$∞$	C1W + $35$ = $35$ 💥 Updated	C2W + $20$ = $25$ 💥 Updated	$25$ ^^^^ C4W 🏆	$25$
Guitar -> Drumset	Piano	$∞$	$∞$	$∞$	C3W + $20$ = $40$ 💥 Updated	C4W + $10$ = $35$ 💥 Updated ^^^^ C5W 🏆
		At this point: ✅ Book	At this point: ✅ Book ✅ Poster	At this point: ✅ Book ✅ Poster ✅ LP	At this point: ✅ Book ✅ Poster ✅ LP ✅ Guitar	At this point: ✅ Book ✅ Poster ✅ LP ✅ Guitar ✅ Drumset

At this point, you've run Dijkstra's algorithm for every node (you don't need to run it for the finish node).

Now you know that the shortest/ cheapest path costs $35. Let's figure out the path.

Piano has Drumset as parent, so you trade Drumset for Piano. And Drumset has LP as parent. And LP has Book as parent.

So here's the series of trades you'll need to make:

Negative weight edges

Imagine that Rama wants to get Drums.

The second path costs him $2 less, so he should take that path, right?
Well, guess what? If you run Dijkstra’s algorithm on this graph, Rama will take the wrong path. He’ll take the longer path.

You can’t use Dijkstra’s algorithm if you have negative-weight edges. Negative-weight edges break the algorithm.

If you want to find the shortest path in a graph that has negative-weight edges, there’s an algorithm for that! It’s called the Bellman-Ford algorithm.

Implementation

To code this example, you’ll need three hash tables: Graph, costs and parents.

To implement the graph, store the neighbors and the cost for getting to that neighbor. For eg:

algorithms/tests/Algorithms.UnitTests/Greedy/DijkstraAlgorithmTests.cs

Lines 19 to 26 in 733e35e

	// Store the neighbors and the cost for getting to that neighbor
	var graph = new Dictionary<string, Dictionary<string, int>>
	{
	["Start"] = new() { { "A", 6 }, { "B", 2 } }, // For eg: Going from Start to A and B
	["A"] = new() { { "Finish", 1 } },
	["B"] = new() { { "A", 3 }, { "Finish", 5 } },
	["Finish"] = new()
	};

Next you need a hash table to store the costs for each node. For example.

algorithms/tests/Algorithms.UnitTests/Greedy/DijkstraAlgorithmTests.cs

Lines 11 to 17 in 733e35e

	var costs = new Dictionary<string, int>
	{
	// Costs from "start" to:
	{ "A", 6 },
	{ "B", 2 },
	{ "Finish", int.MaxValue }
	};

You also need another hash table for the parents.

algorithms/tests/Algorithms.UnitTests/Greedy/DijkstraAlgorithmTests.cs

Lines 28 to 34 in 733e35e

	// Store the parents
	var parents = new Dictionary<string, string?>
	{
	{ "A", "Start" },
	{ "B", "Start" },
	{ "Finish", null }
	};

Finally, you need an array to keep track of all the nodes you’ve already processed, because you don’t need to process a node more than once

algorithms/src/Algorithms/Greedy/DijkstraAlgorithm.cs

Lines 9 to 10 in 733e35e

	// Store the visited nodes
	var visited = new HashSet<string>();

The algorithm looks like this

Check out the code to see how I've implemented it in .NET 8.

Greedy Algorithms

Set covering problem

Given a set of elements ${1, 2, …, n}$ (called the universe) and a collection $S$ of $m$ subsets whose union equals the universe, the set cover problem is to identify the smallest sub-collection of $S$ whose union equals the universe. For example, consider the universe $U = {1, 2, 3, 4, 5}$ and the collection of sets $S = { {1, 2, 3}, {2, 4}, {3, 4}, {4, 5} }$. Clearly the union of $S$ is $U$. However, we can cover all elements with only two sets: ${ {1, 2, 3}, {4, 5} }$. Therefore, the solution to the set cover problem has size 2.

Example:

Suppose you’re starting a radio show. You want to reach listeners in all 8 states. You have to decide what stations to play on to reach all those listeners. It costs money to be on each station, so you’re trying to minimize the number of stations you play on.

 

Check out the code to see how I've implemented it in .NET 8.

NP Complete (Page 159)

Some problems are famously hard to solve. The traveling salesperson and the set-covering problem are two examples. A lot of smart people think that it’s not possible to write an algorithm that will solve these problems quickly.

That's why we solve them by approximating using Greedy algorithms.

There’s no easy way to tell if the problem you’re working on is NP-complete.

Here are some giveaways:

• Your algorithm runs quickly with a handful of items but really slows down with more items.
• “All combinations of X” usually point to an NP-complete problem.
• Do you have to calculate “every possible version” of X because you can’t break it down into smaller sub-problems? Might be NP-complete.
• If your problem involves a sequence (such as a sequence of cities, like traveling salesperson), and it’s hard to solve, it might be NP-complete.
• If your problem involves a set (like a set of radio stations) and it’s hard to solve, it might be NP-complete.
• Can you restate your problem as the set-covering problem or the traveling-salesperson problem? Then your problem is definitely NP-complete.

Dynamic Programming (Page 161)

Dynamic programming starts by solving subproblems and builds up to solving the big problem.

• Dynamic programming is useful when you’re trying to optimize something given a constraint.
• You can use dynamic programming when the problem can be broken into discrete subproblems.
• Every dynamic-programming solution involves a grid.
• The values in the cells are usually what you’re trying to optimize.
• Each cell is a subproblem, so think about how you can divide your problem into subproblems.
• There’s no single formula for calculating a dynamic-programming solution.

Knapsack problem

Example: Optimizing your travel itinerary

Suppose you’re going to London for a nice vacation. You have two days there and a lot of things you want to do. You can’t do everything, so you make a list.

Can you figure out what you should see, based on this list?

Draw the dynamic-programming grid for this list.

Note: The formula looks intimidating, but it's quite intuitive, which I've explained in the grid below.

$cell[i][j] = \max(\text{Previous Max: Value at } cell[i-1][j], \text{Value of current item + value of remaining space: }cell[i-1][j-\text{item's weight}])$

_________________	1/2 day ________	1 day ___________________________	1 1/2 day ___________________________	2 days ___________________________
Westminster Abbey Time: 1/2 day Rating: 7	$7$ (0,0) W	$7$ (0,1) W	$7$ (0,2) W	$7$ (0,3) W
Globe Theater Time: 1/2 day Rating: 6	$7$ (1,0) W	$13$ (1,1) = MAX (Prev Max:Right above it, Current rating + Remaining day rating) = MAX (7, 6 + (1 day - 1/2 day)) = MAX (7, 6 + value at (0,0)) = MAX (7, 6 + 7) = MAX (7, 13) = 13 GW	$13$ (1,2) GW	$13$ (1,3) GW
National Gallery Time: 1 day Rating: 9	$7$ (2,0) W	$13$ (2,1) = MAX (Prev Max:Right above it, Current rating + Remaining day rating) = MAX (13, 9 + 0) = 13 GW	$16$ (2,2) = MAX (Prev Max:Right above it, Current rating + Remaining day rating) = MAX (13, 9 + (1.5 day - 1 day)) = MAX (13, 9 + value at (1,0)) = MAX (13, 9 + 7) = MAX (13, 16) = 16 NW	$22$ (2,3) = MAX (Prev Max:Right above it, Current rating + Remaining day rating) = MAX (13, 9 + (2 days - 1 day)) = MAX (13, 9 + value at (1,1)) = MAX (13, 9 + 13) = MAX (13, 22) = 22 NGW
British Museum Time: 2 days Rating: 9	$7$ (3,0) W	$13$ (3,1) GW	$16$ (3,2) NW	$22$ (3,3) NGW
St. Paul's Cathedral Time: 1/2 day Rating: 8	$8$ (4,0) S	$15$ (4,1) SW	$21$ (4,2) SGW	$24$ (4,3) SNW

Final answer:

• St. Paul's Cathedral
• National Gallery
• Westminster Abbey

Example: Optimizing your travel packing

Check out my answer on StackOverflow.

Longest common substring

Suppose you run dictionary.com. Someone types in a word, and you give them the definition. But if someone misspells a word, you want to be able to guess what word they meant. Alex is searching for fish, but he accidentally put in hish. That’s not a word in your dictionary, but you have a list of words that are similar, like: fish, vista etc.

Which word did Alex mean to type: fish or vista?

Start with the grids:

• Fish
  
• Vista

hish and fish have a substring of three letters in common. hish and vista have a substring of two letters in common.
Alex probably meant to type fish.

Formula

if word_a[i] == word_b[j]:           # The letters match
 cell[i][j] = cell[i-1][j-1] + 1
else:                                # The letters don’t match
 cell[i][j] = 0 

C# Implementation

Example of this in C# is well documented here.

Longest common subsequence

Is the number of letters in a sequence that the two words have in common.

Suppose Alex accidentally searched for fosh. Which word did he mean: fish or fort?

Alex probably meant to type fish.

Formula

if word_a[i] == word_b[j]:                      # The letters match.
 cell[i][j] = cell[i-1][j-1] + 1
else:                                           # The letters don’t match.
 cell[i][j] = max(cell[i-1][j], cell[i][j-1])

C# Implementation

Example of this in C# is well documented here.

k-nearest neighbors (page 187)

Classifying oranges vs grapefruit

How would you classify this fruit?

One way is to look at the neighbors of this spot. Take a look at the three closest neighbors of this spot.

More neighbors are oranges than grapefruit. So this fruit is probably an orange. Congratulations: You just used the k-nearest neighbors (KNN) algorithm for classification!

The KNN algorithm is simple but useful! If you’re trying to classify something, you might want to try KNN first.

Recommender System

Suppose you’re Netflix, and you want to build a movie recommendations system for your users.

You can plot every user on a graph.

These users are plotted by similarity, so users with similar taste are plotted closer together.

Suppose you want to recommend movies for Priyanka. Find the five users closest to her.

Justin, JC, Joey, Lance, and Chris all have similar taste in movies. So whatever movies they like, Priyanka will probably like too!

Once you have this graph, building a recommendations system is easy. If Justin likes a movie, recommend it to Priyanka.

You graphed the users by similarity. How do you figure out how similar two users are?

Feature extraction

Here’s how you can convert users into a set of numbers. When users sign up for Netflix, have them rate some categories of movies based on how much they like those categories. For each user, you now have a set of ratings.

Now each user is represented by a set of five numbers.

What's the distance between Priyanka and Justin?

Let's use the distance formula to find it:

$$\begin{align} & \sqrt{(a_1-a_2)^2 + (b_1-b_2)^2 + (c_1-c_2)^2 + (d_1-d_2)^2 + (e_1-e_2)^2} \\\ = & \sqrt{(3-4)^2 + (4-3)^2 + (4-5)^2 + (1-1)^2 + (4-5)^2} \\\ = & \sqrt{1 + 1 + 1 + 0 + 1} \\\ = & \sqrt{4} \\\ = & 2 \end{align}$$

Priyanka and Justin are pretty similar.

What’s the difference between Priyanka and Morpheus? Priyanka and Morpheus are 24 apart.

The distance tells you that Priyanka’s tastes are more like Justin’s than Morpheus’s.

If you’re a Netflix user, Netflix will keep telling you, “Please rate more movies. The more movies you rate, the better your recommendations will be.” Now you know why. The more movies you rate, the more accurately Netflix can see what other users you’re similar to.

Regression

These are the two basic things you’ll do with KNN—classification and regression:

• Classification = categorization into a group
• Regression = predicting a response (like a number)

Where to go next (page 202)

Binary search tree

Allows you to insert into the array without having to sort the array afterward.

For every node, the nodes to its left are smaller in value, and the nodes to the right are larger in value.

Searching for an element in a binary search tree takes $O(\log n)$ time on average and $O(n)$ time in the worst case.

Running times:

	Sorted Array	Binary Search Tree
Search	$O(\log n)$	$O(\log n)$
Insert	$O(n)$	$O(\log n)$
Delete	$O(n)$	$O(\log n)$

Binary search trees don’t get random access like you get with array.

Those performance times are also on average and rely on the tree being balanced. Suppose you have an imbalanced tree like the one shown below.

This tree doesn’t have very good performance, because it isn’t balanced. There are special binary search trees that balance themselves. One example is the red-black tree.

Built in implementation of red-black tree in .NET: SortedSet<T> class or SortedDictionary<TKey,TValue> class.

algorithms/tests/Algorithms.UnitTests/Trees/BinarySearchTreeTests.cs

Lines 40 to 48 in e3e1ddd

	[Test]
	public void Built_In_BST_Can_Add_And_Retrieve_Items()
	{
	// Arrange and also Act I guess
	SortedSet<int> bst = [5, 7, 3, 6];
	// Assert
	CollectionAssert.AreEqual(bst, new[] { 3, 5, 6, 7 });
	}

Heap

The heap is one maximally efficient implementation of an abstract data type called a priority queue and in fact, priority queues are often referred to as "heaps", regardless of how they may be implemented.

Built in min-heap implementation in .NET: PriorityQueue<TElement,TPriority> class.

algorithms/tests/Algorithms.UnitTests/Trees/BinaryHeapTests.cs

Lines 6 to 20 in 2dca326

	[Test]
	public void BinaryMinHeap_Returns_Items_In_Ascending_Order()
	{
	// Arrange
	var pq = new PriorityQueue<string, int>();
	pq.Enqueue("internet", 5);
	pq.Enqueue("food", 9);
	pq.Enqueue("water", 10);
	// Act
	var lowestPriorityItem = pq.Dequeue();
	// Assert
	Assert.That(lowestPriorityItem, Is.EqualTo("internet"));
	}

Inverted Indexes

It’s commonly used to build search engines.

Suppose you have three web pages with this simple content.

Let’s build a hash table from this content. The keys of the hash table are the words, and the values tell you what pages each word appears on.

Now suppose a user searches for "adit". Below code shows how it's implemented.

algorithms/tests/Algorithms.UnitTests/Search/InvertedIndexTests.cs

Lines 5 to 25 in 54f26bc

	[Test]
	public void Inverted_Index_Maps_Content_To_Webpages()
	{
	//Arrange
	var invertedIndex = new Dictionary<string, string[]>
	{
	{ "hi", ["a.com", "b.com"] },
	{ "there", ["a.com", "c.com"] },
	{ "adit", ["b.com"] },
	{ "we", ["c.com"] },
	{ "go", ["c.com"] },
	};
	// Act
	// Let's say user searches for "adit", and we want to show which webpages it appears on.
	const string searchTerm = "adit";
	var webpages = invertedIndex.TryGetValue(searchTerm, out var value) ? value : [];
	// Assert
	CollectionAssert.AreEqual(new[] { "b.com" }, webpages);
	}

Fourier transform

Given a smoothie, the Fourier transform will tell you the ingredients in the smoothie.

Or, to put it another way, given a song, the transform can separate it into individual frequencies.
The Fourier transform tells you exactly how much each note contributes to the overall song. So you can just get rid of the notes that aren’t important. That’s how the MP3 format works!

People use the Fourier transform to try to predict upcoming earthquakes and analyze DNA.
You can use it to build an app like Shazam, which guesses what song is playing.

MapReduce (Parallel algorithm)

It’s fine to run a parallel algorithm on your laptop if you need two to four cores, but what if you need hundreds of cores? Then you can write your algorithm to run across multiple machines.

The MapReduce algorithm is a popular distributed algorithm. You can use it through the popular open source tool Apache Hadoop.

MapReduce is built up from two simple ideas: the map function and the reduce function.

The map function is simple: it takes an array and applies the same function to each item in the array.

>>> arr1 = [1, 2, 3, 4, 5]
>>> arr2 = map(lambda x: 2 * x, arr1)
[2, 4, 6, 8, 10]
# OR
>>> arr1 = # A list of URLs
>>> arr2 = map(download_page, arr1) # Imagine doing this for thousands of urls across 100s of machine. This is the idea behind "map" in MapReduce.

The reduce function confuses people sometimes "reduces” a whole list of items down to one item.

```py >>> arr1 = [1, 2, 3, 4, 5] >>> reduce(lambda x,y: x+y, arr1) 15 ```

MapReduce uses these two simple concepts to run queries about data across multiple machines. When you have a large dataset (billions of rows), MapReduce can give you an answer in minutes where a traditional database might take hours.

Bloom filters and HyperLogLog

Just read Page 211.

They are probabilistic algorithms which are useful when you have a lot of data and are satisfied with approximate answers.

SHA algorithms

SHA is a hash function. It generates a hash, which is just a short string.

Usage: Comparing files

The hash function for hash tables went from string to array index, whereas SHA goes from string to string.

You can use SHA to tell whether two files are the same. This is useful when you have very large files. Suppose you have a 4 GB file. You want to check whether your friend has the same large file. You don’t have to try to email them your large file. Instead, you can both calculate the SHA hash and compare it.

Usage: Checking passwords

SHA is also useful when you want to compare strings without revealing what the original string was.

For example, suppose Gmail gets hacked, and the attacker steals all the passwords! Is your password out in the open? No, it isn’t. Google doesn’t store the original password, only the SHA hash of the password! When you type in your password, Google hashes it and checks it against the hash in its database.

It’s a one-way hash. But you can’t get the original string from the hash.

Locality-sensitive hashing (Simhash)

SHA has another important feature: it’s locality insensitive. Suppose you have a string, and you generate a hash for it.

dog --> cd6357

If you change just one character of the string and regenerate the hash, it’s totally different!

dot --> e392da

This is good because an attacker can’t compare hashes to see whether they’re close to cracking a password.

Sometimes, you want the opposite: you want a locality-sensitive hash function. That’s where Simhash comes in.

If you make a small change to a string, Simhash generates a hash that’s only a little different. This allows you to compare hashes and see how similar two strings are, which is pretty useful!

• A teacher could use Simhash to see whether a student was copying an essay from the web.
• Google uses Simhash to detect duplicates while crawling the web.

Simhash is useful when you want to check for similar items!

Diffie-Hellman key exchange

How do you encrypt a message so it can only be read by the person you sent the message to?

The easiest way is to come up with a cipher, like a = 1, b = 2, and so on. Then if I send you the message “4,15,7”, you can translate it to “d,o,g”.

Issues with this:

• Both parties need to know the cipher. This could be leaked.
• Cipher could be guessed and easily broken. The Germans used a much more complicated cipher in WWII, but it was still cracked.

Diffie-Hellman solves both of the above issues.

• Both parties don’t need to know the cipher. So we don’t have to meet and agree to what the cipher should be.
• The encrypted messages are extremely hard to decode.

Diffie-Hellman has two keys: a public key and a private key. The public key is exactly that: public. You can post it on your website, email it to friends, or do anything you want with it. You don’t have to hide it.
When someone wants to send you a message, they encrypt it using the public key. An encrypted message can only be decrypted using the private key. As long as you’re the only person with the private key, only you will be able to decrypt this message!
The Diffie-Hellman algorithm is still used in practice, along with its successor, RSA.

Linear programming

Linear programming is used to maximize something given some constraints.

For example, suppose your company makes two products, shirts and totes. Shirts need 1 meter of fabric and 5 buttons. Totes need 2 meters of fabric and 2 buttons. You have 11 meters of fabric and 20 buttons. You make $2 per shirt and $3 per tote. How many shirts and totes should you make to maximize your profit?
Here you’re trying to maximize profit, and you’re constrained by the amount of materials you have.

All the graph algorithms can be done through linear programming instead.

Linear programming is a much more general framework, and graph problems are a subset of that. 🤯