Arpit Mishra

Perhaps a post on these programming languages needs no fore ward. But then again, for the skeptics who are rooting for Go and Swift, here’s a little bit of background that reinforces the fact that despite not being the most popular ones today, these object-oriented languages still form the base for many applications.

Why bother

Java and C# were touted as the pet languages of the 2000s. Now, people talk Python and Ruby, Javascript and PHP.However, fundamental programming skills still necessitate a solid foundation in C and C++. (You can read more here- Top programming languages that will be most popular in 2017)

TIOBE may be scorning C now, but Dice and other job portals show a significant demand for these skill sets across industries. Beginner-friendliness, scalability, and a sizable community continue to make C++ a major player as well.

“They [C and C++] are the native tongue for system-level programming, and they probably will be for many years. Eventually, though, languages like Google Go or D may replace them,” says Gartner Research Analysts Mark Driver. “The trial-by-fire of learning C tends to weed out the noncommitted, so knowledge of C at the very least makes you stand out,” he added.

These languages act like a “mental model” that helps you go where places you thought you couldn’t. Bjarne Stroustrup, the C++ creator, says, “Basically, nothing that can handle complexity runs as fast as C++.” Used with some scripting language, it is for “high performance, high reliability, small footprint, low energy consumption, all of these good things.”

With a plethora of resources available, choosing the best can leave you in a tizzy. We’ve got a list, a valuable one, which keeps the curious ones who wonder what’s beneath the hood get as “close to the machine” as possible.

Stroustrup: The C++ Programming Language (4th Edition)

What’s better than studying from the guru himself? Bjarne Stroustrup created C++ in 1979.

The book covers the language in its entirety, talking about containers, algorithms, abstraction mechanisms, concurrency, utilities, basic facilities, standard libraries, and design models. This reorganized edition discusses C++11, a version that followed C++03, and then got superseded by C++14 and C++17 later on. A must-have for programming enthusiasts, because it certainly is a definitive reference book for general programming principles and practice using C++. Reviewers are raving about the code examples and the way the language has been presented. It may not be the best book for novices according to some readers; it is more of a “description of the features and the reasoning” than answering how-tos. Look at the detailed table of contents here and access the exercises here.

You can buy the book here.

Accelerated C++: Practical Programming by Example by Andrew Koenig and Barbara E. Moo

For learners who are eager to get into the practical aspects of C++, this book, which is a part of Stroustrup’s C++ in-depth series, is the go-to reference. If you don’t have time for the basics, then you can go directly into the coding bit with the help of Koenig and Moo’s “accelerated” C++. Topics covered include “basic string handling, loop and flow-control statements, arrays, functions and methods, iterators, file I/O, operator overloading, inheritance, polymorphism and virtual functions.”

Founding member of the ANSI/ISO C++ committee, Dag Brück, says “This is a first-rate introductory book that takes a practical approach to solving problems using C++. It covers a much wider scope of C++ programming than other introductory books I’ve seen, and in a surprisingly compact format.” The authors talk about features using understandable examples, teaching you how to use the features rather than trying to explain the whats and whys. It takes you from standard library abstractions to defining your own. Key takeaways that crystallize low-level and high-level concepts and end-of-chapter exercises cement your understanding.

With this book, you can begin programming right away!

You can buy the book here.

C++ Primer (5th Edition) 5th Edition by Stanley B. Lippman, Josée Lajoie, and Barbara E. Moo

In the C++ primer, the authors focus on the 2011 revised standard. In the Why Read This Book section, they say they “emphasize good style and explain the rationale behind the rules.” The first part of the book covers basics of C++ such as variables, strings, vectors, arrays, expressions, statements, functions, and classes. The next section deals with the I/O library, sequential and associative containers, generic algorithms, and dynamic memory. Another part takes you through copy control, overloaded operations and conversions, OOP, templates, and generic programming. The primer teaches you high-level programming techniques, such as specialized library facilities and tools for large programs, in the later sections. Learners don’t have to know C, but they need to be familiar with writing, compiling, and running a program “in at least one modern block-structured language.”

You can buy the book here.

Effective Modern C++: 42 Specific Ways to Improve Your Use of C++11 and C++14 (1st Edition) by Scott Meyers

A part of his Effective C++ book series, this edition talks about how you can use the new features of C++11 and C++14, such as lambda expressions and move semantics, effectively. A software architect at Microsoft and chair of ISO C++ standards committee, Herb Sutter, says: “After I learned the C++ basics, I then learned how to use C++ in production code from Meyer’s series of Effective C++ books. Effective Modern C++ is the most important how-to book for advice on key guidelines, styles, and idioms to use modern C++ effectively and well. Don’t own it yet? Buy this one. Now.”

With this book, Meyers ensures that you can “create software that’s correct, efficient, maintainable, and portable.” Topics covered include perfect forwarding, except specifications, braced initialization, auto type declarations, and differences between std:: atomic and volatile and their relation to the concurrency API of C++.

A few reviewers feel that some basic knowledge of C++ is required to fully appreciate this edition on modern C++. Lots of great examples and bite-sized “items” tell you why the features have been added and what they can do; it is a set of guidelines on the newer additions to C++ rather than an introductory text to learn C++.

You can buy the book here.

Exceptional C++: 40 New Engineering Puzzles, Programming Problems, and Solutions by Herb Sutter

