Must read research papers on Algorithms

OpenGenus Tech Review Team -

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

Reading Research papers is a good habit but it is often, difficult to find ourt papers that should be read. Following are the must read research papers on Algorithms:

Note that the above list has been prepared by OpenGenus and is very accuracy. We will now go through each in detail:

QuickSort

Basic details on the paper:

Quick Sort is a fundamental algorithm in Computer Science as it took the sorting algorithm to be optimally solved that is in O(N * logN) time on average. It brings in some of the most fundamental ideas such as:

  • pivot finding
  • divide and conquer

This has been a major step and variants of this algorithms is still the most preferred choice for all programmers and is natively supported in languages like Java.

Ordered Hash Table

Basic details on the paper:

  • Author: O. Amble and D. E. Knuth
  • Date published: 1973
  • Journal/ Conference: The Computer Journal
  • Read this paper here: by Oxford Academia
  • Read about Hash Tables

Hash table is a fundamental progress as it shows how a simple data structure like array can be used to improve common operations like searching to constant time. Today, hash map has a central place in algorithms but a lot of ideas goes into it for efficiency like:

  • collision avoidance
  • hash generation

This is a must read for anyone interested in Computer Science and specially, Algorithms and Data Structures.

Gaussian elimination is not optimal (Strassen’s Matrix Multiplication algorithm)

Basic details on the paper:

This is considered one of the best papers of all time just becuase at a time, when the society strongly believe Matrix Multiplication cannot be improved beyond O(N^3), Strassen come up with his revolutionary paper where he solved the problem in O(N^log7) = O(N^2.8).

Though the improvement was not significant, it broke a major barrier in Algorithms and open a whole new area of optimizations. This lead to several optimizations over his initial version which are widely used today.

Estimating the Efficiency of Backtrack Programs

Basic details on the paper:

Backtracking algorithm proved to be a natural technique but it is often, difficult to understand if it is optimal or estimate its efficiency. This paper illustrates a few techniques which can be used to predict the efficiency of a backtracking algorithm in general case.

This is a must read so it brings in some of the best ideas used to understand if a solution is actually efficient.

On the Shortest Spanning subtree of a graph and the traveling salesman problem

Basic details on the paper:

This paper brings in the famous algorithm for finding Minimum Spanning tree that is Kruskal Minimum Spanning Tree Algorithm. It is a simple algorithm but was a major step in Algorithms as it showed that greedy algorithms are actually efficient even for real world problems.

This paper is a must read as it opens the World of greedy algorithms.

A Note on Two Problems in Connexion with Graphs

Basic details on the paper:

  • Author: E. W. Dijkstra
  • Date published: 1959
  • Journal/ Conference: Numerische Mathematik l, 269 - 27
  • Read this paper here: on TUM (PDF)
  • Read about Dijkstra's algorithm

This paper introduces Dijkstra's shortest path algorithm which is used to find the shortest path between two nodes in a graph optimally. This establishes the domain of graph algorithms by solving a difficult problem.

A Trivial Algorithm Whose Analysis Isn't

Basic details on the paper:

  • Author: Arne T. Jonassen and Donald E. Knuth
  • Date published: June 1978
  • Journal/ Conference: Journal of Computer and System Sciences
  • Read this paper here: Science Direct

This paper is a must read as this shows that algorithms can look simple while understanding and implementing it but when it comes to analysis of its performance, things can be difficult.

This puts light into the field of Algorithms as a truely technical field.

Polynomial Root finding algorithms and Branched Covers

Basic details on the paper:

  • Author: Myong Hi Kim and Scott Sutherland
  • Date published: July 12, 1991
  • Journal/ Conference:
  • Read this paper here: ArXiv (PDF)

Finding roots of algorithms may seem to be a mathematical problem but it has since been captured by the domain of Algorithms. This paper shows how a mathematical problem relies on algorithms which can enable a simple program to solve mathematical problems which can seem to be difficult for humans.

This paper illustrates the relation between Mathematics and Algorithms clearly and is a must read.

Stable husbands

Basic details on the paper:

  • Author: Donald E. Knuth, Rajeev Motwani, and Boris Pittel
  • Date published: 1990
  • Journal/ Conference: SODA '90 Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms
  • Read this paper here: on ArXiv (PDF)

This is a must read as this paper presents a hypothetical problem and proposes an algorithm to solve it. Later on, this algorithm was used to match students to Universities in USA in the early 2000s.

This is a perfect example of how an algorithm can be used to solve a real life problem even though it was not the first problem to begin with.

Analysis of a simple factorization algorithm

Basic details on the paper:

  • Author: Donald E. Knuth and Luis Trabb Pardo
  • Date published: December 1976
  • Journal/ Conference: Theoretical Computer Science
  • Read this paper here: Science Direct
  • Read about Prime Factorization

Having a mathematical background is crucial and this paper provides the background and insights needed in one of the most used Mathematical domains in Algorithms that is Prime factorization.

Fast pattern matching in strings

  • Author: Donald Knuth, James Morris and Vaughan Pratt
  • Date published: 2nd June 1977
  • Journal/ Conference: SIAM Journal on Computing
  • Read this paper here: Semantic Scholar
  • Read about KMP algorithm

This is a must read as it demonstrates how operations on Strings can be optimized and opened up a whole new domain of string algorithms. This was a major step in algorithms and is used widely even today.

With these paper, you will have a fundamental understanding of Algorithms and related domains and you can easily step into becoming a master in this field. Enjoy.

Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.