Algorithms

Shawn — Sun, 26 Sep 2021 21:06:11 +0000

What is an algorithm?

We all hear algorithm so often when doing a simple multiplication or a complicated calculus problem, but what does algorithm mean exactly?

The word algorithm itself originally comes from Medieval Latin algorismus, and east from Greek arithmos which means “number”. It seems that it is also influenced by the name of the 9th Century Persian mathematician Al-Khwārizmī who wrote about calculations, and when his work was translated into Latin 300 years later, his name was somehow incorporated into the name of the process as Algoritmi. This became confused with the Greek word for number, leading to the evolution of the word as we know it.

In mathematics, logic, computer science and related disciplines, an algorithm is a finite series of defined, computer-implementable and unambiguous instructions or rules that typically allow solving a problem, computing, processing data, automated reasoning and carrying out other tasks or activities.

Interestingly, algorithms are not just used in mathematics and computer science but are also widely used in many aspects in our daily life. For instance, user manuals apply algorithms to guide people to use electrical appliance like a cooker, or a dish washer. At work, an electrical technician can follow the instructions which also are made by algorithms step by step to perform maintenance on a transformer. In other words, algorithm is nothing more than a method of solving a problem or accomplishing things by taking steps.

Algorithms in computer programming

Just as in real life, to get a computer to do a task, we need to write a computer program to tell the computer, step by step, exactly what we want it to accomplish. The computer then reads the program and executes the commands shared in it by following each step mechanically in order to complete the said task. This set of related commands or steps is a computer algorithm.

There are many types of algorithms available in computer science, which means most of the time there are many solutions with different steps of solving a specific problem. Generally speaking, algorithms can be classified into six categories based on their kay features and functionalities.

Greedy algorithm

A greedy algorithm is an algorithmic strategy that makes the best optimal choice at each small stage with the goal of this eventually leading to a globally optimum solution. This means that the algorithm picks the best immediate solution at the moment without regard for consequences, therefore it is considered greedy.

Dynamic Programming algorithm

Dynamic programming algorithm is a technique that breaks complex problems into a collection of multiple simpler sub-problems, and stores the result for future purposes to avoid repetitive computations. The subproblems are optimized to optimize the overall solution which is known as optimal substructure property.

Divide and Conquer algorithm

Divide and Conquer algorithm breaks down a problem into two or more subproblems of the same or related type, recursively solves the subproblems, and finally combines the solutions to the subproblems to solve the original problem. Normally, it follows these three steps:

Divide the problem into a number of subproblems that are smaller instances of the same problem.
Conquer the subproblems by solving them recursively. If they are small enough, solve the subproblems as base cases.
Combine the solutions to the subproblems into the solution for the original problem.

Recursive algorithm

Recursive algorithm is a method of simplification that divides the problem into sub-problems of the same nature. The result of one recursion is the input for the next recursion. The repletion is in the self-similar fashion. The algorithm calls itself with smaller input values and obtains the results by simply performing the operations on these smaller values. Generation of factorial, Fibonacci number series are the examples of recursive algorithms.

Brute Force algorithm

Brute Force algorithm is a trial and error methodology, which is used by attackers to break into any website’s data or systems. They try to steal information by generating every possible combination of the password-protected information. Brute Force relies on the computational power of the machine to try every possible combination to achieve the target.

It is also known as Exhaustive Search or Generate and Test that yields all possible solution of the problem. It is a simple problem solving technique that is easy to implement and will always come up with a solution if exists. The computational cost of Brute Force algorithm is directly proportional to the number of candidate solutions, for example it grows as quickly as the problem size increases. Therefore, it is ideal to use when the problem size is limited and small and does not have complex and large problem sets.

Backtracking algorithm

Backtracking is an algorithmic technique where the goal is to get all solutions to a problem using the brute force approach. It consists of building a set of all the solutions incrementally. Since a problem would have constraints, the solutions that fail to satisfy them will be removed.

It uses recursive calling to find a solution set by building a solution step by step, increasing levels with time. In order to find these solutions, a search tree named state-space tree is used. In a state-space tree, each branch is a variable, and each level represents a solution.

A backtracking algorithm uses the depth-first search method. When it starts exploring the solutions, a bounding function is applied so that the algorithm can check if the so-far built solution satisfies the constraints. If it does, it continues searching. If it doesn’t, the branch would be eliminated, and the algorithm goes back to the level before.

About Myself

Shawn — Tue, 31 Aug 2021 20:44:28 +0000

My name is Shawn, and I have been abroad for 10 years -- 5 years in Japan and 5 years in Canada. In 2013, I went to Toyota Technical College and majored in Automobile Technology. With high grades achieved in school, I acquired Japan Student Services Organization Scholarship on my second semester. After graduation, I became an automobile mechanic and worked at Toyota dealership for 1 year. Then I made a decision to immigrate to Canada, as I had been thinking of immigration during my school years. After 2-year study and working for 3 years in Winnipeg, Manitoba which is another province in Canada, I finally received my Permanent Resident Card early this year and moved to Vancouver -- one of the best cities to live in the world.

In my free time, I like reading, listening to music and watching TV shows -- mostly sitcoms like Friends, The Big Bang Theory and so on. Also I enjoy outside activities, like jogging and hiking. I jog everyday and think it is the one of the best ways to relieve stress and challenge myself by setting up harder goals every time.

I am always looking for volunteer opportunities to be involved in the community. In 2017, I assisted with the greeting and direction of guests at special events at University of Manitoba. Back in 2014, I helped with set-up and serving as well as guest entertainment for special events at Toyota Technical College.

After I worked in Canada for 3 years as a car mechanic, I realized that this kind of jobs is not suitable for me because of the different situations between Japan and Canada. So I decided to change my career after I acquired my permanent residency. Then I did a lot of research and it turns out that programming is one of good choices for people who want to change their career like me. Also I watched a few videos about web development, and found out that I am very interested in it and it is suitable for me as well, since I like solving problems and am always willing to learn new things.

Currently, I just took an online course of HTML and CSS, did a lot of code-along projects and finished halfway through a web development bootcamp on Udemy. Then I realized that I need more practice on Javascript, so I decided to pause the boot camp and jump onto another course which is dedicated to Javascript. Now I am working on that course and hope I could grasp a better understanding of Javascript. Although it is getting more and more difficult while moving forward and sometimes I get stuck, but overcoming that is also kind of fun to me and I believe that I will make it through eventually.

My end goal is to find a job in Vancouver, therefore becoming an independent front-end web developer would be my first objective. Since React developers are in very high demand now, I think I will be spending more time on that part.

DEV Community: Shawn

Algorithms

About Myself