Is The Graph Connected or Not? (Implementation of BFS)

Today we are going to solve a very important problem of graph theory. It is to determine whether a given graph is connected or not. We use a very popular and important algorithm to solve this challenge called BFS(Breadth First Search) 

Problem Statement:

Given a graph with V nodes and E edges, we must find out whether it is connected or not.
From wikipedia: "A graph is connected when there is a path between every pair of vertices. In a connected graph, there are no unreachable vertices. A graph that is not connected is disconnected. A graph G is said to be disconnected if there exist two nodes in G such that no path in G has those nodes as endpoints."

Link To a Broader Description of Graph Connectivity

If you feel more comfortable learning the concept from a video, you can watch this youtube video:

BFS:

In order to solve this problem, we use BFS (Breadth First Search) algorithm. BFS is one of the most important and basic algorithms in graph theory.

Wikipedia link for BFS 

You can also watch this youtube video to understand the graph path finding algorithm more clearly.

Link to Youtube video 

I will take help of  the Java code for BFS provided in geeksforgeeks.com. You can see the code in their website in this link.

I hope you clearly understand graph connectivity and BFS algorithm now. If you do, we can proceed to the solution building section.

Solution Approach:

If the graph is connected, BFS will traverse the whole graph i.e. all the nodes in a graph will be visited. But what if we encounter a disconnected graph. Suppose we have a graph of 5 vertices numbered 1,2,3,4,5. We suppose 1,2 and 3 are connected (component no. 1) and 4 and 5 are connected (component no. 2). The 2 components are disconnected. In this case, if the BFS starts from 1/2/3 it'll only traverse component 1 and if   the BFS starts from 4/5 it'll only traverse component 2. 

So in the algorithm to determine connectivity, we traverse all the nodes in a loop and start BFS every time we find a non-visited node. This ensures we can reach all the components. Also starting BFS from every non-visited node in the loop means, we have encountered a new component. 

Complete Code Link 

In the code n is the number of vertices while m is the number of edges. The next m lines consists of u and v - the 2 vertices of edge (the edges are bidirectional here.). Vertices are number from 1 to n here.

Then we call the BFS function to determine the number of components / clusters. Here we have for loop from 1 to n referring to all the vertices. If we find a non-visited node , we have reached a new cluster and so we increment clusterNumber (number of components). This variable is returned to main and it's determined if it is equal to 1 or not. If it is 1, we have only one component meaning the graph is connected , otherwise, disconnected.

Java Game: Console Based Choice Game for Beginner

As a CSE, we had to do a homework of making a console based text game. So I made this game.

You need to learn Java if-else and loops to make this game. Here are some tutorials for that

If - else statement:

loop:

Game Description:

You are a person that has taken up an adventure beset with monsters. There are 4 types of monsters here: Skeleton, Zombie, Assassin and Warrior. At each turn you'll face a monster. When facing them , you can attack (you'll receive damage as retribution), you can run away from that monster or you can drink potion. If your health reaches below 1 (from 100) , the game is over. After defeating each monster, you may get a bonus health potion. Finally you have the choice to continue further into the adventure or leave (quit ) the game.

Project Link

Code Explanation:

Variables:

At first, we initialize the necessary variables, a string array (enemies) naming the enemies, enemyAttackDamage( the damage enemies causes the player), maxEnemyHealth( maximum health the enemy can have initially). For the player we have, health(initial health), attackDamage(the damage the player causes to the enemy), numHealthPotion (number of health potions to use), healthPotionAmount( how much a potion can recover the health) , healthPotionDropChance( used to determine the probability whether the player will get an extra potion after defeating an enemy. More on this later)

Main Loop:

1. We choose the enemy health randomly by using maxEnemyHealth

2. Similarly, we choose an enemy from the 'enemies' array randomly

Now the gaming loop begins and it'll continue until either the player or the enemy is defeated. After printing out the health status, the game offers 3 choices for the player to choose: 

1.Attack

2.Drink Potion

3.Run 

After taking the player's input from the console, if the player chooses option 1 we calculate damageDealt(the damage the player did to the enemy) by randomly picking a number by using attackDamage .Similarly, damageTaken is calculated from enemyAttackDamage. damageDealt is subtracted from enemyHealth and damageTaken is subtracted from health. 

Now if health is less than 1, the game is over and the gaming loop will break.

