Illustrated algorithm examples by types

Algorithms are set of rules that instruct the computer how to perform a task. The most used types of algorithms are Binary search, sorting, Divide and conquer, Two pointers, Greedy, Recursion, Backtracking and Dynamic programming. The illustrated algorithm examples feature well-known examples in each algorithm types.

algorithm examples

Table of Content

  1. Binary search
  2. Simple sorting
  3. Divide and conquer
  4. Two pointers
  5. Greedy
  6. Recursion
  7. Backtracking
  8. Dynamic programming


1. Binary search


binary search

Binary search is an efficient algorithm for finding an item from an ordered list of items. It works by repeatedly dividing in half the portion of the list, until narrowing down the possible locations to just one. The time complexity reduces from O(n) to O(logn).

binary search

Binary search in Java, JavaScript, Python and Doodle


2. Simple sorting


sorting algorithms

Sorting is probably one of the most studied algorithm examples. It is a process that takes an array or strings as input, performs specified operations,  and outputs a sorted order of array or strings. Simple sorting algorithms uses two nested loops to compare two elements and change position if they are not ordered. They are not efficient as the time complexity is O(n^2).

Example 1: Bubble sort – compares adjacent elements and swaps them if they are in the wrong order.

bubble sort

Bubble sort in Java, JavaScript, Python and Doodle

Example 2: Selection sort – repeatedly finds the minimum element from unsorted part and puts it at the beginning.

selection sort

Selection sort in Java, JavaScript, Python and Doodle

Example 3: Insertion sort – repeatedly take an element from the input data and inserts it into the position so that its value is between the previous and the next element.

insert sort

Insertion sort in Java, JavaScript, Python and Doodle


3. Divide and conquer


divide and conquer

Divide-and-conquer technique works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.

Example 1: Merge sort – divides the array in half, sorts each of those halves, and then merges them together.

merge sort

Merge sort in Java, JavaScript, Python and Doodle

Example 2: Quicksort – partitions the array into two subarrays based on the pivot, move the larger ones to the right, and smaller ones to the left.  

quick sort

Quicksort in Java, JavaScript, Python and Doodle


4. Two pointers


two pointers

Two pointers are two indices in array, pointing to either start and end, or slower and faster. They move in different direction or pace in each iteration. By using two pointers in the array, two elements are processed per loop. This helps to reduce the time with fewer iterations.

Example 1: Search in sorted matrix – search when the matrix is sorted horizontally and vertically (Time complexity should be O(n)).

search sorted matrix

Matrix operations in Java, JavaScript, Python

Example 2: Sort squares – sort the squares of elements in a sorted array (Time complexity should be O(n)). 

sort square

Sort squares with optimization


5. Greedy


greedy algorithm

Greedy algorithm chooses the most obvious and immediate benefit item from the list, so that the locally optimal choice leads to a globally-optimal solution. It is usually implemented by sorting or partially sorting (Priority queue).

Example 1: Find shortest path with Dijkstra- repeatedly picks the un-visited vertex with the lowest distance. When all vertices have been evaluated, the result is the shortest path.

shortest path with dijkstra

Dijkstra in Java, JavaScript, Python

Example 2: Huffman coding – generate the binary code based on the frequencies of corresponding characters in the input string. 

huffman coding

Huffman coding in Java, JavaScript, Python


6. Recursion


recursion

Recursion is a technique that a function or an algorithm calls itself. The termination condition should be defined so that when the condition is met, the rest of call stacks return from the last call to the first.

Example 1: Clean directories in file system – clean out files that are older than certain dates, and remove the empty directories after the files are deleted.

clean directories

Clean directories in file system

Example 2: Factorial numbers – denoted as n!, is the product of all integers between n and 1. n! = n x (n-1) x (n-2) … x1. 

factorial call stacks

Factorial number in Java, JavaScript, Python and Doodle


7. Backtracking


backtracking

Backtracking is a method for solving problems recursively. It incrementally builds candidates to the solutions, and removes the candidates (“backtracks”) that fail to satisfy the constraints of the problems.

Example 1: Detect cycle in directed graph – detect whether graph comprises a path that starts from a node and ends at the same node.

detect cycle in graph

Detect cycle in directed graph in Java, JavaScript, Python

Example 2: Generate valid parentheses – generate all possible expressions that containing n pairs of valid parentheses.

generate valid parentheses

Generate valid parentheses


8. Dynamic programming


dynamic programming

Dynamic Programming is a method for solving a complex problem by breaking it down into a collection of simpler sub-problems, solving each of those sub-problems just once, and storing their solutions using data structure, such as arrays, matrices or maps. So the next time the same sub-problem occurs, one simply looks up the previously computed solution, thereby saving computation time. The intuition behind dynamic programming is that we trade space for time.

Example 1: Edit distance – the number of actions (insert, delete and update) to convert one word to another word.

edit distance dynamic programming

Edit distance and autocorrect in Java

Example 2: Fabonacci numbers –  a sequence of numbers, in which each number is the sum of the two preceding ones. 

fabonacci dynamic programming

Fibonacci sequence 4 solutions and their complexity

What are some examples of algorithm Greedy?

Huffman coding
Dijkstra’s algorithm
Greedy algorithm

What are some examples of Backtracking?

Generate valid parentheses
Detect cycle in directed graph
backtracking

What are some examples of Dynamic programming?

Edit distance
Fibonacci number
dynamic programming


Big O notation cheat sheets compilation
Data structures and Algorithms (YouTube)

Comments are closed