Algorithm - GATE CSE Notes

An algorithm is a technique that specifies a series of instructions that must be followed in a precise order to obtain the desired conclusion. Algorithms have the advantage of being able to be executed in numerous programming languages. In this article, we will learn more about the algorithm and its special pointers.

Table of Contents

• Important Pointers Related to Algorithm
• Videos on Algorithm
• Characteristics of an Algorithm
• Why are Algorithms Required?
• How to Write an Algorithm?
• Aspects of an Algorithm
• Approaches of an Algorithm
• Practice Problems

Important Pointers Related to Algorithm

• An algorithm is a set of orders and commands followed by a computer to decode problems and perform several tasks.
• An algorithm is not a programming code; it is a flowchart or pseudocode. In short, it is like a step-by-step procedure.
• After creating an algorithm, it is provided with the required and expected inputs.
• The outcome of the program is known as the output.

Videos on Algorithm

Characteristics of an Algorithm

• An ideal algorithm is represented as specific, that means that its instructions must be clear and straightforward.
• An algorithm should be finite, which means it should have a fixed number of steps or instructions that we can easily count.
• Because each guideline in an algorithm affects the whole procedure, it should be effective.
• When it comes to the programming world, we have a variety of languages. So, an algorithm needs to be language-independent. In short, the instructions of an algorithm can be executed in any language and deliver the exact outcomes.

Why are Algorithms Required?

• In the field of computer science, an algorithm is a crucial component that allows us to efficiently solve a problem. There are numerous reasons why we require algorithms. Let’s look at a few of the reasons:
  • It will help you grasp the concept of scalability. You must break down a large real-world problem into small segments in order to examine it quickly.
  • It implies that a problem is feasible if it can be easily split into smaller steps.

How to Write an Algorithm?

• When it comes to constructing the algorithms, there are no particular standards. All we need to keep in mind is that the algorithm is a step-by-step instruction that we use to solve the problem. Also, it should not be language-specific.
• Although most algorithms are written step by step, that isn’t always the scenario. When it comes to writing an algorithm, first, we need to understand the issue domain for which a solution is being developed.

Aspects of an Algorithm

• Correctness: We can determine the correctness of the algorithm at the time of output generation. Yes, when the input produces the output, that time we can estimate its accuracy.
• Modularity: When talking about algorithms, modularity is one of the most important features. We can say it is meant for algorithms only because, in algorithms, we need to break down the problems into smaller modules. In short, we can say that it is the basic necessity of algorithms.
• Functionality: It is an important factor that we need to consider. Algorithms include multiple steps in order to logical phases to solve a problem.
• Validity: Validity means the ability of an algorithm to specify the problem.
• Maintainability: This means that the method should be written in a clear, structured manner so that when it is redefined, no significant modifications are made.
• Simplicity: An algorithm should be uncomplicated and straightforward so that everyone can easily understand it.
• Extensibility: This is, again, a very important factor an algorithm should have. If another algorithm designer or programmer wants to utilise your algorithm, it should be extensible.

Approaches of an Algorithm

• Insertion Sort Algorithm
• Selection Sort Algorithm
• Heap Sort Algorithm
• Quick Sort Algorithm
• Merge Sort Algorithm
• Greedy Algorithm
• Binary Search Algorithm
• Breadth-First Search
• Depth-First Search
• Recursive Algorithm
• Divide and Conquer Algorithm

Backtracking Algorithm

Brute Force

• Dynamic Programming Algorithms

Practice Problems

Q1. Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?

1. Quicksort runs in time
2. Bubble Sort runs in time
3. Mergesort runs in time
4. Insertion sort runs in time

A) I and II only

B) I and III only

C) II and IV only

D) I and IV only

Q2. The worst-case running times of Insertion sort, Merge sort and Quicksort, respectively, are:

Q3. Consider the following array.

Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?

A) Insertion sort

B) Selection sort

C) Quicksort using the last element as a pivot

D) Merge sort

Q4. Which of the following statement(s) is/are correct regarding the Bellman-Ford shortest path algorithm?

P: Always find a negative weighted cycle if one exist s.

Q: Finds whether any negative weighted cycle is reachable from the source.

A) P Only

B) Q Only

C) Both P and Q

D) Neither P nor Q

Q5. If one uses a straight two-way merge sort algorithm to sort the following elements in ascending order 20, 47, 15, 8, 9, 4, 40, 30, 12, 17, then the order of these elements after the second pass of the algorithm is ___________.

A) 8,9,15, 20,47, 4,12,17, 30, 40

B) 8,15, 20.47.4.9.30 40,12,17

C) 15, 20, 47 4.8.9.12.30 40, 17

D) 4,8,9,15, 20,47, 12.17,30, 40

Q6. Let G(V, E) be a directed graph, where V = {1, 2, 3, 4, 5} is the set of vertices and E is the set of directed edges, as defined by the following adjacency matrix A.

A[i][j] = 1 indicates a directed edge from node i to node j. A directed spanning tree of G, rooted at r

∈

V, is defined as a subgraph T of G such that the undirected version of T is a tree, and T contains a directed path from r to every other vertex in V. The number of such directed spanning trees rooted at vertex 5 is _____________.

Your Input ________.

Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus for CSE (Computer Science Engineering), GATE CSE Notes, GATE CSE Question Paper, and more.