If option 2 is chosen, we check whether there is any potion left. If there is, we check whether the health is 100 in which case no potion is taken. Otherwise, healthPotionAmount is added to health while numHealthPotion is decremented. If there were no potion left, output the message to the console.

If we choose to run away(option 3), we just jump to the GAME label before the while(running) line to start with a new enemy through the 'continue GAME;' statement.

After Defeating an Enemy:

After the enemy health is less than 1, the gaming loop stops. Now the probability for getting a new potion is calculated. We choose a random number within 100 and if it is less than healthPotionDropChance , the player gets a new potion. if healthPotionDropChance's value is decreased , the probability for getting a new potion is also decreased.

The player is presented with 2 options, he/she can continue or quit. We take input from console and if the player decides to quit, we just break from the main loop.

Remarks:

This is a great practice to learn if-else and loops. :)

Beginners' Confusion: Why Should I Learn C++?

1. Games:
C++ overrides the complexities of 3D games, optimizes resource management and facilitates multiplayer with networking. The language is extremely fast, allows procedural programming for CPU intensive functions and provides greater control over hardware, because of which it has been widely used in the development of gaming engines. For instance, the science fiction game Doom 3 is cited as an example of a game that used C++ well and the Unreal Engine, a suite of game development tools, is written in C++.
2. Graphics User Interface (GUI) based applications:
Many highly used applications, such as Image Ready, Adobe Premier, Photoshop and Illustrator, are scripted in C++.
3. Web Browsers:
With the introduction of specialized languages such as PHP and Java, the adoption of C++ is limited for scripting of websites and web applications. However, where speed and reliability are required, C++ is still preferred. For instance, a part of Google’s back-end is coded in C++, and the rendering engine of a few open source projects, such as web browser Mozilla Firefox and email client Mozilla Thunderbird, is also scripted in this programming language.
4. Advance Computations and Graphics:
C++ provides the means for building applications requiring real-time physical simulations, high-performance image processing, and mobile sensor applications. Maya 3D software, used for integrated 3D modeling, visual effects and animation, is coded in C++.
5. Database Software:
C++ and C have been used for scripting MySQL, one of the most popular database management software. The software forms the backbone of a variety of database-based enterprises, such as Google, Wikipedia, Yahoo, and YouTube etc.
6. Operating Systems:
C++ forms an integral part of many of the prevalent operating systems including Apple’s OS X and various versions of Microsoft Windows, and the erstwhile Symbian mobile OS.
7. Enterprise Software:
C++ finds a purpose in banking and trading enterprise applications, such as those deployed by Bloomberg and Reuters. It is also used in the development of advanced software, such as flight simulators and radar processing.
8. Medical and Engineering Applications:
Many advanced medical pieces of equipment, such as MRI machines, use C++ language for scripting their software. It is also part of engineering applications, such as high-end CAD/CAM systems.
9. Compilers:
A host of compilers including Apple C++, Bloodshed Dev-C++, Clang C++ and MinGW make use of C++ language.

Hackerrank Solution: Roads and Libraries (Graph Theory)

Problem link from hackerrank

The solution is given below with the introduction of DFS.

Introduction:

Algorithm: DFS (Depth First Search) - A graph algorithm.

If you read the problem, you can guess this is a bit advanced problem yet it is very important to learn the algorithm of this problem as early as possible. To solve the problem we have used DFS(Depth First Search) algorithm. This is one of the fundamental algorithms of graph theory. This is needed not only for algorithm courses but also to solve many programming problems. It is also used in other real-life graph related applications.

More info. about DFS in wikipedia. Here is a youtube video for visual understanding.

Now that you have understood the algorithm. I recommend you see the implementation in geeksforgeeks because I've taken the help of this code to solve this interesting problem.

Solution link in GitHub 

Explanation:

After reading the problem and understanding the DFS algorithm from the discussion above, the solution will be much easier to understand. Here the damaged roads are edges and the cities are nodes. A graph may contain several clusters.  A cluster is a set of nodes that are somehow connected to each other (directly or indirectly) but not to other nodes in different clusters.

So each cluster can be considered as a sub-problem / sub-task. The solution for all the clusters will be the final solution. 

A cluster will have at least one library. So the solution will be at least cost_of_library times the number of clusters. After this initial consideration, we are now to decide whether to build a library in each city or to repair the roads of a cluster. If there are 'c' cities in a cluster, there will be c-1 roads.

