Table of contents
DAY 1 - 19|09|202
I have embarked on a journey to prepare for a coding interview and I plan to land a Software Engineering role in the next 6 months. I started learning Data Structures and Algorithms in August 2022. I covered topics like Arrays, String, Stack, Queues, Recursion, Trees, Dynamic Programming and Graphs over the last year. It is now time for me to revise everything in the next 6 months and hit the job market.
It is Day 1 of preparation today and I wanna begin with Algorithmic Problem Solving. I will consistently write a blog about concepts and approaches I will use to solve data structures and algorithmic problems. On that note, let's get started.
We are talking about Algorithmic Problem Solving therefore we must understand what an algorithm is.
An unambiguous and finite set of instructions that we give to a computer in a specific sequence to produce an output in a finite amount of time is called an algorithm.
In simple words, an algorithm is a step-by-step procedure for solving a problem. Let me illustrate the notion of algorithms with a diagram.
We have a problem on our hands. We design an algorithm to solve the problem. After that, we prove the correctness of the algorithm. Then we implement an algorithm using a certain programming language like C++, Java, Javascript, etc. and execute it in the computer. The computer gives us an output. The diagram above gives a general idea of algorithmic problem-solving, we will get into the specific details as we move forward. But before we move forward it is essential to understand the properties of an algorithm.
Properties of an algorithm
1. Unambiguous: An algorithm must be unambiguous. It should be clear and concise.
2. Input: An algorithm can take zero or more inputs
3. Output: An algorithm should generate at least one output
4. FInite: An algorithm should be finite. It should terminate.
Since we have already discussed algorithms, it is now time for us to jump into algorithmic problem-solving. We will explore different steps involved in algorithmic problem-solving and also delve deep into each step.
Understand the problem: It is super important to analyze the problem before jumping into the solution. We have to think about all the edge cases and constraints. We must study the nature of the problem. We must ask clarifying questions.
Decision Making: We have to decide on the following things
a. On what computational device the algorithm will be running? It is essential to understand the computational capabilities of the device. From an execution point of view, we have two different algorithms; sequential algorithm and parallel algorithm.
b. If we are trying to solve exactly or approximately? The next important decision to make is to solve the problem exactly or approximately. Some complex problems cannot be solved exactly so we solve them approximation algorithm.
c. Data Structures? We have to choose what data structures we need to design our algorithm. This is the phase where our deep understanding of data structures comes into use. We have to learn linear and non-linear data structures and their limitations to make better decisions.
d. What algorithmic technique do we use? Algorithmic techniques are also called algorithmic strategies or algorithmic paradigms. You might have probably heard of words like Bruteforce, Dynamic Programming, Greedy Approach, Backtracking, Branch and Bound, Divide and Conquer, etc. They are not algorithms. They are algorithmic techniques that we use to design an algorithm. We have to choose the best technique to design our algorithm.
Design an algorithm: Finally, we reach a point where after analyzing the problem and deciding on various decisions like what data structures to use and what algorithmic technique to use we start designing our algorithm.
Prove the correctness of the algorithm: Once we have our algorithm designed we prove its correctness. There are multiple ways to prove the correctness of our algorithms. We will not get into the specific details here. But I do wanna tell you is that-the most common method we use to prove correctness is Mathematical Induction.
Analyze the algorithm: Finally, once we have a correct algorithm with us, we analyze the efficiency of our algorithm. We generally consider the time complexity and space complexity. We will get into the specific details of time and space complexity once I start revising them. Our goal is to write the most efficient algorithm time-wise and space-wise.
Code the algorithm: The last step is coding the algorithm. It is the phase where our understanding of programming languages like Java, C++, Javascript and Python comes into use.
That's a wrap for today. I will write more about more concepts in DSA as we move forward.