This top-quality book is a part of Stroustrup’s C++ in-depth series. Written by Herb Sutter, arenowned expert in C++, the book talks about the what, the why, and the how-to of “solid software engineering” using scenarios in a problem-solution format. Sutter answers questions such as “How does writing inline affect performance? How does exception safety go beyond try and catch statements? What’s the real memory cost of using standard containers?”

If you want to be one of the best C++ programmers around, Exceptional C++ is a definitive guide to topics such as generic programming, writing reusable templates, exception safety issues, compiler firewalls, class design, inheritance, and polymorphism, and optimization. Exemplary presentation and entertaining puzzles make this a must-buy. His next book, More Exceptional C++: 40 New Engineering Puzzles, Programming Problems, and Solutions continues the journey. With an aim to help you write exceptional code, the book comes with new detailed sections (e.g. multi-threaded environments) and insights on vital topics covered in the prequel.

You can buy the book here.

The C Programming Language 2nd Edition by Brian W. Kernighan and Dennis M. Ritchie

Despite having been originally published in 1978, this amazing book continues to be the bible for C programmers. Ritchie (1941–2011) was the original C language designer, and he also co-designed the UNIX OS. The K&R (authors) C version is different from the ANSI C or the earlier version.

The book discusses has challenging exercises to help you attain a working knowledge of C. It concisely and clearly types, operators, and expressions, control flow, functions and program structure, pointers and arrays, structures, input and output, and the UNIX system interface. You need some programming background; you need to know what a compiler is; the book teaches you the syntax and not exactly the programming principles. For example, when it talks four pages about functions, it doesn’t actually tell you what a function is. Still, this seminal text has the first Hello World program.

In the preface to the second edition published in 1988, the authors write: We have improved the exposition of critical features, such as pointers, that are central to C programming. We have refined the original examples, and have added new examples in several chapters. For instance, the treatment of complicated declarations is augmented by programs that convert declarations into words and vice versa. As before, all examples have been tested directly from the text, which is in machine-readable form.

You can buy the book here.

A Book on C: Programming in C (4th Edition) by Al Kelley and Ira Pohl

Kelley and Pohl have put together a great tutorial on ANSI C. The authors have used unique and clear explanations of program code, along with all-encompassing exercises and summary tables, to highlight the power of C, a general purpose programming language.

The USPs of the book include a chapter on how to move to Java from C, detailed coverage of pointers, multi-file programming, and recursion, an improved standard library functions appendix, and more focus on abstract data types. The comprehensive tutorial on ANSI C also discusses input/output and the operating system, lexical elements, operators, and the c system, the preprocessor, structures, functions, unions, transitioning to C++ from C, how ANSI C is different from traditional C, and advanced applications.

You can buy the book here.

Expert C Programming: Deep C Secrets by Peter van der Linden

This book isn’t for a beginner either. Once you have learned C from K & R, Linden’s book can answer questions such as “How can you debug linker errors? What is an activation record? Why are arrays and pointers not identical?” Unlike most bland technical books, Linden has managed to keep the reader engaged with humor, puzzles, depth of content, cultural references, and exercises. Although some bits in the book may not seem relevant anymore, it is still a satisfying read with its hacker stories and more.

John Barry, the author of Sunburst, Technobabble, and other books says “In Expert C Programming, Peter van der Linden combines C language expertise and a subtle sense of humor to deliver a C programming book that stands out from the pack. In a genre too often known for windy, lifeless prose, van der Linden’s crisp language, tongue-in-cheek attitude, and real-world examples engage and instruct.”

For C programming enthusiasts, this book is about the background stories and the appreciation for the language. The lore aside, Linden discusses advanced concepts related to compiling, pointers, and memory usage. The 11 chapters have positive titles that make you curious about linking, runtime data structures, declarations, arrays, and so on.

You can buy the book here.

Let us C by Yashavant P. Kanetkar

This is a book that helps you learn C from scratch. The author, who says he picked up the language from Dennis Ritchie’s book on C programming, has explained the basic concepts such as decision control instruction, complex decision making, loop control instruction, complex repetitions, case-control instruction, functions, pointers, recursion, data types revisited, the c preprocessor, arrays, strings, structures, console input/ output and file input/ output, C in Linux, and operations on bits in an easy-to-understand format. The book also teaches you how to create programs using Visual Studio and NetBeans.

You can buy it here.

Introduction to Algorithms 3rd Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein

This is what Daniel Spielman, Henry Ford II Professor of Computer Science, Mathematics, and Applied Science at Yale, has to say about this book, “Introduction to Algorithms, the ‘bible’ of the field, is a comprehensive textbook covering the full spectrum of modern algorithms: from the fastest algorithms and data structures to polynomial-time algorithms for seemingly intractable problems, from classical algorithms in graph theory to special algorithms for string matching, computational geometry, and number theory. The revised third edition notably adds a chapter on van Emde Boas trees, one of the most useful data structures, and on multithreaded algorithms, a topic of increasing importance.”

The book is meant for readers at all levels. With a bit of programming background, learners can grasp the magic—design, and analysis—of algorithms. The book broadly covers foundations, sorting and order statistics, data structures, advanced techniques such as dynamic programming and greedy algorithms, advanced data structures such as Fibonacci Heaps and van Emde Boas Trees, graph algorithms, and a few selected topics such as matrix operators, linear programming, polynomials and FFT, string matching, computational geometry, and NP-completeness.