Now if cost_of_library < cost_of_road, we are better off building c-1 additional libraries in the other c-1 cities adding (c-1)*cost_of_library to our total cost  and if cost_of_library > cost_of_road, we just repair the c-1 roads adding (c-1)*cost_of_road to our total cost.

Now we are to determine the clusters. Here DFS comes into play. We start DFS on non-visited nodes and mark the visited ones. When we start new DFS on a non-visited node, we are traversing a new cluster because previous nodes of other clusters, determined by previous DFS, are unreachable from this new node. After determining the number of nodes in a cluster (using DFSUtil function), we at first add a library's cost and then depending on the condition either add road reparation cost or add additional library cost.

After traversing all the nodes, we have finally determined the optimal cost.

Hackerrank Solution: Repeated String

Problem Link

Solution Link

Explanation:

This is a simple string manipulation problem. At first, we count the number of a's in the given string and the number is saved in countA variable. We just subtract the number of non- a characters from the string length to find that out. Since we are taking an-length part from an infinite-repeating string, the n-long part will have several occurrences of string s. The variable chunk determines the number of occurrences. So chunk*countA represents the number of a's in chunk number of s strings. We may have a remainder string portion for which we used a separate for loop to count the number of a's there. Last we print out the result.
Runtime: O(n) We used a single loop.

Note: Here n is long type variable because of the constraint 1<=n<=10^12. In Java integer range is -2,147,483,648 to 2,147,483, 647    .And  the range for long is -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807.

so we have chosen a long type variable for n.

You can learn more about Java's variable type ranges from this article by cs-fundamentals.

Beginner's guide: Best Programming Websites for a Novice

There are tons of websites that cater to learning and practicing programming. While some are suitable for beginners, many others are for a bit mature programmers. Here is a list that I use. I recommend these websites to beginner programmers. These are fun, good-looking websites and It won't disappoint you when it comes to guiding you to learn to programme better.


Hackerrank.com :    I have already written a review about this great and fun website in another blog post. Check it out   http://aprogrammersexperience.blogspot.com/2017/05/review-hackerrank-1-great-site-for.html

codeforces.com: It regularly arranges contests where the problems are set by gradual difficulty levels. The problems are later stored in an archive along with their discussions. This is a great website for those who have already learnt the syntax of C, C++ and Java.

codechef.com :   It is also like codeforces with a cute looking interface. But here, the problems come along with subtasks. It means you will receive partial points if the solution passes some of the test cases. This feature is absent in codeforces.com. So I recommend trying out codechef first before proceeding to codeforces.

devskill.com :   This is similar to codeforces but the problems are a little bit easier.

hackerearth.com : This is an interesting website. It has the features of codechef. It also has a fun challenging arena where you duel with another programmer to solve problems as quickly as possible. It regularly arranges various hackathons and idea competitions too. Competing in these hackathons/idea competitions will really broaden your coding horizon.

geeksforgeeks.com: This is not a website for competitions. It is about teaching you about algorithms and their solutions. It is a great guide for your algorithm courses. It explains the solutions of many important, easy and hard algorithms.

tutorialspoint.com: This is a great website to learn a language quickly. They provide numerous examples when explaining an aspect of a programming language. It is your one-stop whenever you need to know something about a programming language. Whenever I find myself confused about syntax or can't remember the syntax I just search through the extensive examples of this website and I am sure to find my answer explained in an easy way.

Beginner's Guide: Best Programming Languages

As a student who is studying C.S(Computer Science), he/she wants to optimize the usage of his/her time learning the most useful/popular programming languages. I will share my advice in this regard.

C and C++

When you first begin programming, it is recommended to learn how logic works behind coding to solve problems and such. C and C++ are the first 2 languages to learn to build a strong basis of logic and coding. While C is needed to practice the skill of logical thinking at the most basic level, C++ gives you the basic idea of Object Oriented Programming (OOP). In many other high-level languages you have inbuilt functions for many activities but in C you may have to build it yourself. Though this may irritate you sometimes, you will also build a strong knowledge about the logic behind the functions. I have written a separate blog post about the importance of learning C++.

Java

After learning C and C++, you have the knowledge about logic and OOP. As a result learning Java won't be too difficult. Using Java you'll find it easier to write solutions to algorithmic problems since you have a basic grasp of logic learning C and also you can make beautiful and useful projects for your college/university with the OOP knowledge of C++. Java gives you the opportunity to learn the basics of building various programming projects involving database, GUI etc.

Python

