Competitive Python

Tuple is a linear data structure which more or less behaves like a python list but with a really important difference, that a tuple is immutable . Immutable means that this structure can't be changed after it has been created, it can't be mutated if I may. Tuples being immutable are more memory efficient than list as they don't over allocate memory . Okay, so what this means is, when a list is created it takes up and reserves extra spaces of memory than needed for the original elements as new elements might be added to the list later and allocating memory on every addition would be quite inneficient but tuples, once created surelly won't change the numbers of elements in it later on, so it allocates exactly how much memory is needed. Almost all the list operations work for tuples except the ones which mutate it, for example, insert, append, remove etc. Declaring a tuple : Tuples can be initialise in a manner similar to list, But there's an important c...

We are going to look at Dijkstra's two-stack algorithm and see how it's implemented. This algorithm is used to evaluate infix expressions. It uses stacks at its core, so if you don't know about stacks or if you'd want to learn more about them, click this link There are three types of expressions, Infix : Infix expressions are the ones where the operators are used between values, like a + b - c . Postfix : These are the expressions where operators are written after the values, like a b c +- , this translates to a + b - c in infix. Prefix : In these expressions, the operators are written before the values, for example + - a b c . This expression will also be equal to a + b - c in infix. Okay, so what this algorithm does is evaluate expressions like ( ( 3 + 4 ) * 83 ) . It starts by breaking down this expression into a list of stings and create two empty stack, one for housing the values and other for the operators. Then we go through the list one by one. Whenev...

Greedy Algorithms is an algorithmic paradigm just like divide and conquer is. It is a design technique that depends on locally optimal choices to produce an overall optimal solution. It makes a greedy choice at every step based on a condition and hopes that the choice it made will produce the most optimum solution. A lot of times this technique fails to generate algorithms that are optimal but it does make a lot of problems very very easy. Its used in several different algorithms, most famous of them being: Huffman Coding Dijstrika's Shortest path Kruskal’s Minimum Spanning Tree Greedy algorithms basically make up a solution step by step fashion choosing the next piece which offers the most immediate benefit. Some problems based on Greedy Algorithms are - Grocery Bagger School Assembly Boxing Chopsticks Receipt

Sieve of Eratosthenes is an algorithm that is used to generate all the primes up to a particular number . It is a very ancient algorithm but is very useful and also is a frequently seen in questions in competitive programming. This is a very elegant algorithm and is certainly better than trial division method . The idea behind this algorithm is to first select 2 and strike of all the multiples of because we know that they are composite. Then look for the next number that is not stricken off, it will definitely be a prime and then strike off all the multiples of that number. This goes on until the square of the number we select is greater than the limit that we assigned to it. As you will notice there is no need to go further because all of their multiple will already be stricken off by one or the other prime before it. To formalise the algorithm, it can be described as follows : Select the smallest prime from the list of all numbers upto n. Strike off all the multiples of the ...

Recursion What is recursion Three rules of recursion Examples Fibonacci Factorial Additional Resources What is recursion? Recursion is a method of solving problems based on divide and conquer.It is a very elegant way to write solutions to problems that would be pretty inefficient in an iterative solution ( using loops ). A recursive function is basically a function that calls itself on a problem that is somehow smaller or more simplified than the original problem . For example see the function sum of list #Iterative Solution---> 1)def listSum( list ) : 2) sum = 0 3) for i in list : 4) sum += i 5) return sum 1)def listSum( list ) : 2) if len( list ) == 1 : 3) return list[0] 4) else : 5) return list[0] + listSum(list[1:]) In the iterative solution we go through each item in the list and keep adding it to the sum variable . But the same can be solved using a recursive solution . First, in line 2 we check for the base case,that is if the list is...