Question

What are some important algorithms to know for computer science?

Answer 1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

I am listing top 7

Here are the Top 7 algorithms and data structures to know:

• Sort algorithms
• Search algorithms
• Hashing
• Dynamic programming
• Exponentiation by squaring
• String matching and parsing
• Primality testing algorithm

1. Sort Algorithms

Sorting is the most heavily studied concept in Computer Science. Idea is to arrange the items of a list in a specific order. Though every major programming language has built-in sorting libraries, it comes in handy if you know how they work. Depending on the requirement, you may want to use any of these.

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

2. Search Algorithms

Binary Search (in linear data structures) – Binary search is used to perform a very efficient search on sorted dataset. The time complexity is O(log₂N). The idea is to repeatedly divide in half the portion of the list that could contain the item until we narrow it down to one possible item.

3. Hashing

Hash lookup is currently the most widely used technique to find appropriate data by key or ID. We access data by its index. Previously we relied on Sorting+Binary Search to look for index whereas now we use hashing.

The data structure is referred as Hash-Map or Hash-Table or Dictionary that maps keys to values, efficiently. We can perform value lookups using keys. Idea is to use an appropriate hash function which does the key -> value mapping. Choosing a good hash function depends on the scenario.

4. Dynamic Programming

Dynamic programming (DP) is a method for solving a complex problem by breaking it down into simpler subproblems. We solve the subproblems, remember their results and using them we make our way to solving the complex problem, quickly.

5. Exponentiation by squaring

Say you want to calculate 2³². Normally we’d iterate 32 times and find the result. What if I told you it can be done in 5 iterations?

Exponentiation by squaring or Binary exponentiation is a general method for fast computation of large positive integer powers of a number in O(log₂N). Not only this, the method is also used for computation of powers of polynomials and square matrices.

6. String Matching and Parsing

Pattern matching/searching is one of the most important problems in Computer Science. There have been a lot of research on the topic but we’ll enlist only two basic necessities for any programmer.

• KMP Algorithm (String Matching)

Knuth-Morris-Pratt algorithm is used in cases where we have to match a short pattern in a long string. For instance, when we Ctrl+F a keyword in a document, we perform pattern matching in the whole document.

• Regular Expression (String Parsing)

Many times we have to validate a string by parsing over a predefined restriction. It is heavily used in web development for URL parsing and matching.

7. Primality Testing Algorithms

There are deterministic and probabilistic ways of determining whether a given number is prime or not. We’ll see both deterministic and probabilistic (nondeterministic) ways.

• Sieve of Eratosthenes (deterministic)

If we have a certain limit on the range of numbers, say determine all primes within range 100 to 1000 then Sieve is a way to go. The length of the range is a crucial factor because we have to allocate a certain amount of memory according to the range.

For any number n, incrementally testing up to sqrt(n) (deterministic)

In case you want to check for few numbers which are sparsely spread over a long range (say 1 to 10¹²), Sieve won’t be able to allocate enough memory. You can check for each number n by traversing only up to sqrt(n) and perform a divisibility check on n.

Kindly revert for any queries

Thanks.