Competitive Programming is a sport. Take any sport, let’s consider cricket for that matter, you walk in to bat for the first time. Swing and a miss, do it couple of times and you’ll eventually hit one over the ropes. Now, consider a programming contest as a game of cricket, metaphorically. Compile a code and submit, you may get a WA (Wrong Answer). Make changes to code and eventually you will get your first AC (Accepted/Correct Answer). Let me give you a sneak peek, about 20% of questions in a programming contest are simple conversion of plain english to a code of your favourite programming language.
Here are the Top Algorithms and data structures you need to know:
- Sort algorithms
- Search algorithms
- Dynamic programming
- Exponentiation by squaring
- String matching and parsing
- Primality testing algorithm
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 upon requirement you may want to use any of these.
- Merge Sort
- Quick Sort
- Bucket Sort
- Heap Sort
- Counting Sort
- Bubble Sort
- Insertion Sort
- Selection Sort
- Radix Sort
- Shell Sort
- Binary Search (in linear data structures)
- Depth/Breadth First Search (in Graph data structures)
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 upon the scenario.
Dynamic Programming is just a fancy way to say ‘remembering stuff to save time later’. DP is a method for solving a complex problem by breaking it down into simpler sub problems. We solve the sub problems, remember their results and using them we make our way to solve the complex problem, quickly.
- N-Queens problem
- Longest Common Subsequence
- Longest path in a matrix
- Minimum difference of subet sum
5. Exponentiation by squaring
Say you want to calculate 2^32. 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 problem 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 a 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 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 range is a crucial factor, because we have to allocate certain amount of memory according to range.
- For any number n, incrementally testing upto sqrt(n) (deterministic)
In case you want to check for few numbers which are sparsely spread over a long range (say 1 to 10^12), Sieve won’t be able to allocate enough memory. You can check for each number n by traversing only upto sqrt(n) and perform a divisibility check on n.
- Fermat primality test and Miller–Rabin primality test (both are nondeterministic)
Both of these are compositeness tests. If a number is proved to be composite, then it sure isn’t a prime number. Miller-Rabin is a more sophisticated one than Fermat’s. Infact, Miller-Rabin also has a deterministic variant, but then its a game of trade between time complexity and accuracy of the algorithm.
Recommended Books for Algorithms learning:
- , by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
Also known as CLRS (taken from name initials), this book is often referred to as the “bible” for algorithms and data structures. It’s one of the most popular textbooks for university algorithm courses. This book covered various algorithms and data structures in great detail. The writing is more rigorous and can be difficult to some.
2., by Robert Sedgewick and Kevin Wayne
This book is neatly categorized, coupled with elaborate explanations and fantastic illustrations. It is used in some IOI training camps as a textbook.
3., by Jon Kleinberg and Éva Tardos
This book revolves around techniques for designing algorithms. It’s well-organized and written in a clear, understandable language. Each chapter is backed with practical examples and helpful exercises. The chapter on network flow is highly praised by lots. … The lecture slides that accompany the textbook are available on its.
Also you can take algorithms course on this site and you are guranteed to get a good grip on all these topics
and a specially curated course for Competitive Programming