Graph Implementation

COMING SOON..👻

Read More

Graph Representation

Graph Declaration

First let us look at the components of graph data structure. To represent graphs, we need the number of vertices, the number of edges and also their interconnections.

Adjacency Matrix

The adjacency matrix of a graph is a square matrix of size N × N, where N is the number of Nodes of the graph. It is basically a Boolean matrix which is initialized with zero. Let’s Say our adjacency matrix as Adj[][]. So Adj[u][v] is set to 1 if there is an edge between node u and v, otherwise it is zero.

Now if the graph is undirected you can either set Adj[v][u] = 1, whenever you set Adj[u][v] = 1 or you can just leave Adj[v][u] = 0. In both the cases to save time we will just process Diagonally half of this Matrix.

Now if the graph is directed you have to consider Adj[v][u] whenever you set Adj[u][v] to 1, because Adj[v][u] ≠ Adj[u][v] for directed graph. But in that case also we will just process diagonal half of the matrix as in each step when Adj[u][v] comes we will also check Adj[v][u].

The Adjacency matrix representation is good if the graphs are dense. The matrix requires O(N²) bits of Storage and O(N²) time for Initialization. If the number of edges is proportional to N²,then there is no problem because N²steps are required to read the edges.

But the Downside is that it doesn’t matter the edges are minimum or maximum it will always take same amount of Space and Time. Which is why Nowadays we don’t use this kind of implementation. If N ≤ 10⁴, we can use It, but if N ˃ 10⁴ We can’t use this implementation in competitive coding platforms. It will give TLE error.

Adjacency List

Adjacency list is better implementation. The basic concept is that we create a list of node and each list node have only those nodes which are connected to the list node.

See below Images to get better idea.

One thing to be kept in mind is that the order of edges in input is important. This is because the order in which edges appear on the adjacency list affects the order in which they are processed by algorithms.

The adjacency List takes O(N+M) of space where N is number of node and M are number of edges. Which is far more less than Adjacency matrix. Also graph traversals are fast & easier in Adjacency List. 

Go to the Implementation Part to Know how They are Implemented.

More Topics will be Added Soon 💚

Read More

BASIC GRAPH THEORY

Introduction

 

In the real world many problems are represented in terms of objects and connections between them. For example, in Railway route map we might be interested in questions like: “What is the fastest way to go from Lucknow to Delhi?” To answer these questions, we use Graph Data structures.

A graph is simply a way of encoding pairwise relationships among a set of objects. It consists of a collection of V nodes and E edges. Edge simply connects two of the nodes but not necessarily. An edge can also go start and end on same node, these types of edges are called self-loops. We will discuss them on later posts.

Types of Edges

· Directed Edge

• Ordered Pair of Vertices (u, v).
• First Vertex is Origin
• Second Vertex is Destination
• Its like one-way road

· Undirected Edge

• Unordered pair of vertices (u, v).
• Its like two-way road.

Types of Graphs

• Directed Graph

 

• All edges are Directed
• It is like Route Network

• Undirected Graph

• All Edges are Undirected
• Its like Flight network

Important Points You Should Know

•      A degree of vertex is the number of edges incident on it.
•     Two edges are parallel if they connect the same pair of vertices.

•     A graph with no cycles is called a Tree. A Tree is an acyclic connected graph.

•     A self-loop is an edge that connects a vertex to itself.

•     Graphs with relatively few edges are called Sparse Graphs.
•     A graph is connected if there is a path from every vertex to every other vertex.
•     If graph is not connected, then is consists of a set of Connected Components.

•     Graphs with all edges present are called Complete graphs.
• Weighted graphs have weights assigned to each edge or node. 

NEW TOPICS ARE BEING ADDED 💚

Read More

Graphs & Algorithms

GRAPH

1)  Basic Graph Theory

i) Introduction

ii) Representation

2) Graph Implementation

i) Adjacency Matrix

ii) Adjacency List

3) Graph Algorithms

4) Graph Traversal

5) Famous Problems on Graph

 

More topics will be made available soon💚

 

Read More

WHAT IS COMPETITIVE PROGRAMMING ?

BEFORE YOU READ : In this article we will try to understand what is Competitive Programming.

 

WHAT WE ARE GOING TO DISCUSS

• What is Competitive programming
• How to practice Competitive Programming   

WHAT IS COMPETITIVE PROGRAMMING ?

Generally refered  as CP, Competitive programming means that you have a specific amount of time to generate or create a working code and not only this the code should be optimized and should be of standard given by the author. For example to understand this you can say that we have two people named A and B. Both are Programmers, But difference between them is that A creates a program which is fast and short, while B creates a program which is slow and lengthy. Programs of both A and B gives correct output,then whose program is better and why ?

Well, A's program is better than B's. That's because of the two most important factors which are Time and Memory{often called 'Space'}. In simple language A's program is short due to which it is processed faster than B's program. Also as A's program is short it requires less Space(Memory) than B's program.