You can buy the book here.

Data Structures and Algorithms Made Easy by Narasimha Karumanchi

For whom is this book? Prof. Hsin-Mu Tsai, National Taiwan University, answers it in his book review. He says, “This book is a good supplement to a conventional data structure textbook, as it offers many good code examples and selections of relevant problems **with solutions**. There is no deep analysis or detailed proof in this book, which is not what this book is for (for example, as a textbook to teach algorithm and complexity analysis), and what you would be able to find in a conventional data structure textbook. The book could also be good for a professional who just wants a quick review of important data structure concepts and implementations.”

Reviewers on Amazon believe that this book is a must-have for job interviews and competitive exams. The author emphasizes problem analysis over theory. The book is coded in C and C++. A comprehensive introduction, recursion and backtracking, linked lists, stacks, queues, trees, heaps, graph algorithms, sorting, searching, selection algorithms, symbol tables, hashing, string, divide-and-conquer, and greedy algorithms, complexity classes, and dynamic programming are the key chapters in the book. Looks like he has covered just about everything you need for a binge-reading evening!

You can buy the book here.

Summary

Computers are not about calculations, they are about information—organizing, retrieving, and manipulating it. You want to write efficient programs? Then you need to understand and learn to work with data structures. Data structures and algorithms tell you how you can put the programming languages you mastered to good use. Pick up C and C++ and implement and play around with data structures, and see how exciting it all is. In spite of young upstarts, dependable C and C++ continue to be the programming languages of choice for several applications.

[Bonus content – Read our latest blog – Top 10 cities to hire developers]

This time we decided to figure out which are the top countries to work with, for programming enthusiasts making a living as developers, software engineers, or data analysts.

From my experience, English speakers can find the most jobs in the U.S. (West Coast, obviously), United Kingdom (London), Ireland(IT employers always ask how to hire workers from Ireland), Netherlands (Amsterdam), Switzerland, and Belgium.

New Zealand and Australia are pretty popular among developers who love the laid-back lifestyle.

But the scenarios change when we talk about non-English speaking nations.

Japan is growing exponentially; Russia and China have a huge culture of programming, and IT companies are growing rapidly in these countries; and India, Southeast Asian countries (Singapore and Indonesia), and South Korea (Seoul) are other popular and growing markets.

Often, the lower median salary is easier to stomach because of the lower cost of living.

What is important to understand that the definition of “best country” may not be categorical, and depends on a lot of people’s preferences.

To keep things fair we decided to dig up data from some popular sources to identify the best countries to work in for software engineers.

We listed these countries in order of their Happiness index and technological advancement in the field of IT over the years.

Top 10 countries forSoftware engineers / Developers/ Data Scientists to work

1. Switzerland
2. Canada
3. Australia
4. Netherlands
5. Germany
6. USA
7. Sweden
8. Denmark
9. Singapore
10. United Kingdom

You can read the detailed research below and other picks of top countries list based on various job profiles

Google Trends

Google Trends is a public web facility of Google Inc., based on Google Search, that shows how often a particular search term is entered relative to the total search volume across various regions of the world, and in various languages (Wikipedia).

Read What is Google trends data – and what does it mean? if you want to know more.

The numbers in the table depict the popularity of one language over another, as searching on Google.

A programming language with a higher number shows that the interest is higher as compared to other languages.

This popularity could be due to academics, a professional requirement, or interest which leads to various job opportunities.

As discussed, Java is fairly popular.

Python is one of the most searched languages in Australia. C#, despite showing a high requirement in the job portal, is not really popular.

Swedish people had been searching for Swift programming language more often than others.

Ruby leads in Ireland. MatLab is a popular Google search term in almost all the listed nations, showing its relevance in academics.

(Also read – How to hire a full stack developer)

The below graphs compares the popularity of programming languagesin order of Java, Python, PHP, C#, JavaScript, C++, C, Objective-C, R, Swift, Angular JS, Ruby, Perl, Matlab in each country respectively.

Which means Java and R are searched more often and in greater volume as compared to Swift and Angular Js in Denmark.

Would you like to get updates once a month on our latest articles? We won’t spam, we promise. Subscribe now to The HackerEarth Blog!

Indeed.co

Indeed.co, available in 50 countries and 28 languages, is one of the most high-traffic job websites in the United States and other countries.

Using country-specific search for the number of software engineers jobs listed on Indeed, we found data which matched our previous research on Top programming languages to learn.

While Java remained the favorite in all the top destinations. C, C++, and C# programmers are still in demand in these nations, making them “evergreen” programming languages and famous among software engineers and developers.

In the U.S., China, India, and Japan, PHP developers have quite sought after.

The requirement of R programmers is higher in Switzerland, USA, India, and much more so in Germany and France. Canada, Netherlands, UK, USA, India, and China clearly require MatLab skills.

If you are a Ruby developer, Japan needs you. But Canada gives first preference to Perl coders.

Median Salary – Programmer salary by country

What’s happiness without a handsome salary?

Hence, we listed the average salary for a particular job (Source – PayScale). These values have been expressed in US dollars.

Switzerland, Sweden, Australia, and the United States have higher software engineersalaries than other countries.

A data scientist is one of the highest-paid jobs across the globe. Argentina pays PHP developers generously compared to the country’s average pay for other IT skills.

