Competitive Python

In this post we will explore and implement an algorithm which helps us verify that if the brackets are balanced or validly used. This is a very important application of stacks as a lot of programming languages use brackets very extensively in their syntax and one of the job of a compiler is to check if the brackets are balanced or not. For simplicity's sake we will just use a list with the methods append() and pop(). This will help us emulate a stack without actually needing to implement it. If you want to, you can go and learn about stacks on this link . A set of brackets can be called balanced if all of the brackets in it are properly matched. Examples of balanced brackets : (([]{}{})) ({{}}[]) Examples of unbalanced brackets : (([)]) {{}]}]]) So now getting to the algorithm, what we simply do is that we go through a string of brackets and check that for every closing bracket there is a properly nested opening bracket. This is how we do it - Convert the input string into a...

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 ...

A prime number is a number that is only divisible by 1 and the number itself. There are multiple ways we could test if a number is prime or not but today we will talk about two ways- Naive method sqrt(n) prime testing (the efficient method) The Naive method One method would be to check all possibilities from 2 to n - 1, n being the number we are testing. This would mean that if a number is prime we will have to search through all the numbers from 2 to n - 1. But if a number is not a prime then we will not have to search through all the possibilities, we will just return false if a number is completely divisible by another number that means it doesn't leave any remainder. def isPrime(n): for i in range(2,n): if n%i==0: return False return True The worst case for this method would be O(N). Sqrt(n) method Okay, so the logic behind this method is that every composite number has at least one factor that lies between 0 and the square root of n. ...

Binary Search Okay, so how do you think we can search for a paticular element in an array? One obvious way will be to loop through the array and return true at which the element is found and to return false if it doesn't exist in the array. But the problem with this algorithm known as linear search is that it can very quickly turn out to be very costly in terms of space and time as this algorithm takes O(n) or linear time. This turns out to be highly costly for a large number of elements in an array. #Linear Search --> def linear_search(array , n ): for i in array: if i == n : return True So, the solution to this is to use an algorithm called binary search . Binary search is an algorithm that works on the divide and conquer technique and is also extremely efficient.It works on O(logn). But the only catch to this algorithm is that the array it is being applied on needs to be sorted . #Binary Search --> def binary_search(array, n ): #Setting up search ...

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...