Topics In Demand
Notification
New

No notification found.

7 Data Structures and Algorithms a Programmer Must Know
7 Data Structures and Algorithms a Programmer Must Know

December 9, 2022

195

0

In programmers' lives,  algorithms and data structures are the most crucial subjects if they want to go out into the programming industry and make some dollars. Today, We shall see what they do and where they are used using basic examples. 

  1. Sort Algorithms

The most extensively researched idea in computer science is sorting. The objective is to arrange the items in a list in a specific order. Though every primary programming language includes built-in sorting libraries, it comes in handy if you know how they function. You should use any of these, depending on the situation.

 

  • Merge Sort
  • Quick Sort
  • Bucket Sort
  • Heap Sort
  • Counting Sort

 

More significantly, one should know when and when to employ them. Examples of cases when sorting techniques are directly applied include:

 

  • Sorting by price, popularity etc., on e-commerce websites

 

  1. Search Algorithms

 

  • Binary Search (in linear data structures) (in linear data structures)

A binary search is used to execute a highly efficient investigation of the sorted dataset. The time complexity is O(log2N) (log2N). The idea is to repeatedly divide half the portion of the list that could include the item until we narrow it down to one possible thing. A few examples are:

When you search for a name of music in a sorted list of tracks, it performs binary search and string-matching to provide the results swiftly.

Used to debug in git with git bisect

 

First Search: Depth and Breadth (in Graph data structures)

DFS and BFS are examples of data structures for locating and navigating trees and graphs. We won't go into great detail about how DFS and BFS work, but the animation that follows will demonstrate how they are different.

  

Applications:

 

  • Used by search engines for web-crawling
  • used to make artificially intelligent bots, such as chess bot
  • Finding the shortest path between two cities on a map and many other related applications

 

  1. Hashing

Hash lookup is now the mechanism most frequently used to locate pertinent material by key or ID. We access data using its index. Previously we relied on Sorting+Binary Search to hunt for indexes, whereas now we employ hashing.

 

A "Hash-Map," "Hash-Table," or "Dictionary" is a data structure that effectively maps keys to values so that we can search for values using keys. A suitable hash function should be picked based on the circumstances. da

 

Applications:

 

  • To store IP addresses -> Path pairs for routing systems in routers.
  • To check if a value already exists in a list. A linear search would be expensive. We may also use a Set data structure for this operation.

 

  1. Dynamic Programming

Dynamic programming (DP) is a technique for decomposing a large problem into smaller, more manageable challenges. We resolve the smaller issues, keep track of the solutions, and use those to tackle the larger, more difficult issue quickly.

 

  • *writes down “1+1+1+1+1+1+1+1 =” on a sheet of paper* What’s that equal to?
  • Eight, I'm counting.
  • What about that? *adds another "1+" to the left*
  • Immediately, Nine!
  • How'd you know it was nine so fast?
  • You recently added another.
  • You knew there were 8, so you didn't have to recount! Remembering things so you can save time later is what dynamic programming is just a fancy way of saying.

 

Applications:

 

  • There are various DP algorithms and uses, but the Duckworth-Lewis method in cricket will really blow you away.

 

  1. Exponentiation by squaring

Say you wish to compute 232. Normally, it would take us 32 iterations to find the solution. What if I told you that five iterations would suffice?

Exponentiation by squaring, often known as binary exponentiation, is a common method for efficiently computing large positive integer powers of a number in O. (log2N).

 

Application:

  • In RSA encryption, calculations involving vast powers of a number are frequently necessary. RSA makes use of both binary exponentiation and modular arithmetic.

 

  1. String Matching and Parsing

One of the essential problems in computer science is pattern matching and searching. Despite thorough investigation on the topic, we'll list the top two needs for programmers.

  1. Primality Testing Algorithms

Both probabilistic and deterministic techniques can be used to determine whether a given number is prime. There will be examples of both deterministic and probabilistic (nondeterministic) techniques.

The Eratosthenes Sieve (deterministic)

If we have a specific limit on the range of numbers, say, determine all primes within the range of 100 to 1000, then Sieve is a way to go. Since we must allot a certain amount of memory based on the range, the range's length is a crucial factor. 

For any number n, incrementally testing upto sqrt(n) (deterministic) (deterministic)

If you wish to check for a few values sparsely dispersed over a broad range (say 1 to 1012), Sieve won't be able to allocate adequate RAM. By going up to sqrt(n), you can examine each n number.

 

The Miller-Rabin and Fermat primality tests (both are nondeterministic)

Both of these are compositeness tests. A number cannot be a prime number if shown as a composite. The Miller-Rabin model is more complicated than Fermat's model. In fact, Miller-Rabin also has a deterministic variation but then is a game of trade between time complexity and accuracy of the method.

 

Application:

 

  • The use of prime integers in cryptography is their most significant application. More precisely, they are utilized in encryption and decryption in the RSA algorithm, which was the very first implementation of Public Key Cryptosystems.
  • Hash functions used in Hash Tables are another application.

 

In this article you learnt the cutting-edge algorithms that any competitive programmer should be familiar with.

 


That the contents of third-party articles/blogs published here on the website, and the interpretation of all information in the article/blogs such as data, maps, numbers, opinions etc. displayed in the article/blogs and views or the opinions expressed within the content are solely of the author's; and do not reflect the opinions and beliefs of NASSCOM or its affiliates in any manner. NASSCOM does not take any liability w.r.t. content in any manner and will not be liable in any manner whatsoever for any kind of liability arising out of any act, error or omission. The contents of third-party article/blogs published, are provided solely as convenience; and the presence of these articles/blogs should not, under any circumstances, be considered as an endorsement of the contents by NASSCOM in any manner; and if you chose to access these articles/blogs , you do so at your own risk.


© Copyright nasscom. All Rights Reserved.