What is Algorithmic Knowledge?
Developers who interview for jobs in tech companies are often flustered that knowledge of algorithms and data structures are questions of interest to interviewers. Some of these non-computer science developers do not understand why emphasis should be made on the algorithm to solve a problem rather than the actual coding they know. It seems irrelevant and a waste of time.
Of recent, there has been unrest that these forms of interviews should be discontinued. But can we do without algorithms and algorithmic knowledge? Why are algorithms so important in computer science and programming?
What is an Algorithm?
Algorithms are considered the ‘heart’ of computer science and programming. We can define algorithms as step-by-step instructions in solving problems. They often follow a logical or sequential path to giving instructions, acting like roadmaps or guides.
Compare an algorithm to a recipe, let us say - pancakes. As in any recipe, we first write down our ingredients:
- One (1) cup all-purpose flour
- Two (2) tablespoons white sugar
- Two (2) teaspoons baking powder
- One (1) teaspoon salt
- One (1) egg, beaten
- One (1) cup milk
- Two (2) tablespoons vegetable oil
Then, we follow with the steps we need to take to mix these ingredients:
STEP 1: Mix flour, sugar, baking powder, and salt in a bowl.
STEP 2: Make a well in the center, and pour all the milk, egg, and oil. Mix until smooth.
STEP 3: Heat a lightly oiled griddle or frying pan over medium-high heat.
STEP 4: Pour or scoop the batter onto the griddle, using approximately 1/4 cup for each pancake. Brown on both sides and serve while hot.
This recipe gives clear instructions on how we prepare pancakes in a precise sequential process. It also has all the features of a good algorithm.
- Concise and Precise: The recipe is straightforward and straight to the point. It only gives instructions on how to prepare a pancake in a step-by-step manner.
- Data and output: Algorithms must work on data; that is why we usually link them to data structures. There must be an input of data and outcome (or result). The ingredients, in this case, are the data, and the pancake is the output.
- Finite: The steps must be limited. It must terminate after all the steps are completed.
- Language: Algorithms are usually written in a natural language and not a programming language. They could also be done graphically in the form of a flowchart.
There is a saying. ‘The journey of a thousand miles begins with a single step’. An algorithm is that step. While following a recipe to prepare pancakes might seem easy, the world of technology today is full of complex computations, machines, and intelligence. We are dealing with artificial intelligence, robots, self-driving cars, smartphones, and virtual assistants. Preparing food is just a basic example that has the engrained logic of algorithms – but they can solve infinitely more complex problems. Building these technologies without clear instructions and procedures and building blocks will be overwhelming and make the task almost impossible.
From a programming point of view, “an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value or set of values as output.” Algorithms must take an input and give an output.
Why knowing algorithms is important
When programmers must solve problems, they do not just start with code. They start with a blueprint and analyze the steps to solve the given situation. An interviewer asking about algorithms is not just testing the algorithmic knowledge of the interviewee, but his problem-solving skills and logical approach to solving a question.
Approach to problem-solving (Types of Algorithms)
Distinct types of problems need different algorithms to solve problems. A suitable Algorithm must be used for each issue at hand to ensure an error-free code.
In a library, books are arranged sequentially, in different sections. The ‘history section’ holds books related to past events, the ‘literature section’ holds classical materials, and so on. This organizational logic makes it easy for a librarian to find any book they might need. Finding a book in a library is a type of problem that uses a sorting or classification algorithm.
Searching for a particular page or note in a paper book takes a different approach. We could go page by page, go to a bookmarked page. We solve this type of problem with a binary search algorithm.
A. Searching algorithms
Search algorithms are designed to find and retrieve a given element in an extensive data collection. Search algorithms further subdivide into linear and sequential (or interval search).
Let us say we must search for a particular word in a dictionary. A linear search would go page by page, not skipping any of the pages until it finds the word. But this is not ideal and takes a lot of time. When we search for words, we look for the first word of the letter. For example, it does not make sense to start the search at ‘A’ for ‘Zebra.’
An interval search, on the other hand, searches at intervals. An example of this is a binary search. A binary search divides the array in half repeatedly.
Here is an algorithm for a word search using binary search.
Step 1: Divide the dictionary into two parts
Step 2: Compare the first letter of the word with the middle element
Step 3: If the letter matches the central part, return the middle index.
Step 4: If the letter is not in the middle index, check lower or higher than the mid index.
Step 5: If lower than the mid index, check the left subarray and divide it in half.
Step 6: Else, if it is higher than the mid index, check the right subarray and divide it into half.
Step 7: Repeat the process until you find the letter.
B. Sorting algorithms
This kind of algorithm sorts through a collection of data, re-organizing and arranging them into specific orders. It could be from highest-to-lowest, longest-to-shortest, ascending, or descending orders, numerical or alphabetical.
Searching and sorting algorithms usually use arrays or lists, which are popular data types.
C. Compression Algorithms
Compression algorithms compress files without losing its information, format, and quality.
- Compression algorithms reduce the size of data and program files to facilitate efficient exchange over networks.
- We use compression algorithms to compress audio, images, and video. Subclassification of compression algorithms used on media files can be lossy or lossless compression.
Unlike other algorithms with outputs, compression algorithms do not have a finite output. Instead, it optimizes the result, ensuring it uses as few bytes as possible (Optimization of Size).
D. Graph Transversal Algorithms
Graph transversal algorithms involve checking the nodes or vertices in a graph. We can transverse graphs using a breadth-first search or depth-first search.
An excellent example of graph transversal algorithms is searching for a person who is a friend or follower of another person on social media networks like Facebook or Twitter. The connection of people on social media resembles a graph-like network. A person might be a follower or friend of one person, have mutuals with that person, and have friends who are not followers.
A breadth-first search method is an excellent way to do this search. A breadth-first search finds the shortest path in a graph. No node is visited twice.
First, we treat each person as a node; then, we find the adjacent path that leads to another person, exploring all the other nodes nearby.
Step 1: initialize the search at A. Mark it as visited.
Step 2: Visit adjacent nodes of B and C. Enqueue them. A no longer has any unvisited nodes, so we move to B and dequeue A.
Step 3: From B, we visit F
Step 4: Move to C, mark it as visited, and enqueue it.
Step 5: The adjacent nodes to C are D, E, and G.
Step 6: We move to D and E, mark them as visited, and enqueue them.
Step 7: From E, we move to G
Step 8: All nodes are visited and enqueued.
Step 9: The program ends
Algorithms like Dijkstra are complex algorithms used to find the shortest path between nodes in a road-like network. Google maps are using it to compute directions and calculate distances from one point to another.
E. Fast-Fourier Transform Algorithm
A fast Fourier transform is an algorithm that computes the discrete Fourier sequence transform or its inverse. It is used extensively for digital signal processing (DSP).
F. Encoding Algorithm
Encoding algorithms encrypt, decrypt, scramble and decipher data or text using special keys.
G. Geometric Algorithm
These algorithms study or identify geometric shapes.
H. Parsing Algorithm
This algorithm transforms data so a specific software can understand it. Parsing We use algorithms to identify different programming constructs by computer programs.
I. Pattern-Matching Algorithm
Pattern-matching algorithms compare images and shapes.
J. Pattern-searching Algorithm
These are also called string searching algorithms. Pattern-searching algorithms search and compare strings within other strings.
Time complexity and memory optimization
Time complexity is an essential factor in writing algorithms. It is closely related to the time it takes a program to run. If the algorithm takes too long to execute a program, then it is not good enough.
Varied factors like space complexity (which quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input). The size of the input influences the time complexity of a program
Time complexity is calculated by time as a function of the length of the input, the input data size (n), and the number of operations performed (N) concerning time.
There are several types of time complexities used; they include:
- Constant time – O (1)
- Linear time – O (n)
- Logarithmic time – O (log n)
- Quadratic time – O (n^2)
- Cubic time – O (n^3) etc
Time complexity also calculates the worst-case runtime, average-case runtime, and best-case runtime scenarios. The worst-case runtime measures how long an algorithm takes to execute given impossible inputs of arbitrary size. The Big O notation denotes it. Big O notation provides us with an asymptotic upper bound for the growth rate of the runtime of an algorithm.
The average-case runtime measures how long an algorithm executes given ‘normal’ or ‘average inputs.’ It is estimated and calculated using the big Theta notation.
The best-case runtime calculates how long an algorithm executes given the best possible inputs. The omega notation measures it. Of the three runtimes, the worst-case runtime algorithm is frequently used as a yardstick to test execution speed.
There are separate ways to solve a particular problem. But not every solution is the right one. The right tools to make a programming job manageable. Algorithms are a handy computing tool for problem-solving, especially for grand issues. The average computer has different components (hardware and software) that must be taken into consideration.
When writing a program, accuracy, speed, memory consumption, processor/CPU power, and time usage are crucial factors. Good algorithmic knowledge is required to choose the best possible algorithm to solve a particular problem.
The suitable algorithm will ensure that all computer resources are perfectly utilized, eliminating unnecessary computer assets that only add burden and strain to the computer and processing power. Algorithmic knowledge produces efficient software.
Companies continually seek new ways to implement ideas, stay ahead of the competition, save time, maintain servers, and increase revenue. They spend more time designing optimal algorithms before the actual coding to handle many users while preserving their resources. They are also on the outlook for programmers who can help them achieve this goal.
Computers and programming have evolved in many ways, yet the hardware and software resources are still limited. Use them wisely.
The frameworks we learn today do not mandate algorithms, but knowledge of algorithms differentiates a skilled developer from an unskilled one
Using the proper algorithm method can be the difference between good and bad software. A computer scientist needs the knowledge of different algorithms to employ the best one when required.