What is Algorithm? Properties and Real-life Applications

Introduction

Before the invention of computers, there were algorithms. Now computers are everywhere, so algorithms are everywhere! Algorithms lie at the heart of computing.

If we observe our surroundings, we can find several algorithms working to solve our daily life problems: Social media networks, GPS applications, Google search, e-commerce platforms, Netflix recommendation systems, etc. All of these applications are powered by high performance algorithms.

On other side, algorithmic problem solving techniques are also popular for coding interviews to get a high-paying job in the software industry. In simple words: learning algorithms is one of the critical career skills for programmers!

Critical ideas to think about!

• Why did we use algorithms before the invention of computers?
• Why some of the ancient algorithms are still relevant?
• Algorithms are about computers or much more than that?

Definition of an Algorithm

An algorithm is a well-defined step-by-step procedure to transform a given input into the desired output to solve a computational problem. In other words, an algorithm is a tool for solving a well-specified computational problem. Note: Computational problem is a collection of questions that computers might be able to solve. For example, the problem of sorting  is a computational problem.

Example: Linear search

Given an array A[] of n elements, write an algorithm to search for a given element k in A[]. If k is present, return the index where it is present; otherwise, return -1.

Extracting all relevant details from the problem:

• Input size or total elements in the input = n.
• Input data structure: Array.
• Input data type: Integer, which can be both positive or negative.
• Input distribution or constraint: There are no constraints given in the input. All integers are stored in random order.
• Input: Array of integers and a value k.
• Output: If the value k is present, return the index; otherwise, return -1.

Input: X[] = [ 5, 8, - 3, - 4, 13, 9, - 17, 7, 12], k = 13
Output: 4
Explanation: Element 13 is present at index 4.

Input: X[] = [ 5, 8, - 3, - 4, 13, 9, - 17, 7, 12], k = 11
Output: -1
Explanation: Element 11 is not present in X[].

Linear search idea 

The value k can be present at any index in the array because we don’t know the input distribution. So a simple strategy would be:

• We run a loop to compare k with each element of X[].
• If k matches with an element X[i], we return the index i.
• If k doesn’t match with any of the elements, we return -1.

Linear search pseudocode

int linearSearch(int X[], int n, int k)
{
    for(int i = 0; i < n; i = i + 1)
    {
        if(X[i] == k)
            return i
    }
    return -1
}

Critical ideas to remember!

Always ask the following questions related to input for every algorithmic problem:

• What is the size of input? like 10 or 1000 or 10 billion!
• What is the data type of input? It can be an integer, floating-point number, character, string, or boolean!
• How input values are stored? It can be stored in a data structure like an array, linked list, tree, graph, etc.
• Is there some information available for the distribution of input? Like values can be stored in sorted order, input is allowed in a certain range, some permutation of the input is allowed only, etc.

Properties of a good algorithm

A good algorithm must be correct, efficient, finite, and easy to implement.

1. Clearly specified input: We need to know all relevant details, such as input data type, input size, data structure, input distribution, etc. Input can be a single value or a set of values.
2. Clearly specified output: We need to know all relevant details related to the output. Output can be a single value or a set of values.
3. Correctness: For every set of inputs, our algorithm must halt with the correct output. In other words, our algorithm must be correct. An incorrect algorithm might halt with incorrect answers or not halt at the correct output for some input values.
4. Efficiency: Running time and memory are bounded resources, and our algorithms must use them wisely. In simple words, our algorithm should be efficient in terms of time and memory!
5. Finiteness: A good algorithm must terminate after a finite set of steps. We should avoid infinite recursion or infinite loop conditions.
6. Simplicity and elegance: An algorithm should be easy to understand and implement.

Why analysing efficiency is important?

Suppose computers were infinitely fast and computer memory was free. Would you have any reason to study algorithms? But the reality is that computers may be fast but not infinitely fast, and memory may be inexpensive but not free. So, running time and space are essential resources for defining the performance of a computer program. Think!

In computer science, several factors are crucial for an algorithm's performance, including code correctness, functionality, user-friendliness, modularity, scalability, security, and maintainability, as well as the programmer's time. The critical question is: why do we analyze the performance of an algorithm? Here are a few important reasons:

• The performance determines what is feasible and what is infeasible.
• It provides a clear standard for understanding program or system behaviour.
• Performance is like money - we use it to pay for more functionality or user-friendliness. For example, we may choose to code in Java for the OOPS features, even though Java is approximately 3 times slower than C. In other words, we are willing to sacrifice performance by a factor of 3 to gain more functionalities.
• Speed is always fun, and we love it!

Suppose we would like to run two different sorting algorithms on two different computers A and B, where computer B is 1000 times slower than computer A. To compare their performances, we run the slower sorting algorithm Insertion sort on faster computer A and run the faster sorting algorithm Merge sort on slower computer B.

What differences do we observe? Still, computer B is taking much less time than computer A, if the input size is large. This gap will increase further if we increase the input size. This would be one of the reasons for learning algorithms and their efficiency. Think!

An algorithm is a technology!

The performance of a system depends on choosing efficient algorithms as much as on choosing fast hardware. Even applications that do not require algorithms directly at the application level rely heavily on algorithms. For example:

• Does the application require fast hardware? The hardware design uses algorithms.
• Does the application depend on the user interface? The design of the user interface relies on algorithms.
• Does the application rely on fast networking? Networking relies heavily on routing algorithms.

Overall, algorithms are at the core of almost all computer applications. Just as rapid innovations are being made in other computer technologies, they are also being made in algorithms!

Critical ideas to think!

• The heart of any algorithm is an idea that should be clearly and simply expressed.
• Reasonable-looking algorithms can easily be incorrect or partially correct. 
• Algorithm correctness is a property that must be carefully verified.
• Performance is just like money. We use performance to pay for more functionality or features or user-friendliness.

