Lucky Day!! Getting Blogger Recognition(Trafotoz) AND Liebster Award(Nikkistalk)

So recently I have received a "Blogger Recognition Award" from Trafotoz, along with 8 other blogs. And nikkistalk nominated me for Liebster Award along with 4 others. You can view the award page with all the nominations in here  Blogger Recognition Award page(Trafotoz) and Liebster Award(nikkistalk). The Awards are about posting interesting contents on a regular basis.
For me this is a very exciting and good news because I've only started blogging for about a month using the platform google's blogger.com . And now I've received this achievement for my hard work and time investment behind my blog Programmer's Experience.

What's my blog about?

I have started my blog to share my experience as a CSE student of the best engineering university of Bangladesh BUET (Bangladesh University of Engineering and Technology). Since I had to practice a lot of programming problems using many websites/platform such as Hackerrank, Codeforces, Codechef  and Hackerearth  and I also had to complete a lot of class projects in C++, C , Python, Java , HTML,CSS, Javascript , SQL , Assembly etc, I decided to write about these experience in a blog to help other people who are interested in programming /coding or are students of CSE. And what's the best way to share my ideas and experience? The answer is blogging. 

My blog includes reviews, programming problem solutions and advice for beginners on programming. As of now I've written 16 posts in the span of a month and  the response was very positive and now I've received the recognition I've sought since the beginning. I plan to continue my effort and contribute more to the programming community. 

Some tips to newbies...(from my experience)

1. Write contents with necessary links and it should be at least 100-150 words
2. Post the blog-post links to appropriate forum, facebook groups and pages, youtube and google+
3. Use quora.com  to embed your blog-post links to your answers to get more views.

I've followed these simple yet effective rules to get quick views and a growing viewership. I hope it works for you to. 

Don't forget to share and subscribe. Leave your comments below. 

Beginner's Guide: Discrete Mathematics And Programming Contests

As a student of CSE, one must complete a course on Discrete mathematics. Many then become confused why they should even learn this mathematical subject. Discrete mathematics is a vast topic, but here are some essential things that you should know to be able to solve programming contest problems:

• Counting : You are going to see a lot of problems like "Count the number of ways to do X". In most of the cases, enumerating all possible ways is simply not going to work, and you are expected to use some kind of dynamic programming. To be able to solve counting problems properly, you need to have a good understanding of certain topics such as:
• Recurrence relations : Ubiquitous in counting problems. In particular, learn to come up with recurrences for counting. Also, learn to convert recurrences of high complexity to lower complexity
• Matrix exponentiation : In the case of recurrences that have constant coefficients, it is possible to express the final state vector as the product of the power of a matrix and the initial state vector. A good example is calculating Fibonacci numbers using matrix multiplication. This trick helps to reduce the complexity of finding Nth term of some recurrences from O(N) to O(Log N)
• Binomial coefficient : Many counting problems with symmetries can be reduced to finding a few cases and multiplying them with some binomial coefficients. So learn to calculate these efficiently depending on the type of problem. There are different kinds of precomputations one does. Also, try to learn the properties of binomial coefficients modulo primes.
• Pigeonhole principle : More of a proof-aid technique rather than something that you directly apply. But I have used this in cases where I was required to find two cases which share some property. Birthday attack can be thought of as the probabilistic variant of pigeonhole principle, but it is not that commonly used.
• Inclusion–exclusion principle : How to formalise dealing with double counting. It is sometimes so much easier to double count in the beginning and use inclusion-exclusion later than to try some double counting avoiding recurrence
• Subsets and Permutations : Learn to generate subsets of a set and permutations of a sequence. There are some counting problems where you are expected to sum up quantities over permutations or subsets. DP over subsets is something that you should learn too in this regard.
• Indistinguishable and distinguishable objects : Learn the difference, and learn how counting changes between the two cases.
• Lattice problems : Counting the number of ways to go between two points on a lattice with various kinds of restrictions is a very common problem. Learn the basic method, and how things like binomial coefficients and Catalan numbers appear in the solutions.
• Counting on graphs : The questions of this type that I have seen commonly include tree DPs. Counting problems on non-tree graphs are usually hard. You see problems coming up based on Kirchhoff's theorem once in a while too.
• Pólya enumeration theorem : I have seen this coming up in contests only a couple of times. But learn this and if something comes up, it should be easy for you.
• Learn to work with moduli : Most of the times, you are asked to do the counting mod some big prime (most favourite is 10^9 +7). Learn to do the calculations without overflow, and learn some basic properties of primes from group theory which help solve some problems.
• Probability and Expectation value : Here are the basic things you should know:
• Calculating probabilities as ratios of counting problems : Do this and you can calculate things to very good accuracy
• Recurrences for probabilities and expectation values : In a lot of cases, even when you can count and take ratios to get probabilities, it is much easier to find a recurrence directly in terms of probabilities. Taking care of double counting can be a pain though
• Linearity of expectation value : Learn to use it right (I can't) and many expectation value problems should be cakewalks for you
• Random walk : Modified random walk problems come up very often as probability/expectation value problems, so learn the basic results
• Coin toss problems : Another set of practically overused problems

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.