France is looking for Java and front-end developers, paying them well for their skills.

Japan, Singapore, and, particularly China and India, offer fairly poor compensation despite having a high requirement for skilled employees.

Top countries for Java developers to work –

• Switzerland
• The United States of America
• Australia
• Germany
• United Kingdom

Top countries for.NET developers to work –

• The United States of America
• Canada
• Germany
• Netherlands
• Japan

Top countries for PHP developers to work –

• The United States of America
• United Kingdom
• Germany
• France
• Sweden / Australia

Top countries for Data Scientist to work –

• Switzerland
• Canada
• Netherlands
• United Kingdom / Germany
• The United States of America

Read here – 8 different job roles in Data Science / Big Data industry

We understand that the quality of life, safety, cost of living, state taxes, commute cost, etc. are some of the other major factors to be considered when deciding the top work destinations for a developer.

However, job listing, the popularity of the skill, median salary, and happiness index are equally important.

Every time you try to create a new account on any of the websites, you begin with your name and, more often than not, you get the response “Username is already taken.”

Then, you add “your name + date of birth”, to realize it also has been “already taken” to finally end up with “your name + date of birth + license plate + graduation” to create the account.

I’m sure a lot of you are nodding and saying “been there, done that.”

But how many of you have wondered how these giant sites like Facebook, Instagram, and Gmail verify whether the username is taken or not?

Let’s start with the two possible approaches

A linear search may not be a good idea

Let’s assume that Facebook stores all the data in its directory.

And the software simply checks each name on the list one at a time and if it doesn’t find a match, it tells you your desired username is available.

Doesn’t sound sensible, does it?

The software has to look at each name every time a username needs to be verified.

The technique is unreasonable when you compare it with the Facebook database, which has over 1.5 billion users, and Twitter, which has 300 million users.

What if they use a Binary search?

This makes more sense, with all the brains working at Facebook.

Facebook keeps all the data sorted and arranged in an alphabetized list.

The list is 1.5 billion characters long, stored like a, aa,aaa……xyy, XYZ, yaa,yaa,yxz, zaa, zac and is very similar to your dictionary.

When you enter a name, it matches the entry with the username exactly in the middle of the list. If it matches, the software rejects the new username.

If it doesn’t match (which has a lot of possibilities), the next question the software addresses are “ If searched alphabetically, does the requested username come before or after this username in the middle?”

If it comes before, then the software knows that all the 750 million people after the username found in the middle of the list is of no use for the current search.

That eliminates 750 million possibilities in a single comparison.

If the desired username comes after the name in the middle (alphabetically), it eliminates all the names before it.

Either way, the software eliminates almost 750 million names for search in the first comparison.

Next, it takes the selected half of the list and immediately matches the requested username with the name in the middle of the remaining list.

If it matches, the requested name is rejected and if it doesn’t, the requested name is again checked for the possibility of it occurring before or after the name in the middle.

If it is before, reject the 350 million names after the name.

And go ahead with divide and conquer for the rest of the names as done earlier.

If the requested name is after the middle string, reject the names before it and try with the 350 million remaining names.

By dividing the list every time, you can compare the required username with the names in the list quite quickly…

But the question is…how quickly?

You will continue dividing the list into two until you can no longer do so.

And when you are left with one name in the database, you match it with your desired username.

This would be the last step before you find whether the username “chosen” is available or not.

For data as big as 1.5 billion, this method would need no more than 30 steps. 2 to the power of 31 gives you 2.14 billion, which is closest to our expectation of 1.5 billion users on Facebook.

This means fewer steps and complications for the same data when searched with a linear search.

What if the developers are very smart and use a Bloom filter as the solution?

Before you understand Bloom filters, you need to understand the concept of Hashing.

Hashing is like the license plate of your car.

A hash function takes data of any length as input and gives you a smaller identifier of a smaller, fixed length, which is often used to identify or compare data.

Bloom filters work simply – Test and Add.

Test whether the element is present in the list:

• If it returns false, the element is definitely not on the list.
• If it returns true, the element might probably be on the list. This false positive (will discuss it below) is a function of the Bloom filter and depends on the size and is independent of the hash function used.

A Bloom filter divides the memory area into buckets, which are filled with various hashes generated from one or many hash functions.

Let’s understand with an example.

Suppose, you have a memory bucket of size 10 and 3 hash functions which will give you three unique identifiers.

Suppose, you enter Ronaldo into this memory bucket.

Ronaldo, when passed through these hash functions, gives the value of 1,4, and 5. The filter quickly fills the memory in the bucket with these identifiers.

Now, you enter Messi into the memory bucket. Messi, when passed through the hash function, gives its own unique identifier. In this case, it is 3,7, and 8 and the filter fills the bucket.

As the functions always return the same value for similar inputs, we can be sure that when the name Ronaldo is given to the filter, it would check in locations 1,4, and 5 to find it full, which means that the name Ronaldo is already on the list.

Let’s continue with another example of entering Rooney into the memory.

Rooney, when passed through the hash function, returns 2,6, and 8. The filters check the memory to find that though 8 is full 2 and 6 are empty, which means you don’t have Rooney in the memory.

Therefore, the name is available.

But when the name Neymar is passed through the hash functions, it returns the value of 1,3 and 7 which eventually makes the filter believe that the name Neymar is already present on the list.