Real-life applications of algorithms and data structures

Application of array data structure

• Arranging a particular type of data in a sequential arrangement: Storing contacts on our phone, Storing speech signals in speech processing, etc.
• Implementing stack and queue
• Adjacency matrix representation of graphs
• Implementing hash tables, heaps, segment trees, etc.

Application of linked list data structure

• Singly-linked list: Maintaining a directory of names, Performing arithmetic operations on long integers, Manipulation of polynomials, Implementing stack and queue, Adjacency list representation of Graphs, Hashing by chaining method, Dynamic memory allocation, etc.
• Doubly-linked list: Implementing LRU Cache, Implementing LFU Cache, Implementing Fibonacci heap, Thread scheduler in operating systems, Representing deck of cards game, Implement undo and redo functionality, Previous and next page in a web browser.
• Circular linked list: Process scheduling in operating system, Keep track of the turn in a multi-player game

Application of stack data structure

• Storing browser history, UNDO/REDO options in a text editor
• Process scheduling, Static memory allocation
• Storing function calls in recursion
• In IDE or a compiler to know missing braces
• Expression evaluation, Syntax parsing

Application of queue data structure

• Process scheduling in operating systems (CPU and IO scheduling)
• Interprocess communications
• Breadth first traversal of tree and graph
• Waiting list in applications
• Customer care calls management

Application of hashing in data structure

• Accessing website using keywords in search engines
• Searching phone numbers on mobile devices, Employees information system
• Spelling checkers in word processing software, Symbol table in a compiler
• Encrypting critical data(Cryptography)

Application of tree data structure

• Binary tree: Store hierarchical data like folder structure, organization structure, File systems, Document Object Model to represent documents with a logical tree.
• Binary search tree: Used in applications where continuous insertion and deletion of data is happening, To implement ordered map and set objects in languages' libraries.
• Trie data structure: Autocompletion in google search, Spell-checking in word processors, Contact search on a phone book, Swipe features in your mobile keypad, Network browser history of the URL's, Longest prefix matching used by routers in internet protocols, Predictive text technology (T9 dictionary in mobile phones)
• Heap data structure: Used in implementing efficient priority queues, scheduling processes in operating systems, Dynamic memory allocation, Order statistics problem like finding kth largest or kth smallest in an array.
• Advanced data structures: Compiler design for parsing of the syntax (Syntax Tree), Wireless networking and a memory allocation (Treap), Range query processing on a data set (Segment Tree and Binary Index Tree), finding the nearest neighbour to a particular point (K Dimensional Tree), To store data on the drive (B-tree), 3D computer graphics (BSP tree), Fast full-text search in word processors (Suffix tree), etc.

Application of graph data structure

• Shortest path algorithm: Network routing protocols, Google maps, Shipment routing in e-commerce, Robot path planning, etc.
• Breadth-first search (BFS): Social network websites to find people with a given distance k from a person, Web crawling in a google search, Finding all neighbour nodes in the peer to peer network like BitTorrent (BFS), Network broadcasting, Finding neighbouring places via GPS navigation, etc.
• Depth-first search (DFS): Detecting cycle in a graph, Bipartiteness test in a graph, Finding strongly connected components, Solving maze puzzles, Topological sorting, Path-finding, etc.
• Topological sorting: Used in many different scenarios that involve scheduling several tasks with inter-dependencies: 1) Generating dependency graph of dependent modules in IDE build-systems 2) Determining order to create complex database tables with interdependencies 3) Determining order to take courses and their pre-requisites to complete a degree, etc.
• Other important applications: Assigning fastest pick-ups to Uber drivers (Hungarian algorithm), Facebook’s friend suggestion algorithm, Google page ranking algorithm where web pages are considered to be the vertices, Resource allocation graph in operating systems, Transaction graphs in cryptocurrency (Blockchain, which is a large graph), Artificial neural networks, Facebook graph search, Google knowledge graph, Product recommendation graphs (Recommendation system)

Application of dynamic programming

• Sequence alignment, Document diffing algorithms, Document distance algorithm (Edit distance), Plagiarism detection, Typesetting system
• Duckworth Lewis Method in cricket, Flight control
• Speech recognition, Image processing, Machine learning algorithms
• Economics, Financial Trading, Bioinformatics, Operations research

Application of greedy algorithms 

• Loss-less data compression of .png and .mp3 file-formats (Huffman coding)
• Shortest path algorithms (Dijkstra algorithms), Minimum spanning tree (Kruskal and prim's algorithms), Approximation algorithms for NP-hard problems
• Solving activity selection and other optimization problems

Application of backtracking 

• Solving famous puzzles like N-queens, crosswords, verbal arithmetic, Sudoku
• Solving various optimization and constraint satisfaction problem

Application of number theory

• Cryptography and computer graphics
• Designing hash functions and Random number generators
• Fast arithmetic operations

Other applications of algorithms and data structures

• Load balancing algorithms
• String matching (KMP algorithm)
• Image editing software like photoshop (Convex-hull algorithm)
• Filter out stories that people have seen before (Quora uses a bloom filter for this)
• Breaking down signals into frequencies (Fast Fourier Transform)
• Block-sorting compression (Suffix array)

Coding problems to warm-up in algorithms

• Reverse an array, Find the transpose of a matrix
• Bubble sort, Selection sort, Insertion sort
• Convert Roman to Integer
• Find the GCD of two numbers
• Given a number n, check if it is prime or not
• Check if a given string is a palindrome
• Print a given matrix in spiral form
• Find the largest element in an array

Content references

• Algorithms by CLRS
• The Algorithm Design Manual by Steven Skiena

If you have any queries/doubts/feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy system design, Enjoy algorithms!