Friday, September 1, 2017

Data Structures: Dynamic Array implementation in C++ (Part 1)

What is array?
-->Often, we have to deal with groups of objects of same type such as names of persons, instrument readings in an experiment, roll numbers of students, and so on. These groups can be conveniently represented as elements of arrays. An array is defined as a sequence of objects of the same data type. All the elements of an array are either of type int (whole numbers), or all of them are of type char, or all of them are of floating decimal point type, etc. An array cannot have a mixture of different data types as its elements. Also, array elements cannot be functions; however, they may be pointers to functions. In computer memory, array elements are stored in a sequence of adjacent memory blocks. Since all the elements of an array are of same data type, the memory blocks allocated to elements of an array are also of same size. Each element of an array occupies one block of memory. The size of memory blocks allocated depends on the data type and it is same as for different data types. 

Here's a youtube video to understand the concept of Array : Intro into Arrays


In this post we are going to look at the C++ implementation of Array meaning , we will write the code for several functions to manipulate an Array. By successfully understanding these functions , we will know how an array works.

Each Computer Science student must do an obligatory course on Data Structures. During this course , the students come across the implementation of many data structures. Arrays list implementation usually comes in the beginning of the course. So this is one of the easier data structures to both understand and implement.

We are going to complete 6 tasks to create a complete code manipulate an array list. This code will be helpful in teaching you guys to manually make your own code for data structures. Such codes are needed in the future in situations where custom made array list codes are needed. After the 6 tasks I will show you an example to implement this code to solve a problem.
The 6 tasks are:

Task 1: Add getLength function. Add a new function getLength to the list. This function will return the current length, i.e., the number of items, of the list.

 Task 2: Add insertItemAt function. Add a new function insertItemAt to the list. This function will insert a new item at a given position. The prototype of the function is as follows: int insertItemAt(int pos, int item). The function will insert the given at the given . You have to do this by shifting only one item of the existing list. Note that the pos value can be larger or equal to length variable. In such a case, you should not insert anything in the list. You may also require allocating new memory similar to insertItem  function if list is already full.

Task 3: Add shrink feature to the list. The current implementation expands its memory when it is full. This is done in the function. When it finds that the length variable has reached the value of listMaxSize, it allocates a new memory whose size is double the existing memory. Your job is to add shrink feature to the list. This feature will allow the list to shrink its memory whenever the length variable has reached to half of the current size. In that case, you will reallocate a new memory whose size will be half the current size. However, if the current size of the list is LIST_INIT_SIZE, then you will not need to shrink the memory. Write a function shrink that will shrink the list appropriately.

Task 4: Add deleteLast function. Add a new function deleteLast  to the list. This function will behave similar to existing deleteItem function except that it will delete the last item of the list. You will not need to move any other items. So, this function will not have any input parameter. You must call the ℎ function after deletion. You will also require adding shrink function calls inside deleteItem and deleteItemAt  functions.

 Task 5: Add clear function. Add a new function clear to the list. This function will delete all items from the list and will de-allocate its memory. When a new item will be inserted next, the list must be allocated a new memory of size LIST_INIT_SIZE again. You must write required codes in the insertItem  function to enable this.

 Task 6: Add deleteAll function. Add a new function deleteAll to the list. This function will delete all items from the list, but will not de-allocate its memory. However, it will shrink its memory to LIST_INIT_SIZE if the list is currently consuming a memory whose size is larger than LIST_INIT_SIZE.


Before I head on to the solution, I want you guys to think about the tasks and write codes solving them. This will increase your capability to think about problem solving. I will write blog posts describing the solution in near future.


Don't forget to share and follow my blog-posts...... See you guys next time. :)

Wednesday, August 30, 2017

CodeForces: New Year Transportation(500 A) Solution in Java for Beginners

 New Year Transportation(500 A) Problem Link



The solution is found in the problem, so I suggest you try it by yourself.
If you need a quick reminder for while loop, check out this youtube video of newBoston.
You can find tutorial for if-else , in this tutorialspoint page about if-else.

.
.
.
.
.

New Year Transportation(500 A) Solution Link