This scenario explains the concept of false positives used in Bloom filters. One can control the false positive by controlling the size of the Bloom filter.

More space is inversely proportional to false positives.

Each of the above-mentioned techniques comes with its own advantages and disadvantages.

With technology and computers getting smarter and faster every day, even the brute-force method seems feasible.

But with space and time complexity, many companies, such as Reddit, prefer Binary search, whereas some others, such as Medium, use Bloom filters smartly to suggest articles for you without repeating them again on your timeline.

Register now before your username is taken on the HackerEarth platform.

“What is imagination?…It is a God-like, a noble faculty. It renders earth tolerable; it teaches us to live, in the tone of the eternal.” – Ada Lovelace to Charles Babbage

When Charles Babbage, in 1837, proposed a ”Fully programmable machine” which would be later called an Analytical engine, not even the government who seed-funded his Difference Engine believed him.

Undoubtedly the most influential machine in existence in today’s modern computer.

But back in the 19th century, when the world was drooling over the industrial revolution and railway tracks and steam engines, a machine which could think and calculate looked like a distant dream.

While most see the evolution of these advanced machines such as computers and smartphones as examples of electronic innovation, what people have taken for granted had been an evolution and the hard work of transforming a mechanical device into a self-thinking smart device which would become an integral part of our lives.

Charles Babbage – The father of the computer

In the 19th century, the concept of specialization had not breached the revered halls of universities and laboratories.

Most of the geniuses were polymaths, so was the Englishman Charles Babbage. Charles Babbage was a renowned mathematician, philosopher, and mechanical engineer of his times.

During those days, mathematical tables (such as your logbook) were manually made and were used in navigation, science, and engineering.

Since most of these tables were manually updated and calculated, the values in these tables varied frequently, giving inconsistent results during studies.

While at Cambridge, Charles Babbage noticed this flaw and thought of converting this mathematical-table based calculation into a mechanical product to avoid any discrepancies.

Difference Engine

In 1822, Charles Babbage decided to make a machine to calculate the polynomial function—a machine which would calculate the value automatically.

In 1823, the British government gave Charles Babbage £1700 (probably the first ever seed funding).

He named it the Difference Engine, possibly after the finite difference method is used to calculate.

Charles Babbage invited Joseph Clement to design his ambitious massive difference engine that had about 25,000 parts, weighed around 15 tons, and was 8 feet tall.

Despite the ample funding by the government, the engine never got completed. And in the late 1840s, he planned on making an improved engine.

But that was not completed either due to lack of funds.

In 1989–1991, scientists and engineers studying Charles Babbage’s research paper built the first difference engine, which is now placed in The Museum of the History of Science, Oxford.

How Does Charles Babbage’s Difference Engine work?

Wikipedia says: “A difference engine is an automatic mechanical calculator designed to tabulate polynomial functions.

The name derives from the method of divided differences, a way to interpolate or tabulate functions by using a small set of polynomial coefficients.”

Let’s take an example with a polynomial function R = x² + 1

To solve this manually, you need to solve the equation “n+1” times, where n is the polynomial. So, for the given equation, we need threesteps.

When X = 0, result of R = 1; X= 1, R =2; X=2, R= 5, and so on.

Difference 1 : D11 = R2 (Step 2) – R1 (Step 1) or D12 (Step 2) = R3 (Step 3) – R2 ( Step 2) and so on

So for the Difference 1 column in the table above,

D11 = 2 (R2) – 1(R1) = 1

D12 = 5 (R3) – 2(R2) = 3

D13 = 10 (R4) – 5(R3) = 5

Difference 2 : D21 = D12 (Difference 1 -Step 2) – D11( Difference 1- Step 1), and so on.

By subtracting two consecutive values from the Difference 1 column,

D21 = 3 (D12) – 1(D11) = 2

D22 = 5 (D13) – 3 (D12) = 2

Similarly, for a third-order equation, we can prepare a new column called Difference 3, and calculate it by subtracting two consecutive numbers from the last column.

*The values in the last column or the highest power value always remain constant in the last difference column.*

Since the engine could only add and subtract, some of the values from each column are given to the difference engine to feed the engine with information necessary for further calculations.

Working of a difference engine

Let’s take another example where you have to calculate the result for x = 3 from the above equation (R = x² + 1), and the engine was already given the values of Step 1 and Step 2 columns (Refer to above table). The engine would follow the following steps:

Step 1: To calculate the value for D12, Step 1 difference 2 is added to Step 1 Difference 1, which is 2(D21) +1( D11)=3.

Step 2: This D12 when added with R2, which gives the result for Step 3 = 3 (D12) + 2( R2) = 5

Similarly, to calculate the result for x = 4

Step 1 – For X = 4, Step 2 – Difference 2 added to Difference 1 = 2 (D22) +1 (D12) = 5

Step 2 – Add value from Step 1 to Step 3 result R3, which is 5+5, giving the final value as 10

A difference engine (shown above) consisted of N+1 columns, where column N could only store constants and Column 1 showed the value of the current iteration.

And the machine was only capable of adding values from column n+1 to N.

The engine is programmed by setting initial values to the columns. Column 1 is set to the value of the polynomial at the start of computation.

Column 2 is set to a value derived from the first and higher derivatives of the polynomial at the same value of X.

