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. applications are powered by algorithms. Even it is also popular for coding interviews to get a high-paying job in the software industry. So 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 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
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 coding 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.
- Clearly specified input: We need to know all relevant details like input data type, input size, data structure, input distribution, etc. Input can be a value or some set of values.
- Clearly specified output: We need to know all relevant details related to the output. Output can be a value or some set of values.
- Correctness: For every set of inputs, our algorithm must halt with the correct output. In other words, our algorithm must be correct. The incorrect algorithm might halt with incorrect answers or not halt at the correct output for some input values.
- 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!
- Finiteness: Good algorithm must terminate after a finite set of steps. We should avoid infinite recursion or infinite loop condition.
- Simple and Elegant: 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 the computer program. Think!
In computer science, these things are as crucial as an algorithm’s performance: Code correctness, Functionality, User Friendliness, Modularity, Scalability, Security, Maintainability, Programmers time, etc. The critical question is : Why do we analyze the performance of an algorithm? Here are a few important reasons:
- The performance draws a line between feasible and infeasible.
- It provides a clean standard to think about the program or system behavior.
- Performance is just like money where we use it to pay for more functionality or user-friendliness. For example, we code in Java or C++ for the OOPS features, even though Java is approx. 3 times slower than C. In other words, we are willing to pay the performance by a factor of 3 to get 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. For comparing performances, we are running the slower sorting algorithm Insertion sort on faster computer A and running the faster sorting algorithm Merge sort on slower computer B.
What difference do we observe? Still, computer B is taking much less time than computer A, if 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!
There can be different solutions or algorithms for the same coding problem and these solutions may differ in terms of efficiency. These differences can be much more significant than differences due to hardware and software. So the system performance depends on choosing efficient algorithms as much as on choosing fast hardware. Even applications that do not require algorithm directly at the application level, relies heavily upon algorithms. For examples:
- Does the application require fast hardware? The hardware design uses algorithms.
- Does the application depend upon 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!
Real-life applications of algorithms and data structures
- 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
- 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
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
You can find these problems on the Internet.
Content references
- Algorithms by CLRS
- The Algorithm Design Manual by Steven Skiena
Enjoy learning! Enjoy coding! Enjoy algorithms!