Currently, python is a widely used, especially in machine learning and data analytics. It's an easy-to-handle high-level language with the benefits of OOP. Many things which were hard to do in C, C++ and Java have become easier with the emergence of Python. You can also use Django to build projects with more comfort than PHP. As a result, Django is slowly taking over PHP regarding the development of backends of website building.

Here is a link to learn more about python's usefulness: Why Learn Python

HTML & CSS

These are the 2 languages that form the basis of making the front end of many projects as well as creating beautiful websites. The other ones mentioned above don't really provide such comfortable tools as these 2 to design GUI, interface , user-control etc. for your projects. While HTML builds the backbone / basic structure of the interface, CSS beautifies it.

Javascript

JavaScript is very easy to learn. No setup is required. JavaScript is used in web browser (Angular, React) and server-side (Node). JavaScript dominates in web development because it’s the native language of the web browser. Node is super popular. There are over 30,000 NPM packages available! There are lots of high-paying jobs for JavaScript developers. There are lots and lots of JavaScript job postings. And all of them are related to front-end web development or Node. JavaScript is an incredibly expressive and powerful language.

If you complete learning these languages, you don't need to worry about building a career in CS. Even if you have to learn new languages, the knowledge you have earned won't cause much difficulty.

Hackerrank Solution: Sock Merchant (a more optimal solution)

Problem Link 

Solution Link

Link to previous less efficient solution

Algorithm : linear array mapping

Explanation:
It is a programming problem for beginners. The problem is about array manipulation. In many array related programming problems array mapping of integers is used to keep track of the frequencies of the elements in the array of a test case. This helps reduce runtime like it does for the current challenge. In many problems of character arrays, this technique is also used to keep keep track of the frequencies of alphabets.

In this problem the range of element value is from 1 to 100. So we initialized a frequency array of 100 elements with 0 because we have not counted any element yet.

Then we traverse the given array and use the elements as indices in frequency array. We increment an element in the frequency array using the elements as indices until we reach the end of given array.
So now the frequency array holds the information of the number of distinct values in the given array.
Next we traverse the whole frequency array and if it is not 0 (the index is present as an element in the given array) we divide the value by 2 to determine the number of pairs of that value and add it to our answer.

Runtime : O(n) (due to traversing a one-dimensional array)
Required Space : O(n) (Using one dimension array)

Hackerrank Solution: Sock Merchant in Java for Beginners

Problem Link 

Solution Link

Algorithm : Brute Force

Explanation:
It is a programming problem for beginners. The problem is about array manipulation. I have used a nested  for  loop to compare every possible pair. If they have the same value they are assigned -1 and the count is incremented. Here of course, you need to check whether any element is -1 before comparing for equality, otherwise, if both are -1, the count variable will be incremented.

Runtime : O(n^2) (due to the second order nested for loop)
Required Space : O(n) (Using one dimension array)

NOTE: I will try to post a more efficient solution with less run-time in near future.

Hackerrank Solution : The Birthday Bar / Birthday Chocolate

Problem Link

Solution Link

Explanation:

The solution is written in the getWays() method. At first we check whether n (the size of array) is less than m. If that's the case, there's no way we can satisfy Ron since we can't give him m consecutive pieces anymore. So we return 0.

Otherwise we enter a nested loop where m consecutive elements from index i to i+m are added and saved in tempSum which is evaluated to see whether it is equal to d. If it is, we have found a way.

Finally after iterating through the loops we can just print our answer that we get as a returning value from the getWays() method.

Runtime : O(n^2) since we have used a second order nested loop. 

Hackerrank Solution

Problem Link: The Hurdle Race

Solution Link: Here

This is a very easy problem. You just need to find the maximum height and subtract from it 'k'. This result shows the minimum beverages you need. But if the maximum is less than k: congratulations!!! you don't need any beverages.

Solution of : Viral Advertising(problem link)

solution link

At first we initialize three variables m, liked and total with values 5,2(floor(5/2)) ,2 respectively. Here m is the total number of people.  As you can see this simulates the first day.
So the loop must simulate from the 2nd day to nth day. Hence it is initialized with i=2.
Each iteration simulates a day. At first we calculate the total number of people exposed to advertisement i.e. m = liked*3;
next we divide the value of m by 2 to get the number of people that liked the
ad. This is equivalent to floor(x/2). The result is then added to the total number of likes.

After getting out of the loop we just print the total as desired. :)
#HappyCoding