Each column from 3 to N is set to a value derived from the first-order derivative. To simplify what the difference engine did, here is a simple code for Polynomial Function calculation using C++ –

#include <iostream>
#include <math.h>
using namespace std;

int d; // degree of the polynomial
int i; // 
int c; // 
int value; 
int j;
int p;
int sum;



int main()
{
    cout << "Enter the degree of the polynomial: " << endl;
    cin >> d; // degree of the polynomial
    cout << "The degree of the polynomial you entered was " << d << endl;

    
    int *c = new int[i];
    
    for(i = 0; i <= d; i++)
    {
        cout << "Enter coefficients: " << endl;
        cin >> c[i];
        int c[d+1];

    }
    
        cout << "There are " << d + 1 << " coefficients";
        cout << " The coefficients are: ";
        
        for (i = 0; i < d + 1; i++)
        cout << "\n   " << c[i];
        cout << endl;
        
        cout << " Enter the value for evaluating the polynomials" << endl;
        cin >> value;
        sum = 0;
        cout << " The value is " << value << endl;
        
        cout << "First polynomial is: " << endl;
        cout << c[0] << "x^3 + " << c[1] << "x^2 + " << c[2] << "x + " << c[3] << endl;
        {

            for (i = 0; i <= d; i++)
            p = 1;
            {


                for (j = 0; j <= (d - 1); j++)
                p = p * value;
                sum = sum + p;
                sum = pow(c[0]*value,d)+pow(c[1]*value,d-1)+pow(c[2]*value,d-2)+pow(c[3]*value,d-3);
                
                cout << "The sum is " << sum << endl;
            }
            
        }
             
}

The difference engine was never finished, and during its construction, Charles Babbage had a brilliant idea of using Punch Cards for calculation.

Till then, punch cards that had been used only for the mundane job of weaving would form the basis of future computer programming.

Punch Cards

Before Joseph Jacquard came up with the idea of punch cards, the weaving was done using draw looms. A drawloom generally used a “figure harness” to control the weaving pattern.

The drawloom required two operators to control the machine.

Although till 1801, punch cards were only used for individual weaving, Jacquard decided to use perforated papers with the mechanism, because he found that though being intricate, weaving was mechanical and repetitive.

Working

In the most basic form, a weaving design is made by passing onethread over another.

In a patterned weave, the threads crossing each other are not synchronized by equal blocks but are changed according to the required pattern.

A weaver controls the threads by pulling and releasing them.

When Joseph Jacquard came up with the idea of a loom, the fabric design in it was first copied on square papers.

This design on the square was translated into punch cards. These cards are stitched together in a continuous belt and fed into the loom.

The holes in the card controlled which threads are raised into the weaving pattern.

This automation allowed Jacquard to make designs and produce them again at lesser costs. Keeping this bunch of cards helped to reproduce the same design repeatedly with perfection on the same or another machine.

“Visualizing” the concept of using these punch cards to calculate, Charles Babbage described using them for the analytical engine.

In 1883, Charles Babbage was introduced to ayoung brilliant mathematician, Ada, who later became Countess of Lovelace, byher tutor.

He was impressed with Ada’sanalytical skills and invited her to look the difference engine, which fascinated her.

This formed the basis of a lasting friendship that continued until her death.

Ada Lovelace – The first programmer

Born to British poet Lord Byron and Annabella Milbanke, Augusta Ada Byron married William King-Noel, who was the first Earl of Lovelace.

Ada was a natural poet who found mathematics poetic.

Growing up, Ada’s education and her families’ influential presence got her in touch with a few prestigious innovators and literary figures of her time.

While studying mathematics, her tutor Mary Somerville introduced her to Charles Babbage, who, after his work on the unsuccessful Difference Engine, was working on an ambitious project of a machine which could solve any complex mathematical function (the Analytical Engine).

What you see below is a caricature image of the Analytical Engine as proposed by Charles Babbage.

The important parts of this engine still constitute our modern computers.

Part 1 – The Store, was what we now call Hard disk or memory

Part 2 – The Mill, was what we now call Central Processing Unit (Mill where the churning or production is done)

Part 3 – Steam engine, which would be the source of energy

Ada, impressed by the theory and concept of the Analytical Engine, decided to work with Charles Babbage onthe construction of the engine.

During her study of the Analytical Engine, she wrote a series of notes which explained the difference between a Difference Engine and an Analytical Engine.

She took up Bernoulli number theory and built a detailed algorithm on the process of calculating Bernoulli numbers using an Analytical engine which was demonstrated in Note G of her article shown below.

This made her the first programmer in the world. (This is disputed.)

Though her notes were never accepted, and as there was no funding or investment to back Charles Babbage’s fantastic idea, the analytical engine was never completed.

Here is a simple C++ program to the algorithm developed by Ada Lovelace in her lengthy notes:

// bernoulli_distribution
#include <iostream>
#include <random>

