In our last blog, we covered the various ins and outs of competitive programming and proved it to be essential for all engineers. Now that you know why competitive programming is important, let's see the topics you need to prepare to win that competition! Let's divide them into 2 parts - Basic topics and Advanced Topics.

The Basic Topics-

The basic Topics consist of the ability to understand anyone's programming language properly. This process gradually sinks in over time with regular practice and by solving problems. In addition, there are a few basic concepts that are required to be kept in mind before moving forward-

• Basics of Input/Output - The very first step of getting started with the online judge is to understand how to read input data and how to output the answer. There exists standardized single-line command syntax for both input and output in different coding languages.

• Time and Space Complexity - Often we need to compare the performance of different algorithms and choose the best one to solve a particular problem. This is where space and time complexity comes into the picture. Only the execution time of an algorithm is considered. The time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the input. The space complexity of an algorithm quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input.

• Basic Implementation - Questions that are based on brute-force solutions are classified under the implementation category. The objective of such questions is to help coders improve their ability to convert English statements into code implementation.

• Operators - These are symbols that tell the compiler to perform specific mathematical or logical manipulations. The most commonly used operators in programming are – Arithmetic, Relational, Bitwise, Logical, Assignment, Increment, and Miscellaneous.

• Recursion - Recursion is useful in solving problems that can be broken down into smaller problems of the same kind. When a function calls itself, it’s called Recursion. For example in the movie Inception, the main protagonist Leonardo had a dream, in that dream, he had another dream, and in that dream, he had yet another dream, and that went on.

Mathematical Induction becomes the underlying principle for many of these concepts. These basic modalities are mostly covered in the introductory year of engineering where the freshman are exposed to the sophisticated subject of computer science. Being self-explanatory and understandable, they could be easily accessible on online CP learning platforms.

The Advanced Topics-

The advanced modalities require an intensive commitment regularly and cognitive thinking ability to grasp the fundamentals, right from the word go. Finally, we arrive at an impasse and knock at the uncanny door of Data Structures and Algorithms. DSA indeed is the most defining factor for programming. It is like the bible for computer science and its applications.

Data Structures-

• Arrays - An array is a sequential collection of elements of the same data type and stores data elements in a contiguous memory location. The elements of an array are accessed by using an index. The index of an array of size N can range from 0 to N−1.

• Stacks - Stacks are dynamic data structures that follow the Last In First Out (LIFO) principle. The last item to be inserted into a stack is the first one to be deleted from it. For example, in a stack of trays on a table, the tray at the top of the stack is the first item to be moved if required.

• Queues - Queues are data structures that follow the First In First Out (FIFO) i.e. the first element that is added to the queue is the first one to be removed. Elements are always added to the back and removed from the front.

• Hash Tables - Hashing is a technique that is used to uniquely identify a specific object from a group of similar objects. A key is assigned to an object to enhance searching. When the keys are large and cannot be used directly as an index, hashing is used. The values of these keys are stored in a data structure called a hash table.

• Linked List - A linked list is a way to store a collection of elements. Each element in a linked list is stored in the form of a node. A node is a collection of two sub-elements or parts. The data part stores the element and the next part that stores the link to the next node.

• Trees - A tree is a data structure that represents hierarchical data. It is a structure made out of nodes, where each node comprises 3 components including a data element, a left pointer, and a right pointer. If the tree is empty, then it’s represented by a null pointer.

Undoubtedly, the more intriguing sounds the name of the data structure, the more complex and tougher it becomes to comprehend. In an algorithm design, there is no one 'silver bullet' to tackle all computation problems. Different problems require the usage of different kinds of techniques and algorithms-

• Searching – Searching Algorithms are designed to check for an element or retrieve an element from any data structure where it is stored. Based on the type of search operation, these algorithms are generally classified into two categories – sequential and interval search.

• Sorting - A Sorting Algorithm is used to rearrange a given array or list of elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of elements in the respective data structure.

• Greedy Algorithm - A greedy algorithm always makes the best choice that seems to be plausible at that moment (carpe diem). In nutshell, it makes a locally optimal choice in the hope of leading it to a globally-optimal choice.

• Graphs - A Graph is a non-linear data structure consisting of nodes and edges. The nodes are also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph. Graphs are used to solve many real-life problems and represent complex networks.

• String Algorithms - Declaring a string is as simple as declaring a one-dimensional array. Strings are defined as an array of characters. The difference between a character array and a string is the string is terminated with a special character ‘\0’.

• Dynamic Programming - The core idea of Dynamic Programming is to avoid repeated work by remembering partial results. In programming, Dynamic Programming is a powerful technique that allows one to solve different types of real-life problems in a shorter time.

The Final Test Case- At the end of the day, it is always the application that truly matters rather than the basic raw knowledge. After acquiring enough fundamentals based on data structures and algorithms, the crux is to able to articulate these components according to the demand and need of the problem because of the following-

• Data storage – Certain data structures are well suited or best designated for some kind of the datatype.

• Memory Usage – Excessive storage is expensive and slows down the execution. A data structure with low memory utilization is the idlest.

• Basic Operations – Resources should be quantified and the problem should be analyzed to determine the basic operations that must be supported.

Signing Off-

You can learn DSA from online resources but to excel you need to practice. There are never-ending practice problems on each topic with interesting and diversified applications. Each data structure has associated costs and benefits. In practice, it is hardly ever true that one data structure is better than another for use in all situations.

All the best with your preparation! Tell us all about your next competition on Twitter :)