Well, Everything comes with a price and in computer science Time and Memory are Inversely related. Either you can save Space(Memory) by increasing Execution Time of program or you can save Time by increasing Space(Memory) of Program. Then what we do in Competitive programming ?  In Competitive Programming we find the "Best possible program whose Execution time is minimum possible as well as Space". 

Lets understand it with a better example. Suppose A and B play tennis and they consecutively score.Hence you will be given a string with alternate A or B telling who scored on ith round. The player who scored more will win the game or if equal then its tie . How will you solve this problem ?

Example string : BABABABABABABAB

First method : Just create two variables and count all occurrences of 'A' and 'B' and then compare the values to find the winner or tie. 

Did you also thought this ? 

Second method : By observation and after some dry calculations we can easily find that if string starts with A and ends with A , A will Win, Similarly if string starts with B and ends with B, B will Win, otherwise there will be a tie always. Did you thought this solution?

Second Method is far better than first method in terms of Time of execution and Space of program. You will require at-least n (size of string) units of time to find answer by first method but you can do that in  at most 4 units of time by second method with a really less space. This is Competitive programming. You come up with a better solution possible for the given problem. 

If you thought the second method congrats and if not it's normal and happens with everyone at their early stages of Competitive programming.

I hope now you all have an idea of what is competitive programming. So, lets move forward to our next point.

How to Practice Competitive Programming ?

 Choose a Programming Language

Firstly, you need to select a programming language with which your are most comfortable and then learn its syntax and rules. It can be any language C, C++, C++14, Java, Python, Python 3, Ruby etc. C, C++ and Java are faster programming languages with C being the fastest among all other available languages moreover they are allowed in almost every competition or interviews. So it’s good if you choose one out of these three still there is no restriction if you are comfortable with any other language.

Understanding Time and Space Complexity

In most of the cases there is more than one solution that exists to a problem so you need to come up with the best solution as we seen earlier in the post. So it’s really important to learn about these two concepts to write an optimal solution for the problem.

Learning Data Structures and Algorithms

DSA is the heart of programming and you can not ignore it while solving coding problems in competitive programming. Array, Linked List, Stack, Queue, Tree, Trie, Graph, Sorting, Recursion, Dynamic Programming all these basic building blocks of DSA will help you to become a good programmer. The most important thing you need to know where , what and when to apply them. It means which data structure is suitable for what type of problem to get the optimal solution. Practicing questions based on DSA will you in that.

Solve Coding Problems

Now you have cleared the beginner round and now its time to practice. You need to take part in coding challenges on different coding platforms. Before participating in contest it would be great if you practice for some challenges on your own and then participate there.
Start from the basic level  and once you build the confidence, get out of your comfort zone and gradually try to solve the complex problems. Below are some points you need to keep in mind once you start solving problems.

• You need to understand the input, output and test cases on online coding platforms. Check the link Solving Problem on Codechef to get started on this platform.
• The online coding platforms run your code on a lot of inputs then take out the output and store it in one place. They also have the tester's code or author's code which is one of the correct code for the problem. They run the same set of input on correct code and create the outputs and after that, they match these two outputs. If these two outputs match then your solution is considered correct.
• You may freeze out in the beginning once you see the problems on these coding platforms and think that you are not made for it or your thinking ability is not much higher to solve these questions. The reason is as a beginner you just know the syntax of the language and some basic loops or function, so when you encounter these challenges you freeze out and start doubting on your capabilities which you should not do that. You need to understand that there is a process to learn competitive programming and you have to move gradually from level 0 to the top level 💪.

Practice and Do it Regularly

 Your patience, dedication, and consistency are very important to become a good competitive programmer. Keep practicing the coding questions every single day on the online coding platforms or you can also take the help of whiteboard to solve coding questions but the important thing is to do it regularly. Do not make a mistake to take a break from it once you have started. Stick on it, no matter how difficult the problem is or how much time you take to solve a single coding problem. Participate in different coding competitions and learn from other programmers. As a beginner try to practice 100 different problems rather than solving 1000 same problems, because in your early stages you need to expand your critical thinking and problem solving skill. Your daily practice makes you a perfect coder, good problem solver and you will be able to find a suitable data structure for a specific problem and that matters a lot in software development.

Never Give Up!

Do not lose hope in getting wrong answers because this is the moment where most of the people lose interest and even quit it. If you can't solve problem read it's solution to get an idea and then again solve it. Day by day you will improve. It's not about how many you got correct it's  about how much you tried. 

Never say Never because limits like fears are often an illusion - Micheal Jordan

Online Platforms to practice Competitive Programming

• Hacker-earth - Indian Platform
• Codechef - Indian Platform
• Codeforces - Russian Platform
• URI
• SPOJ
• Hacker-rank - Indian-American Platform
• Top-coder - American Platform
• At-coder - Japanese Platform
• Geeksforgeeks - Indian Platform

You can also share your views in comments. 💗

Read More