int main()
{
  const int nrolls=10000;

  std::default_random_engine generator;
  std::bernoulli_distribution distribution(0.5);

  int count=0;  // count number of trues

  for (int i=0; i<nrolls; ++i) if (distribution(generator)) ++count;

  std::cout << "bernoulli_distribution (0.5) x 10000:" << std::endl;
  std::cout << "true:  " << count << std::endl;
  std::cout << "false: " << nrolls-count << std::endl;

  return 0;

Charles Babbage declined both the title of Knighthood and baronetcy and instead asked for a life peerage, but that wish wasn’t granted in his lifetime.

He died in 1871 ate the age of 79. Ada Lovelace died at the young age of 36 in 1852.

Her contribution to computer science for having come up with the “first” algorithm still remains one of the greatest controversies in technology history.

You can read one such article here.

Irrespective of these facts, their contribution to the field of computer and programming cannot be ignored.

A super calculator which would be able to solve any mathematical problem and a device which would have the ability to think of ways to approach a problem is what Charles Babbage and Ada Lovelace thought of; this was the founding stone of the first programmable computer.

In the next article, we will discuss the use of Punch Cards and how with all technological developments in Europe, the USA got the first computer!

Do you know SixDegrees.com was the first social network site which allowed the user to create a profile and connect?

In a world of 7 billion people, it seems hard to believe that the Six Degrees of Separation theory contends that we are all connected to each other by six or fewer acquaintances.

For example, there are, at most, six people standing between you and Tom Cruise or President Obama (or Trump if you lean that way).

Going by the numbers, the idea looks pretty plausible.

Assume that you know 50 people or have 50 friends and these 50 friends of yours know 50 others who are not your friends, and so on.

The math says that in 6 steps you would be connected with 50⁶, or 15.62 billion people.

Six Degrees of Separation Theory

In 1929, Hungarian author Frigyes Karinthy published a volume of short stories named Everything is Different.

In one of his stories titled Chains, he said that with growing communication and travel, the friendship network would grow irrespective of the distance between two humans.

And with a growing social network, the social distance would shrink immensely.

All the people on the planet could be connected to one another by 5 or fewer people.

This theory captivated millions of mathematicians, sociologists, and physicists and also laid the founding stone of the first online social network.

Soon several “small world” projects were conducted.

The small world experiment comprised experiments conducted by Stanley Milgram, examining the average path length for social networks of people in the United States.

These experiments suggested that humans are connected to each other through a network, connected to each other by the shortest path.

In 2005, Samy Kamkar wrote a small piece of code for his myspace account.

Whenever anyone visited Samy’s profile, it copied his picture and tag line on his home page saying “Samy is my hero” and also copied the code.

Within 20 hours, this code was on more than 1 million myspace user profiles. It is considered one of the fastest growing web viruses of all time.

Though mostly harmless, Samy was caught by the United States Secret Service and was prohibited from using the Internet for three years.

The point I am trying to make is that within a span of few hours, a simple XSS webworm was shared among more than 1 million users, proving that the world was getting smaller and further studies and research on small world projects need to be escalated.

The real breakthrough came with the college game of “Six degrees of Kevin Bacon” where college students linked other Hollywood co-stars to Kevin Bacon in six or fewer steps.

The huge volume of data collected in the game gave scientists and researchers immense information to process and proceed and gave them opportunities to prove the concept of six degrees of separation.

In 2011, Facebook and researchers at Cornell computed that the average separation across 721 million people using Facebook was only 3.74.

In their latest research published in February 2016, this number dropped down to 3.57, with more than 1.59 billion people active on Facebook.

On average, Facebook users are connected by an average of 2.9 to 4.2 degrees of separation. The image shows the average of each person.

Six Degrees of Separation Theory meaning analysis

Suppose you assign an integer called Hash to each friend in a group (Read more about Hash Function here).

Approximately half of your friends will have even numbers or even hash, whose binary representation would be 0.

A quarter of them would have the number divisible by 4, giving the binary representation as 00. This means ½ⁿ people will have their hash or numbers ending with n zeros.

To track, you find the number with the maximum number of zeros. If there are n zeros, you can find C*2ⁿ unique numbers.

To calculate the average, you find the number with the maximum number of zeroes.

Use Bitwise OR operation on these numbers and then recursively do it for one set of friends, and then friends-of-friends, and their friends and so on to find the shortest path.

The result is amazing! It is just unbelievable how small the world is.

With a growing social network, the average separation and connection would soon reduce to possibly 2 to 3 degrees of separation.

And someday, a mail from The Prince of Somalia telling you that you have won the lottery might be actually true!

Till then, connect with best developers across the planet using first degree connections by building your profile on HackerEarth and participating in various programming challenges.

Most of the cable network companies use the Disjoint Set Union data structure in Kruskal’s algorithm to find the shortest path to lay cables across a city or group of cities.

Which leads us to this post onthe properties of Disjoint sets union and minimum spanning tree along with their example.

Before we proceed with an example of Kruskal’s algorithm, let’s first understand what disjoint sets are.

What are Disjoint Sets?

A disjoint set is a data structure which keeps track of all elements thatare separated by a number of disjoint (not connected) subsets.

With the help of disjoints sets, you can keep a track of the existence of elements in a particular group.

Let’s say there are 6 elements A, B, C, D, E, and F. B, C, and D are connected and Eand F arepaired together.

This gives us 3 subsets that haveelements (A), (B, C, D), and (E, F).

Disjoint sets help us quickly determine which elements are connected and close and tounite twocomponents into asingle entity.

A disjoint set data structure consists of twoimportant functions:

Find() – It helps to determine which subset a particular element belongs to.

It also helps determine if the element is in more than one subset.

Union() – It helps to check whether a graph is cyclic or not. And helps connect or join two subsets.

Implementation of Disjoint Set

For the previous example, we assumethat for the set (B, C, D), B is a parent node.

For the disjoint set, we keep a single representative for each node.

If we search for an element in a particular node, it leads us to the parent of that particular node.

Therefore, when you search for D, the answer would be B.

Similarly, we can connect the subset (A) to (E, F ) which would result in node Aas the parent node.

Now we have twosubsets, but both B and A don’t have any parent node.

Each tree is an independent disjoint set, that is if twoor more elements are in the same tree, they are part of the same disjoint set, else they are independent.

So if for a particular tree B is a representative, then Parent[i]=B.

If B is not a representative, we can move up the tree to find the parent or representative for the tree.

You can read more here about Basics of Disjoint sets.

What is Kruskal’s algorithm?

Spanning tree is the sum of weights of all the edges in a tree.

A minimum spanning tree (MST) is one which costs the least amongall spanning trees.

Here is an example of aminimum spanning tree.

Kruskal’s Algorithm and Prim’s minimum spanning tree algorithm are two popular algorithms to find the minimum spanning trees.

Kruskal’s algorithm uses the greedy approach for finding a minimum spanning tree.

Kruskal’s algorithm treats every node as an independent tree and connects one with another only if it has the lowest cost compared to all other options available.

Step to Kruskal’s algorithm:

• Sort the graph edges with respect to their weights.
• Start adding edges to the minimum spanning tree from the edge with the smallest weight until the edge of the largest weight.
• Only add edges which don’t form a cycle—edges which connect only disconnected components.

Or as a simpler explanation,

Step 1 – Remove all loops and parallel edges

Step 2 – Arrange all the edges in ascending order of cost

Step 3 – Add edges with least weight

But how do you check whether twovertices are connected or not? That’s where the real-life example of Disjoint Sets come into use.

Kruskal’s algorithm example in detail

I am sure very few of you would be working for acable network company, so let’s make the Kruskal’s minimum spanning tree algorithm problem more relatable.

On your trip to Venice, you plan to visit all the important world heritage sites but are short on time. To make your itinerary work,you decide to use Kruskal’s algorithm using disjoint sets.

Here is amap of Venice.

Let’s simplify the map by converting it into a graph as below and naming important locations on the map with lettersand distance in meters (x 100).

Let’s understand how Kruskal’s algorithm is used in the real-world example using the above map.

Step 1- Remove all loops and parallel edges

So for the given map, we have a parallel edge running between Madonna dell’Orto (D) to St. Mark Basilica (J), which is of length 2.4kms(2400mts).

We will remove the parallel road and keep the 1.8km (1800m) length for representation.

Step 2 – Arrange all the edges on the graph in ascending order. Kruskal’s algorithm considers each group as a tree and applies disjoint sets to check how many of the vertices arepart of other trees.

Step 3 –Add edges with least weight; we begin with the edges with least weight/cost. Hence, B, C is connected first considering their edge cost only 1.

I, J has cost 1; it is the edge connected next.

Then, we connect edges with weight = 2.

Similarly, we connect node K, Lwhich has an edge with weight = 3.

As given in the table above, all the edges are connected in ascending order, ensuring no loop or cycle is formed between 2 vertices.

Thisgives us the following graph, which is the minimum spanning tree forthe given problem.

Here Kruskal’s algorithm using C++

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;
const int MAX = 1e4 + 5;
int id[MAX], nodes, edges;
pair <long long, pair<int, int> > p[MAX];

void initialize()
{
    for(int i = 0;i < MAX;++i)
        id[i] = i;
}

int root(int x)
{
    while(id[x] != x)
    {
        id[x] = id[id[x]];
        x = id[x];
    }
    return x;
}

void union1(int x, int y)
{
    int p = root(x);
    int q = root(y);
    id[p] = id[q];
}

long long kruskal(pair<long long, pair<int, int> > p[])
{
    int x, y;
    long long cost, minimumCost = 0;
    for(int i = 0;i < edges;++i)
    {
        // Selecting edges one by one in increasing order from the beginning
        x = p[i].second.first;
        y = p[i].second.second;
        cost = p[i].first;
        // Check if the selected edge is creating a cycle or not
        if(root(x) != root(y))
        {
            minimumCost += cost;
            union1(x, y);
        }    
    }
    return minimumCost;
}

int main()
{
    int x, y;
    long long weight, cost, minimumCost;
    initialize();
    cin >> nodes >> edges;
    for(int i = 0;i < edges;++i)
    {
        cin >> x >> y >> weight;
        p[i] = make_pair(weight, make_pair(x, y));
    }
    // Sort the edges in the ascending order
    sort(p, p + edges);
    minimumCost = kruskal(p);
    cout << minimumCost << endl;
    return 0;
}

After understanding how Kruskal’s algorithm works, it’s important to understand the difference between MST and TSP.

Minimum Spanning Tree vs. Traveling Salesman problem

A minimum spanning tree helps you build a tree which connects all nodes, or as in the case above, all the places/cities with minimum total weight.

Whereas, a traveling salesman problem (TSP) requires you to visit all the places while coming back to your starting node with minimum total weight.

Following are some of the other real-life applications ofKruskal’s algorithm:

1. Landing Cables
2. TV Network
3. Tour Operations

If you understood the example and working with disjoint sets, you are all set to join the CodeMonk challenge on the Disjoint Sets Union.