If you are facing problems solving this , now you can come here for the solution. So after taking the necessary input, you begin from the first index (currentIndex - set to 1). Then you enter a while loop. Here on every iteration you check whether you've reached your destination, on which case done variable will be true. If currentIndex > destination, you'll never get to destination since you can't travel backwards. In this case you just break out of the loop. The loop will terminate once you've traversed the whole array.

Finally you check  whether done is true (you've reached your destination) or false(otherwise).


Check out my other codeforces solutions in  under codeforces label.



Tuesday, August 22, 2017

Codeforces: Pangrams 520A Solution in Java

Problem link of 520A

Solution link in github

The problem is a quite simple one. If you learn Java Strings, it'll be a piece of cake. I suggest you try the problem yourself before proceeding. As a quick reminder, check out this short java string tutorial from tutorialspoint  as a guide to this problem.

When taking input, in line 13 I've written an extra sc.nextline(), because when taking a string input before an integer input omitting line 13 would cause erroneous input. So line 13 works as buffer to correctly take a string input after a numerical input.

The 'frequency' integer array will count the occurrence of each character in the input string. frequency[0] refers to count of 'a', frequency[1] refers to count of 'b' and so on. For convenience I've converted the whole string into lowercase. To determine index into this array for a particular character just subtract 'a'. For example index for count of 'c' is 2. So if we encounter 'c' just subtract 'a' to get the index 2.

Next we check for the number of elements in the frequency array that have non-zero values. If it's 26 we output 'YES', since all the characters in the alphabet are present. Otherwise print "No".

Hope you find this useful. Check out my Hackerrank Solutions in Java. Don't forget to share and follow :) 

Monday, August 21, 2017

CodeForces: Ultra Fast Mathematician-61A Solution in Java

Ultra Fast Mathematician-61A Problem Link

Solution Link in Java

The problem is a quite simple one. If you learn Java Strings, it'll be a piece of cake. I suggest you try the problem yourself before proceeding. As a quick reminder, check out this short java string tutorial from tutorialspoint  as a guide to this problem.

Now let's come to our solution. After taking the input, we enter a for loop with range from 0 to n-1 , where n is the length of the input string(both strings have the same length). We extract one character from each string and put them in two character variable a and b.

We now check whether they are the same character or not. If they are the same, we output 0. Otherwise, we print out 1 since a and b are not same characters.

After the loop is finished, we get the desired output binary string.

If you face any problem or have any other suggestion, feel free to post a comment.

Don't forget to share and subscribe.

Thursday, July 13, 2017

Beginners Guide: Google Ranking. Tips for Improvement In Ranking

What is Google Page Rank:

Page ranking by Google follows an algorithm called PageRank (PR). The purpose of this algorithm is to rank websites to display in Google search engine and use this resultant rank to order websites in that search engine to put the more popular pages to the front. The basics of the algorithm is to calculate the a website’s quality by determining the number of links of various other websites pointing to the website and also the quality of the aforementioned links. In simple mathematical terms, if a page provides quality content, it is considered more important to a wider population of internet users. As a result, it will get a higher number of links from other websites.
When Google first launched its search engine, this algorithm was used. It is the best-known algorithm so far though other algorithms have been developed since that time.
If you want a comprehensive description and analysis of PR algorithm, check out the wikipedia page for Google PR.

For bloggers interested in SEO(search engine optimization), this term comes up sooner or later because they want to put their blog or website at the front pages of google or any other search engine. This blogpost discusses the factors to use this concept for one’s benefit i.e. to make one’s website rank higher in the search engine.

WHY Does Google Page Rank (For SEO) Matter:
Many believe Pagerank is dead- a propaganda spouted everywhere. This is incorrect. This is a very important algorithm that will always be used to rank websites. Many SEO practitioners don’t understand it well and may say it’s not important. But it would be wise not to heed to such ill advise. Many think so because Toolbar PageRank is indeed dead.So what is Toolbar PageRank? It is a webtool to determine the rank of a page by analysing search information from Google’s database.
It used to help SEO bloggers since the tool was updated several times but now according to this souce, Google has now decided to remove this tool.  On their part it’s a considered as a ‘smart’ business decision to stop the manipulation of search results.
The real algorithm, however, is still running but the visual tool used by the bloggers is now taken out. Since the algorithms is running behind the curtain to influence the search results, it is still relevant for bloggers to pay attention to this, if they want to bring their pages forward in the search engine. Thus Google PageRank still matters, though we may not have a visual of the results.
What Should A Blogger Do To Improve Google Page Ranking:
  1. Post  Quality Content:  At first plan what to write and do some research. Writing relevant and informative content is the most important thing for any blogger before thinking about any other SEO strategy. Creating posts for a specific group increases the probability of increased site traffic. Try to think from a reader’s perspective. What do they want in your article? Are you, the poster, providing enough information to satisfy the need of the reader? What will the reader search about in the google search bar to get to your website? All these questions should come to your mind before heading to write a post. For example check out this blog-post (Best Programming Websites for Beginners) from A Programmer’s Experience where the article is targetting beginner programmers and their confusion about where to learn and practice programming. They wanted to see a compiled list of websites ready for them to browse through along with information to let them know what they can expect from each link. They frequently search the web for “programming websites for beginners” and such. Some may fill their posts with keywords but that will ruin the quality of the post and the popularity of the website will eventually decrease. So you must be careful of that.

  2. Frequent Update:  Many feel lazy after a while and start delaying their posts. This is a big no-no especially for the beginner bloggers. Google checks the regularity of websites. Websites that are updated regularly are considered to be more important by PageRank algorithm. Infrequent updates or posts is a leading cause for websites to slowly lose their viewership.

  3. Metadata: Metadata is the information about the page. You can see this youtube video about the definition of metadata. It is very important since search algorithms use this to analyze the popularity of search keys and relevance of pages. They can be added to titles and description. Descriptive metadata should be like an advertisement since they are shown below the link to a page in the search results. For example in the blog-post for Beginner's Guide: Discrete Mathematics And Programming Contests. A descriptive metadata has been added-“It's a Beginner's guide to discrete mathematics and its importance for and  relation to programming contest”. And this is shown in the search result in the following figure





  1. Links to Relevant Websites: If links to other websites are added, be sure the websites you are linking to are popular websites and the links work properly. These not only help the linked websites to rank better but also help you get more viewers since the PR algorithms recommends your websites to have a higher rank. But there is small but important trick here. Rather than writing “click here” or “here” or “this website”, spell out the website name or a keyword referring to that website.

  2. DescriptiveImages:  Alt tags or alternative text descriptor are highly recommended to be used when inserting images or videos in your blog posts. This alt tags help Google to locate and rank a page which is the most important factor for any page/post. Learn more about alt tag in Accessibility’s article about Alt Tag.

  3. Social Networking:  Whenever a new post is written, share it on various social platforms. Some of the popular ones are facebook, twitter, pinterest , google+, youtube and quora. They help you get instant views. The increase in viewership will obviously be noted by the PageRank algorithm for better ranking. Also posting in these platforms, the links to your website will also increase internal count variables of the algorithms which are used to determine page ranks. They can also be used as advertising platforms.



There are so many other advice out there in the internet but these are considered to be the most important for any blogger to follow.



If you are interested in programming problem solutions, reviews of programming websites and useful articles for beginners, feel free to check out A Programmer’s Experience.






Thursday, July 6, 2017

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. 

Saturday, July 1, 2017

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

Wednesday, June 28, 2017

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.


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


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. 


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.



Monday, June 26, 2017

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 potions 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 main loop.

Remarks:

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




 















Sunday, June 25, 2017

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 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. Graphic 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, are also scripted in the 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 development of advanced software, such as flight simulators and radar processing.
8. Medical and Engineering Applications:
Many advanced medical equipments, 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.

Thursday, June 22, 2017

Hackerrank Solution: Roads and Libraries (Graph Theory)

Problem link

Solution is given below 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.


Explanation:

After reading the problem and understanding 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. 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' citites 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.

Data Structures: Dynamic Array implementation in C++ (Part 1)

What is array ? --> Often, we have to deal with groups of objects of same type such as names of persons, instrument readings in an expe...