problem solving algorithm representation

What is Problem Solving Algorithm?, Steps, Representation

What is problem solving algorithm.

Computers are used for solving various day-to-day problems and thus problem solving is an essential skill that a computer science student should know. It is pertinent to mention that computers themselves cannot solve a problem. Precise step-by-step instructions should be given by us to solve the problem.

Thus, problem solving is the process of identifying a problem, developing an algorithm for the identified problem and finally implementing the algorithm to develop a computer program.

Definition of Problem Solving Algorithm

[su_quote cite=””]Algorithms are the solutions to computational problems. They define a method that uses the input to a problem in order to produce the correct output. A computational problem can have many solutions.[/su_quote]

[su_quote cite=””]Algorithms have a definite beginning and a definite end, and a finite number of steps. A good algorithm, which is precise, unique and finite, receives input and produces an output.[/su_quote]

Steps for Problem Solving

Problem solving begins with the precise identification of the problem and ends with a complete working solution in terms of a program or software. Key steps required for solving a problem using a computer.

Analysing the Problem

It is important to clearly understand a problem before we begin to find the solution for it. If we are not clear as to what is to be solved, we may end up developing a program which may not solve our purpose.

Developing an Algorithm

We start with a tentative solution plan and keep on refining the algorithm until the algorithm is able to capture all the aspects of the desired solution. For a given problem, more than one algorithm is possible and we have to select the most suitable solution.

Testing and Debugging

Software industry follows standardised testing methods like unit or component testing, integration testing, system testing, and acceptance testing while developing complex applications. This is to ensure that the software meets all the business and technical requirements and works as expected.

Representation of Algorithms

Using their algorithmic thinking skills, the software designers or programmers analyse the problem and identify the logical steps that need to be followed to reach a solution. Once the steps are identified, the need is to write down these steps along with the required input and desired output.

A flow chart is a step by step diagrammatic representation of the logic paths to solve a given problem. Or A flowchart is visual or graphical representation of an algorithm .

Advantages of Flowcharts:

Differences between algorithm and flowchart.

Pseudo code

In pseudo code , the program is represented in terms of words and phrases, but the syntax of program is not strictly followed.

Advantages of Pseudocode

You might also like, data representation in computer: number systems, characters, audio, image and video, data and information: definition, characteristics, types, channels, approaches, what is cloud computing classification, characteristics, principles, types of cloud providers, advantages and disadvantages of operating system, 10 types of computers | history of computers, advantages, what is debugging types of errors, what is big data characteristics, tools, types, internet of things (iot), types of computer memory, characteristics, primary memory, secondary memory, what is artificial intelligence functions, 6 benefits, applications of ai, generations of computer first to fifth, classification, characteristics, features, examples, what is microprocessor evolution of microprocessor, types, features, types of storage devices, advantages, examples, what are data types in c++ types, what are decision making statements in c types, what are c++ keywords set of 59 keywords in c ++, what are functions of operating system 6 functions, what is operating system functions, types, types of user interface, types of computer software: systems software, application software, what is flowchart in programming symbols, advantages, preparation, what is c++ programming language c++ character set, c++ tokens, leave a reply cancel reply.

Lesson 1: Algorithm definition and representation

Algorithms is a main topic in programming and Computer Science. In this lesson you will learn the definition of algorithm, how to represent them using natural language, pseudo-code and flow diagrams.

The approximate time to complete this lesson is 15 minutes.

Please enable JavaScript

In this lesson, we are going to talk about algorithms

Algorithms are one of the main concepts in computer science. That’s why we are starting this course on programming by studying algorithms.

It is widely used in many areas. For instance, in mathematics, physics and also, daily in our lives we are using algorithms.

Table of Contents

Algorithm definition.

An algorithm is a finite sequence of well-defined steps. When the steps are executed in the given order, they solve a problem. The order of the steps is defined by the sequence of the steps. These steps can be executed without the knowledge of the problem that is being solved. This means that it doesn’t matter whether you know the problem that is being solved or not.  You must be able to execute the algorithm.

Algorithm example

Let’s see the following example: calculate a perimeter of a square giving the length of one side.

The algorithm will be as follows

Here we are summing the side’s length four times (perimeter = side + side + side + side), instead of multiplying the length of the side by 4 (perimeter = 4* side).

These are considered two different algorithms, although both will give you the same result.

How to choose the best algorithm

Well, it depends, it will always depend.

The algorithms are compared according to time complexity and space complexity.

These two are the criteria that one must follow when we want to choose one algorithm among several others.

All algorithms have certain characteristics that are very important. So anytime we design an algorithm, we need to consider these characteristics.

Algorithms have a finite sequence of well-defined steps. It means they have a finite number of steps and, each of those steps must be executed in a finite time. Also, the execution of the whole algorithm will finish after a finite time.

The steps must be clear very clear and unambiguous. So, the steps must be well defined, everyone will understand what is required to execute each step.

Three ways of representing algorithms

 As you can see, on the left side we have an algorithm expressed in natural language. The first step is to assign the value of the side to a variable named side. The second step is to calculate the perimeter (perimeter = 4* side) and the last step is to print the value of the variable perimeter.

If we write that algorithm using pseudo-code, it will look like what you see in the middle of the picture. The first step is “read side”. The second step will be the formula. In this case, we are just using the variable names. We don’t have to write “calculate”. The last step is to print the perimeter.

In this lesson, we studied a definition of algorithm. Three main ways that we can use to represent an algorithm which are: natural language, pseudo-code, and flow diagrams.

• 1. Micro-Worlds
• 2. Light-Bot in Java
• 3. Jeroos of Santong Island
• 4. Problem Solving and Algorithms
• 5. Creating Jeroo Methods
• 6. Conditionally Executing Actions
• 7. Repeating Actions
• 8. Handling Touch Events
• 9. Adding Text to the Screen

Problem Solving and Algorithms

Learn a basic process for developing a solution to a problem. Nothing in this chapter is unique to using a computer to solve a problem. This process can be used to solve a wide variety of problems, including ones that have nothing to do with computers.

Problems, Solutions, and Tools

I have a problem! I need to thank Aunt Kay for the birthday present she sent me. I could send a thank you note through the mail. I could call her on the telephone. I could send her an email message. I could drive to her house and thank her in person. In fact, there are many ways I could thank her, but that's not the point. The point is that I must decide how I want to solve the problem, and use the appropriate tool to implement (carry out) my plan. The postal service, the telephone, the internet, and my automobile are tools that I can use, but none of these actually solves my problem. In a similar way, a computer does not solve problems, it's just a tool that I can use to implement my plan for solving the problem.

Knowing that Aunt Kay appreciates creative and unusual things, I have decided to hire a singing messenger to deliver my thanks. In this context, the messenger is a tool, but one that needs instructions from me. I have to tell the messenger where Aunt Kay lives, what time I would like the message to be delivered, and what lyrics I want sung. A computer program is similar to my instructions to the messenger.

The story of Aunt Kay uses a familiar context to set the stage for a useful point of view concerning computers and computer programs. The following list summarizes the key aspects of this point of view.

A computer is a tool that can be used to implement a plan for solving a problem.

A computer program is a set of instructions for a computer. These instructions describe the steps that the computer must follow to implement a plan.

An algorithm is a plan for solving a problem.

A person must design an algorithm.

A person must translate an algorithm into a computer program.

This point of view sets the stage for a process that we will use to develop solutions to Jeroo problems. The basic process is important because it can be used to solve a wide variety of problems, including ones where the solution will be written in some other programming language.

An Algorithm Development Process

Every problem solution starts with a plan. That plan is called an algorithm.

There are many ways to write an algorithm. Some are very informal, some are quite formal and mathematical in nature, and some are quite graphical. The instructions for connecting a DVD player to a television are an algorithm. A mathematical formula such as πR 2 is a special case of an algorithm. The form is not particularly important as long as it provides a good way to describe and check the logic of the plan.

The development of an algorithm (a plan) is a key step in solving a problem. Once we have an algorithm, we can translate it into a computer program in some programming language. Our algorithm development process consists of five major steps.

Step 1: Obtain a description of the problem.

Step 2: analyze the problem., step 3: develop a high-level algorithm., step 4: refine the algorithm by adding more detail., step 5: review the algorithm..

This step is much more difficult than it appears. In the following discussion, the word client refers to someone who wants to find a solution to a problem, and the word developer refers to someone who finds a way to solve the problem. The developer must create an algorithm that will solve the client's problem.

The client is responsible for creating a description of the problem, but this is often the weakest part of the process. It's quite common for a problem description to suffer from one or more of the following types of defects: (1) the description relies on unstated assumptions, (2) the description is ambiguous, (3) the description is incomplete, or (4) the description has internal contradictions. These defects are seldom due to carelessness by the client. Instead, they are due to the fact that natural languages (English, French, Korean, etc.) are rather imprecise. Part of the developer's responsibility is to identify defects in the description of a problem, and to work with the client to remedy those defects.

The purpose of this step is to determine both the starting and ending points for solving the problem. This process is analogous to a mathematician determining what is given and what must be proven. A good problem description makes it easier to perform this step.

When determining the starting point, we should start by seeking answers to the following questions:

What data are available?

Where is that data?

What formulas pertain to the problem?

What rules exist for working with the data?

What relationships exist among the data values?

When determining the ending point, we need to describe the characteristics of a solution. In other words, how will we know when we're done? Asking the following questions often helps to determine the ending point.

What new facts will we have?

What items will have changed?

What changes will have been made to those items?

What things will no longer exist?

An algorithm is a plan for solving a problem, but plans come in several levels of detail. It's usually better to start with a high-level algorithm that includes the major part of a solution, but leaves the details until later. We can use an everyday example to demonstrate a high-level algorithm.

Problem: I need a send a birthday card to my brother, Mark.

Analysis: I don't have a card. I prefer to buy a card rather than make one myself.

High-level algorithm:

Go to a store that sells greeting cards Select a card Purchase a card Mail the card

This algorithm is satisfactory for daily use, but it lacks details that would have to be added were a computer to carry out the solution. These details include answers to questions such as the following.

"Which store will I visit?"

"How will I get there: walk, drive, ride my bicycle, take the bus?"

"What kind of card does Mark like: humorous, sentimental, risqué?"

These kinds of details are considered in the next step of our process.

A high-level algorithm shows the major steps that need to be followed to solve a problem. Now we need to add details to these steps, but how much detail should we add? Unfortunately, the answer to this question depends on the situation. We have to consider who (or what) is going to implement the algorithm and how much that person (or thing) already knows how to do. If someone is going to purchase Mark's birthday card on my behalf, my instructions have to be adapted to whether or not that person is familiar with the stores in the community and how well the purchaser known my brother's taste in greeting cards.

When our goal is to develop algorithms that will lead to computer programs, we need to consider the capabilities of the computer and provide enough detail so that someone else could use our algorithm to write a computer program that follows the steps in our algorithm. As with the birthday card problem, we need to adjust the level of detail to match the ability of the programmer. When in doubt, or when you are learning, it is better to have too much detail than to have too little.

Most of our examples will move from a high-level to a detailed algorithm in a single step, but this is not always reasonable. For larger, more complex problems, it is common to go through this process several times, developing intermediate level algorithms as we go. Each time, we add more detail to the previous algorithm, stopping when we see no benefit to further refinement. This technique of gradually working from a high-level to a detailed algorithm is often called stepwise refinement .

The final step is to review the algorithm. What are we looking for? First, we need to work through the algorithm step by step to determine whether or not it will solve the original problem. Once we are satisfied that the algorithm does provide a solution to the problem, we start to look for other things. The following questions are typical of ones that should be asked whenever we review an algorithm. Asking these questions and seeking their answers is a good way to develop skills that can be applied to the next problem.

Does this algorithm solve a very specific problem or does it solve a more general problem ? If it solves a very specific problem, should it be generalized?

For example, an algorithm that computes the area of a circle having radius 5.2 meters (formula π*5.2 2 ) solves a very specific problem, but an algorithm that computes the area of any circle (formula π*R 2 ) solves a more general problem.

Can this algorithm be simplified ?

One formula for computing the perimeter of a rectangle is:

length + width + length + width

A simpler formula would be:

2.0 * ( length + width )

Is this solution similar to the solution to another problem? How are they alike? How are they different?

For example, consider the following two formulae:

Rectangle area = length * width Triangle area = 0.5 * base * height

Similarities: Each computes an area. Each multiplies two measurements.

Differences: Different measurements are used. The triangle formula contains 0.5.

Hypothesis: Perhaps every area formula involves multiplying two measurements.

Example 4.1: Pick and Plant

This section contains an extended example that demonstrates the algorithm development process. To complete the algorithm, we need to know that every Jeroo can hop forward, turn left and right, pick a flower from its current location, and plant a flower at its current location.

Problem Statement (Step 1)

A Jeroo starts at (0, 0) facing East with no flowers in its pouch. There is a flower at location (3, 0). Write a program that directs the Jeroo to pick the flower and plant it at location (3, 2). After planting the flower, the Jeroo should hop one space East and stop. There are no other nets, flowers, or Jeroos on the island.

Analysis of the Problem (Step 2)

The flower is exactly three spaces ahead of the jeroo.

The flower is to be planted exactly two spaces South of its current location.

The Jeroo is to finish facing East one space East of the planted flower.

There are no nets to worry about.

High-level Algorithm (Step 3)

Let's name the Jeroo Bobby. Bobby should do the following:

Get the flower Put the flower Hop East

Detailed Algorithm (Step 4)

Get the flower Hop 3 times Pick the flower Put the flower Turn right Hop 2 times Plant a flower Hop East Turn left Hop once

Review the Algorithm (Step 5)

The high-level algorithm partitioned the problem into three rather easy subproblems. This seems like a good technique.

This algorithm solves a very specific problem because the Jeroo and the flower are in very specific locations.

This algorithm is actually a solution to a slightly more general problem in which the Jeroo starts anywhere, and the flower is 3 spaces directly ahead of the Jeroo.

Java Code for "Pick and Plant"

A good programmer doesn't write a program all at once. Instead, the programmer will write and test the program in a series of builds. Each build adds to the previous one. The high-level algorithm will guide us in this process.

FIRST BUILD

To see this solution in action, create a new Greenfoot4Sofia scenario and use the Edit Palettes Jeroo menu command to make the Jeroo classes visible. Right-click on the Island class and create a new subclass with the name of your choice. This subclass will hold your new code.

The recommended first build contains three things:

The main method (here myProgram() in your island subclass).

Declaration and instantiation of every Jeroo that will be used.

The high-level algorithm in the form of comments.

The instantiation at the beginning of myProgram() places bobby at (0, 0), facing East, with no flowers.

Once the first build is working correctly, we can proceed to the others. In this case, each build will correspond to one step in the high-level algorithm. It may seem like a lot of work to use four builds for such a simple program, but doing so helps establish habits that will become invaluable as the programs become more complex.

SECOND BUILD

This build adds the logic to "get the flower", which in the detailed algorithm (step 4 above) consists of hopping 3 times and then picking the flower. The new code is indicated by comments that wouldn't appear in the original (they are just here to call attention to the additions). The blank lines help show the organization of the logic.

By taking a moment to run the work so far, you can confirm whether or not this step in the planned algorithm works as expected.

THIRD BUILD

This build adds the logic to "put the flower". New code is indicated by the comments that are provided here to mark the additions.

FOURTH BUILD (final)

Example 4.2: replace net with flower.

This section contains a second example that demonstrates the algorithm development process.

There are two Jeroos. One Jeroo starts at (0, 0) facing North with one flower in its pouch. The second starts at (0, 2) facing East with one flower in its pouch. There is a net at location (3, 2). Write a program that directs the first Jeroo to give its flower to the second one. After receiving the flower, the second Jeroo must disable the net, and plant a flower in its place. After planting the flower, the Jeroo must turn and face South. There are no other nets, flowers, or Jeroos on the island.

Jeroo_2 is exactly two spaces behind Jeroo_1.

The only net is exactly three spaces ahead of Jeroo_2.

Each Jeroo has exactly one flower.

Jeroo_2 will have two flowers after receiving one from Jeroo_1. One flower must be used to disable the net. The other flower must be planted at the location of the net, i.e. (3, 2).

Jeroo_1 will finish at (0, 1) facing South.

Jeroo_2 is to finish at (3, 2) facing South.

Each Jeroo will finish with 0 flowers in its pouch. One flower was used to disable the net, and the other was planted.

Let's name the first Jeroo Ann and the second one Andy.

Ann should do the following: Find Andy (but don't collide with him) Give a flower to Andy (he will be straight ahead) After receiving the flower, Andy should do the following: Find the net (but don't hop onto it) Disable the net Plant a flower at the location of the net Face South

Ann should do the following: Find Andy Turn around (either left or right twice) Hop (to location (0, 1)) Give a flower to Andy Give ahead Now Andy should do the following: Find the net Hop twice (to location (2, 2)) Disable the net Toss Plant a flower at the location of the net Hop (to location (3, 2)) Plant a flower Face South Turn right

The high-level algorithm helps manage the details.

This algorithm solves a very specific problem, but the specific locations are not important. The only thing that is important is the starting location of the Jeroos relative to one another and the location of the net relative to the second Jeroo's location and direction.

Java Code for "Replace Net with Flower"

As before, the code should be written incrementally as a series of builds. Four builds will be suitable for this problem. As usual, the first build will contain the main method, the declaration and instantiation of the Jeroo objects, and the high-level algorithm in the form of comments. The second build will have Ann give her flower to Andy. The third build will have Andy locate and disable the net. In the final build, Andy will place the flower and turn East.

This build creates the main method, instantiates the Jeroos, and outlines the high-level algorithm. In this example, the main method would be myProgram() contained within a subclass of Island .

This build adds the logic for Ann to locate Andy and give him a flower.

This build adds the logic for Andy to locate and disable the net.

This build adds the logic for Andy to place a flower at (3, 2) and turn South.

• Part 2 Problem-solving »
• Chapter 3 Solving Problems by Searching
• Edit on GitHub

Chapter 3 Solving Problems by Searching 

When the correct action to take is not immediately obvious, an agent may need to plan ahead : to consider a sequence of actions that form a path to a goal state. Such an agent is called a problem-solving agent , and the computational process it undertakes is called search .

Problem-solving agents use atomic representations, that is, states of the world are considered as wholes, with no internal structure visible to the problem-solving algorithms. Agents that use factored or structured representations of states are called planning agents .

We distinguish between informed algorithms, in which the agent can estimate how far it is from the goal, and uninformed algorithms, where no such estimate is available.

3.1 Problem-Solving Agents 

If the agent has no additional information—that is, if the environment is unknown —then the agent can do no better than to execute one of the actions at random. For now, we assume that our agents always have access to information about the world. With that information, the agent can follow this four-phase problem-solving process:

GOAL FORMULATION : Goals organize behavior by limiting the objectives and hence the actions to be considered.

PROBLEM FORMULATION : The agent devises a description of the states and actions necessary to reach the goal—an abstract model of the relevant part of the world.

SEARCH : Before taking any action in the real world, the agent simulates sequences of actions in its model, searching until it finds a sequence of actions that reaches the goal. Such a sequence is called a solution .

EXECUTION : The agent can now execute the actions in the solution, one at a time.

It is an important property that in a fully observable, deterministic, known environment, the solution to any problem is a fixed sequence of actions . The open-loop system means that ignoring the percepts breaks the loop between agent and environment. If there is a chance that the model is incorrect, or the environment is nondeterministic, then the agent would be safer using a closed-loop approach that monitors the percepts.

In partially observable or nondeterministic environments, a solution would be a branching strategy that recommends different future actions depending on what percepts arrive.

3.1.1 Search problems and solutions 

A search problem can be defined formally as follows:

A set of possible states that the environment can be in. We call this the state space .

The initial state that the agent starts in.

A set of one or more goal states . We can account for all three of these possibilities by specifying an \(Is\-Goal\) method for a problem.

The actions available to the agent. Given a state \(s\) , \(Actions(s)\) returns a finite set of actions that can be executed in \(s\) . We say that each of these actions is applicable in \(s\) .

A transition model , which describes what each action does. \(Result(s,a)\) returns the state that results from doing action \(a\) in state \(s\) .

An action cost function , denote by \(Action\-Cost(s,a,s\pr)\) when we are programming or \(c(s,a,s\pr)\) when we are doing math, that gives the numeric cost of applying action \(a\) in state \(s\) to reach state \(s\pr\) .

A sequence of actions forms a path , and a solution is a path from the initial state to a goal state. We assume that action costs are additive; that is, the total cost of a path is the sum of the individual action costs. An optimal solution has the lowest path cost among all solutions.

The state space can be represented as a graph in which the vertices are states and the directed edges between them are actions.

3.1.2 Formulating problems 

The process of removing detail from a representation is called abstraction . The abstraction is valid if we can elaborate any abstract solution into a solution in the more detailed world. The abstraction is useful if carrying out each of the actions in the solution is easier than the original problem.

3.2 Example Problems 

A standardized problem is intended to illustrate or exercise various problem-solving methods. It can be given a concise, exact description and hence is suitable as a benchmark for researchers to compare the performance of algorithms. A real-world problem , such as robot navigation, is one whose solutions people actually use, and whose formulation is idiosyncratic, not standardized, because, for example, each robot has different sensors that produce different data.

3.2.1 Standardized problems 

A grid world problem is a two-dimensional rectangular array of square cells in which agents can move from cell to cell.

Vacuum world

Sokoban puzzle

Sliding-tile puzzle

3.2.2 Real-world problems 

Route-finding problem

Touring problems

Trveling salesperson problem (TSP)

VLSI layout problem

Robot navigation

Automatic assembly sequencing

3.3 Search Algorithms 

A search algorithm takes a search problem as input and returns a solution, or an indication of failure. We consider algorithms that superimpose a search tree over the state-space graph, forming various paths from the initial state, trying to find a path that reaches a goal state. Each node in the search tree corresponds to a state in the state space and the edges in the search tree correspond to actions. The root of the tree corresponds to the initial state of the problem.

The state space describes the (possibly infinite) set of states in the world, and the actions that allow transitions from one state to another. The search tree describes paths between these states, reaching towards the goal. The search tree may have multiple paths to (and thus multiple nodes for) any given state, but each node in the tree has a unique path back to the root (as in all trees).

The frontier separates two regions of the state-space graph: an interior region where every state has been expanded, and an exterior region of states that have not yet been reached.

3.3.1 Best-first search 

In best-first search we choose a node, \(n\) , with minimum value of some evaluation function , \(f(n)\) .

3.3.2 Search data structures 

A node in the tree is represented by a data structure with four components

\(node.State\) : the state to which the node corresponds;

\(node.Parent\) : the node in the tree that generated this node;

\(node.Action\) : the action that was applied to the parent’s state to generate this node;

\(node.Path\-Cost\) : the total cost of the path from the initial state to this node. In mathematical formulas, we use \(g(node)\) as a synonym for \(Path\-Cost\) .

Following the \(PARENT\) pointers back from a node allows us to recover the states and actions along the path to that node. Doing this from a goal node gives us the solution.

We need a data structure to store the frontier . The appropriate choice is a queue of some kind, because the operations on a frontier are:

\(Is\-Empty(frontier)\) returns true only if there are no nodes in the frontier.

\(Pop(frontier)\) removes the top node from the frontier and returns it.

\(Top(frontier)\) returns (but does not remove) the top node of the frontier.

\(Add(node, frontier)\) inserts node into its proper place in the queue.

Three kinds of queues are used in search algorithms:

A priority queue first pops the node with the minimum cost according to some evaluation function, \(f\) . It is used in best-first search.

A FIFO queue or first-in-first-out queue first pops the node that was added to the queue first; we shall see it is used in breadth-first search.

A LIFO queue or last-in-first-out queue (also known as a stack ) pops first the most recently added node; we shall see it is used in depth-first search.

3.3.3 Redundant paths 

A cycle is a special case of a redundant path .

As the saying goes, algorithms that cannot remember the past are doomed to repeat it . There are three approaches to this issue.

First, we can remember all previously reached states (as best-first search does), allowing us to detect all redundant paths, and keep only the best path to each state.

Second, we can not worry about repeating the past. We call a search algorithm a graph search if it checks for redundant paths and a tree-like search if it does not check.

Third, we can compromise and check for cycles, but not for redundant paths in general.

3.3.4 Measuring problem-solving performance 

COMPLETENESS : Is the algorithm guaranteed to find a solution when there is one, and to correctly report failure when there is not?

COST OPTIMALITY : Does it find a solution with the lowest path cost of all solutions?

TIME COMPLEXITY : How long does it take to find a solution?

SPACE COMPLEXITY : How much memory is needed to perform the search?

To be complete, a search algorithm must be systematic in the way it explores an infinite state space, making sure it can eventually reach any state that is connected to the initial state.

In theoretical computer science, the typical measure of time and space complexity is the size of the state-space graph, \(|V|+|E|\) , where \(|V|\) is the number of vertices (state nodes) of the graph and \(|E|\) is the number of edges (distinct state/action pairs). For an implicit state space, complexity can be measured in terms of \(d\) , the depth or number of actions in an optimal solution; \(m\) , the maximum number of actions in any path; and \(b\) , the branching factor or number of successors of a node that need to be considered.

3.4 Uninformed Search Strategies 

3.4.1 breadth-first search .

When all actions have the same cost, an appropriate strategy is breadth-first search , in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on.

Breadth-first search always finds a solution with a minimal number of actions, because when it is generating nodes at depth \(d\) , it has already generated all the nodes at depth \(d-1\) , so if one of them were a solution, it would have been found.

All the nodes remain in memory, so both time and space complexity are \(O(b^d)\) . The memory requirements are a bigger problem for breadth-first search than the execution time . In general, exponential-complexity search problems cannot be solved by uninformed search for any but the smallest instances .

3.4.2 Dijkstra’s algorithm or uniform-cost search 

When actions have different costs, an obvious choice is to use best-first search where the evaluation function is the cost of the path from the root to the current node. This is called Dijkstra’s algorithm by the theoretical computer science community, and uniform-cost search by the AI community.

The complexity of uniform-cost search is characterized in terms of \(C^*\) , the cost of the optimal solution, and \(\epsilon\) , a lower bound on the cost of each action, with \(\epsilon>0\) . Then the algorithm’s worst-case time and space complexity is \(O(b^{1+\lfloor C^*/\epsilon\rfloor})\) , which can be much greater than \(b^d\) .

When all action costs are equal, \(b^{1+\lfloor C^*/\epsilon\rfloor}\) is just \(b^{d+1}\) , and uniform-cost search is similar to breadth-first search.

3.4.3 Depth-first search and the problem of memory 

Depth-first search always expands the deepest node in the frontier first. It could be implemented as a call to \(Best\-First\-Search\) where the evaluation function \(f\) is the negative of the depth.

For problems where a tree-like search is feasible, depth-first search has much smaller needs for memory. A depth-first tree-like search takes time proportional to the number of states, and has memory complexity of only \(O(bm)\) , where \(b\) is the branching factor and \(m\) is the maximum depth of the tree.

A variant of depth-first search called backtracking search uses even less memory.

3.4.4 Depth-limited and iterative deepening search 

To keep depth-first search from wandering down an infinite path, we can use depth-limited search , a version of depth-first search in which we supply a depth limit, \(l\) , and treat all nodes at depth \(l\) as if they had no successors. The time complexity is \(O(b^l)\) and the space complexity is \(O(bl)\)

Iterative deepening search solves the problem of picking a good value for \(l\) by trying all values: first 0, then 1, then 2, and so on—until either a solution is found, or the depth- limited search returns the failure value rather than the cutoff value.

Its memory requirements are modest: \(O(bd)\) when there is a solution, or \(O(bm)\) on finite state spaces with no solution. The time complexity is \(O(bd)\) when there is a solution, or \(O(bm)\) when there is none.

In general, iterative deepening is the preferred uninformed search method when the search state space is larger than can fit in memory and the depth of the solution is not known .

3.4.5 Bidirectional search 

An alternative approach called bidirectional search simultaneously searches forward from the initial state and backwards from the goal state(s), hoping that the two searches will meet.

3.4.6 Comparing uninformed search algorithms 

3.5 Informed (Heuristic) Search Strategies 

An informed search strategy uses domain–specific hints about the location of goals to find colutions more efficiently than an uninformed strategy. The hints come in the form of a heuristic function , denoted \(h(n)\) :

\(h(n)\) = estimated cost of the cheapest path from the state at node \(n\) to a goal state.

3.5.1 Greedy best-first search 

Greedy best-first search is a form of best-first search that expands first the node with the lowest \(h(n)\) value—the node that appears to be closest to the goal—on the grounds that this is likely to lead to a solution quickly. So the evaluation function \(f(n)=h(n)\) .

Problem Solving

Solving problems is the core of computer science. Programmers must first understand how a human solves a problem, then understand how to translate this "algorithm" into something a computer can do, and finally how to "write" the specific syntax (required by a computer) to get the job done. It is sometimes the case that a machine will solve a problem in a completely different way than a human.

Computer Programmers are problem solvers. In order to solve a problem on a computer you must:

Know how to represent the information (data) describing the problem.

Determine the steps to transform the information from one representation into another.

Information Representation

A computer, at heart, is really dumb. It can only really know about a few things... numbers, characters, booleans, and lists (called arrays) of these items. (See Data Types). Everything else must be "approximated" by combinations of these data types.

A good programmer will "encode" all the "facts" necessary to represent a problem in variables (See Variables). Further, there are "good ways" and "bad ways" to encode information. Good ways allow the computer to easily "compute" new information.

An algorithm (see Algorithm) is a set of specific steps to solve a problem. Think of it this way: if you were to tell your 3 year old neice to play your favorite song on the piano (assuming the neice has never played a piano), you would have to tell her where the piano was, and how to sit on the bench, and how to open the cover, and which keys to press, and which order to press them in, etc, etc, etc.

The core of what good programmers do is being able to define the steps necessary to accomplish a goal. Unfortunately, a computer, only knows a very restricted and limited set of possible steps. For example a computer can add two numbers. But if you want to find the average of two numbers, this is beyond the basic capabilities of a computer. To find the average, you must:

• First: Add the two numbers and save this result in a variable
• Then: Divide this new number the number two, and save this result in a variable.
• Finally: provide this number to the rest of the program (or print it for the user).

We "compute" all the time. Computing is the act of solving problems (or coming up with a plan to solve problems) in an organized manner. We don't need computers to "compute". We can use our own brain.

Encapsulation and Abstraction and Complexity Hiding

Computer scientists like to use the fancy word "Encapsulation" to show how smart we are. This is just a term for things we do as humans every day. It is combined with another fancy term: "Abstraction".

Abstraction is the idea of "ignoring the details". For example, a forest is really a vastly complex ecosystem containing trees, animals, water paths, etc, etc, etc. But to a computer scientist (and to a normal person), its just "a forest".

For example, if your professor needs a cup of coffee, and asks you the single item: "Get me a cup of coffee", he has used both encapsulation and abstraction. The number of steps required to actually get the coffee are enumerable. Including, getting up, walking down the hall, getting in your car, driving to a coffee stand, paying for the coffee, etc, etc, etc. Further, the idea of what a cup of coffee is, is abstract. Do you bring a mug of coffee, or a Styrofoam cup? Is it caffeinated or not? Is it freshly brewed or from concentrate? Does it come from Africa or America?

All of this information is TOO MUCH and we would quickly be unable to funciton if we had to remember all of these details. Thus we "abstract away" the details and only remember the few important items.

This brings us to the idea of "Complexity Hiding". Complexity hiding is the idea that most of the times details don't matter. In a computer program, as simple an idea as drawing a square on the screen involves hundreds (if not thousands) of (low level) computer instructions. Again, a person couldn't possible create interesting programs if every time they wanted to do something, they had to re-write (correctly) every one of those instructions. By "ecapsulating" what is meant by "draw square" and "reusing" this operation over and over again, we make programming tractable.

Encapsulation

The idea behind encapsulation is to store the information necessary to a particular idea in a set of variables associated with a single "object". We then create functions to manipulate this object, regardless of what the actual data is. From that point on, we treat the idea from a "high level" rather than worry about all the parts (data) and actions (functions) necessary to represent the object in a computer.

Brute Force

Brute force is a technique for solving problems that relies on a computers speed (how fast it can repeat steps) to solve a problem. For example, if you wanted to know how many times the number 8 goes into the number 100, you could do the following:

Of course this is a silly way for a computer (or a human) to solve this problem. The real way we would do it is:

When in doubt, you can often use "brute force" to solve a problem, but it often saves time (at least computer time) to think about the problem and solve it in an elegant manner.

Have a language expert improve your writing

Check your paper for plagiarism in 10 minutes, generate your apa citations for free.

• Knowledge Base
• Using AI tools
• What Is an Algorithm? | Definition & Examples

What Is an Algorithm? | Definition & Examples

Published on August 9, 2023 by Kassiani Nikolopoulou . Revised on August 29, 2023.

An algorithm is a set of steps for accomplishing a task or solving a problem. Typically, algorithms are executed by computers, but we also rely on algorithms in our daily lives. Each time we follow a particular step-by-step process, like making coffee in the morning or tying our shoelaces, we are in fact following an algorithm.

In the context of computer science , an algorithm is a mathematical process for solving a problem using a finite number of steps. Algorithms are a key component of any computer program and are the driving force behind various systems and applications, such as navigation systems, search engines, and music streaming services.

Instantly correct all language mistakes in your text

Upload your document to correct all your mistakes in minutes

Table of contents

What is an algorithm, how do algorithms work, examples of algorithms, other interesting articles, frequently asked questions about algorithms.

An algorithm is a sequence of instructions that a computer must perform to solve a well-defined problem. It essentially defines what the computer needs to do and how to do it. Algorithms can instruct a computer how to perform a calculation, process data, or make a decision.

The best way to understand an algorithm is to think of it as a recipe that guides you through a series of well-defined actions to achieve a specific goal. Just like a recipe produces a replicable result, algorithms ensure consistent and reliable outcomes for a wide range of tasks in the digital realm.

And just like there are numerous ways to make, for example, chocolate chip cookies by following different steps or using slightly different ingredients, different algorithms can be designed to solve the same problem, with each taking a distinct approach but achieving the same result.

Algorithms are virtually everywhere around us. Examples include the following:

• Search engines rely on algorithms to find and present relevant results as quickly as possible
• Social media platforms use algorithms to prioritize the content that we see in our feeds, taking into account factors like our past behavior, the popularity of posts, and relevance.
• With the help of algorithms, navigation apps determine the most efficient route for us to reach our destination.
• It must be correct . In other words, it should take a given problem and provide the right answer or result, even if it stops working due to an error.
• It must consist of clear, practical steps that can be completed in a limited time, whether by a person or the machine that must execute the algorithm. For example, the instructions in a cookie recipe might be considered sufficiently concrete for a human cook, but they would not be specific enough for programming an automated cookie-making machine.
• There should be no confusion about which step comes next , even if choices must be made (e.g., when using “if” statements).
• It must have a set number of steps (not an infinite number) that can be managed using loops (statements describing repeated actions or iterations).
• It must eventually reach an endpoint and not get stuck in a never-ending loop.

Check for common mistakes

Use the best grammar checker available to check for common mistakes in your text.

Fix mistakes for free

Algorithms use a set of initial data or input , process it through a series of logical steps or rules, and produce the output (i.e., the outcome, decision, or result).

If you want to make chocolate chip cookies, for instance, the input would be the ingredients and quantities, the process would be the recipe you choose to follow, and the output would be the cookies.

Algorithms are eventually expressed in a programming language that a computer can process. However, when an algorithm is being created, it will be people, not a computer, who will need to understand it. For this reason, as a first step, algorithms are written as plain instructions.

• Input: the input data is a single-digit number (e.g., 5).
• Transformation/processing: the algorithm takes the input (number 5) and performs the specific operation (i.e., multiplies the number by itself).
• Output: the result of the calculation is the square of the input number, which, in this case, would be 25 (since 5 * 5 = 25).

We could express this as an algorithm in the following way:

Algorithm: Calculate the square of a number

• Input the number (N) whose square you want to find.
• Multiply the number (N) by itself.
• Store the result of the multiplication in a variable (result).
• Output the value of the variable (result), which represents the square of the input number.

It is important to keep in mind that an algorithm is not the same as a program or code. It is the logic or plan for solving a problem represented as a simple step-by-step description. Code is the implementation of the algorithm in a specific programming language (like C++ or Python), while a program is an implementation of code that instructs a computer on how to execute an algorithm and perform a task.

Instead of telling a computer exactly what to do, some algorithms allow computers to learn on their own and improve their performance on a specific task. These machine learning algorithms use data to identify patterns and make predictions or conduct data mining to uncover hidden insights in data that can inform business decisions.

Broadly speaking, there are three different types of algorithms:

• Linear sequence algorithms follow a specific set or steps, one after the other. Just like following a recipe, each step depends on the success of the previous one.
• For example, in the context of a cookie recipe, you would include the step “if the dough is too sticky, you might need to refrigerate it.”
• For example, a looping algorithm could be used to handle the process of making multiple cookies from a single batch of dough. The algorithm would repeat a specific set of instructions to form and bake cookies until all the dough has been used.

Algorithms are fundamental tools for problem-solving in both the digital world and many real-life scenarios. Each time we try to solve a problem by breaking it down into smaller, manageable steps, we are in fact using algorithmic thinking.

• Identify which clothes are clean.
• Consider the weather forecast for the day.
• Consider the occasion for which you are getting dressed (e.g., work or school etc.).
• Consider personal preferences (e.g., style or which items match).

In mathematics, algorithms are standard methods for performing calculations or solving equations because they are efficient, reliable, and applicable to various situations.

Suppose you want to add the numbers 345 and 278. You would follow a set of steps (i.e., the standard algorithm for addition):

• Write down the numbers so the digits align.
• Start from the rightmost digits (the ones place) and add them together: 5 + 8 = 13. Write down the 3 and carry over the 1 to the next column.
• Move to the next column (the tens place) and add the digits along with the carried-over value: 4 + 7 + 1 = 12. Write down the 2 and carry over the 1 to the next column.
• Move to the leftmost column (the hundreds place) and add the digits along with the carried-over value: 3 + 2 + 1 = 6. Write down the 6.

The final result is 623

Navigation systems are another example of the use of algorithms. Such systems use algorithms to help you find the easiest and fastest route to your destination while avoiding traffic jams and roadblocks.

If you want to know more about ChatGPT, AI tools , fallacies , and research bias , make sure to check out some of our other articles with explanations and examples.

• ChatGPT vs human editor
• ChatGPT citations
• Is ChatGPT trustworthy?
• Using ChatGPT for your studies
• Sunk cost fallacy
• Straw man fallacy
• Slippery slope fallacy
• Red herring fallacy
• Ecological fallacy
• Logical fallacy

Research bias

• Implicit bias
• Framing bias
• Cognitive bias
• Optimism bias
• Hawthorne effect
• Unconscious bias

Don't submit your assignments before you do this

The academic proofreading tool has been trained on 1000s of academic texts. Making it the most accurate and reliable proofreading tool for students. Free citation check included.

Try for free

In computer science, an algorithm is a list of unambiguous instructions that specify successive steps to solve a problem or perform a task. Algorithms help computers execute tasks like playing games or sorting a list of numbers. In other words, computers use algorithms to understand what to do and give you the result you need.

Algorithms and artificial intelligence (AI) are not the same, however they are closely related.

• Artificial intelligence is a broad term describing computer systems performing tasks usually associated with human intelligence like decision-making, pattern recognition, or learning from experience.
• Algorithms are the instructions that AI uses to carry out these tasks, therefore we could say that algorithms are the building blocks of AI—even though AI involves more advanced capabilities beyond just following instructions.

Algorithms and computer programs are sometimes used interchangeably, but they refer to two distinct but interrelated concepts.

• An algorithm is a step-by-step instruction for solving a problem that is precise yet general.
• Computer programs are specific implementations of an algorithm in a specific programming language. In other words, the algorithm is the high-level description of an idea, while the program is the actual implementation of that idea.

Algorithms are valuable to us because they:

• Form the basis of much of the technology we use in our daily lives, from mobile apps to search engines.
• Power innovations in various industries that augment our abilities (e.g., AI assistants or medical diagnosis).
• Help analyze large volumes of data, discover patterns and make informed decisions in a fast and efficient way, at a scale humans are simply not able to do.
• Automate processes. By streamlining tasks, algorithms increase efficiency, reduce errors, and save valuable time.

Cite this Scribbr article

If you want to cite this source, you can copy and paste the citation or click the “Cite this Scribbr article” button to automatically add the citation to our free Citation Generator.

Nikolopoulou, K. (2023, August 29). What Is an Algorithm? | Definition & Examples. Scribbr. Retrieved September 23, 2024, from https://www.scribbr.com/ai-tools/what-is-an-algorithm/

Is this article helpful?

Kassiani Nikolopoulou

Other students also liked, what is deep learning | a beginner's guide, what is data mining | definition & techniques, what is machine learning | a beginner's guide, get unlimited documents corrected.

✔ Free APA citation check included ✔ Unlimited document corrections ✔ Specialized in correcting academic texts

• Create account
• Contributions
• Discussion for this IP address

Problem Solving: Algorithm design

Express the solution to a simple problem as an algorithm using flowcharts, pseudo-code or structured English and the standard constructs:

performing or operating each step consecutively in the order they arise

• include<stdio.h>

int main() {

Selection is choosing a step

A sequence of steps that loop until a requirement is met

• Book:A-level Computing

Algorithm Representation

ECE-1021 Home

Algorithms - An Overview

Essential elements of a good representation, show the logic, reveal the flow, be expandable and collapsible, aid in implementation, implementation independence, a recommended pseudocode format, documentation keywords, action keywords, flow control keywords, basic flowchart shapes, circle - entry/exit point, rectangle - task, parallelogram - input/output, diamond - decision point, arrow - interblock flow.

Algorithms are basically a set of instructions that, if correct and if followed carefully, produce some desired result. Since they are sets of instructions, they are generally presented in such a way that that the step-by-step nature of how they should be followed is readily apparent. The two most common representations are pseudocode and flowcharts. In this course, unless it is stated otherwise, you are free to use either one at your discretion. Likewise, unless the context indicates otherwise, references to either in the following discussion generally refer to both.

Algorithms can be thought of as the recipe for taking the general solution for a class of problem and applying it to a specific instance of a problem covered by that class. For instance, the class of problem might be to find the surface area of a sphere given its radius. Through some problem solving means - perhaps by performing the fundamental calculus computation or perhaps simply by looking up the equation in a math book - we determine that the general solution to the problem is that the area is four times pi times the square of the radius. We can then use this general solution and create an algorithm that permits use to compute the surface area of a specific sphere:

• GET: radius
• SET: area = 4pi*radius*radius

But our problem could be at an even more abstract level than this - perhaps the problem is to find the surface area of a solid of rotation for a function that intersects the x-axis in exactly two places. In this case, a sphere is simply a specific instance of the problem where the function happens to be:

y = sqrt(r 2 - x 2 )

Now the algorithm might look something more like this:

• TASK: Determine the left hand intersection (xmin) of the function with the x-axis.
• TASK: Determine the right hand intersection (xmax) of the function with the x-axis.
• TASK: Integrate the surface of rotation between xmin and xmax.

Notice that we still only have a set of tasks, but each task is more narrowly defined and can be treated as its own problem and a more detailed algorithm for that task developed independently. Notice also that two of the tasks are intimately related such that figuring out how to solve the first can be expected to directly lead to knowing how to solve the second.

Note how the word "TASK" is used above. A line that starts with this word contains a description of something that needs to be accomplished as opposed to an instruction, such as "GET" or "SET" in the first example, that tells us how to actually accomplish it. The process of breaking down a problem into a set of tasks is frequently referred to as decomposing the problem and the result is generally called a "decomposition outline". At some point, a given task is so thoroughly refined that any further decomposition almost has to involve specific instructions on how to perform the task. Some people maintain that at this point you have moved from writing a decomposition outline to writing pseudocode. Others maintain that the phrases "decomposition outline" and "pseudocode" are largely interchangeable. This latter school of thought makes a strong argument when they point to the analogous situation when this same process is done graphically. Whether it is at the highest level of abstraction or the deepest level of detail, we call the result a "flowchart". We might use adjectives such as "top-level" or "highly-detailed" to indicate the degree of abstraction represented in the flowchart, but we don't usually claim that there is something fundamentally different between the two.

What everyone pretty much agrees on is that, whatever you call it, there is a continuum in the tradeoff between remaining very abstract versus being highly detailed and the proper balance depends on the specifics of the situation. For instance, Task 1.1 above - finding the left hand intersection - may well be adequately refined if it can be reasonably assumed that the person using the outline is capable of going from there and figuring out, on their own, how to find that intersection. The purpose of the outline is to tell them that finding the point of intersection is something that needs to happen and not how to go about finding it. If that is not a reasonable expectation, then that task should be further refined. Hence, if you are asked to develop a flowchart or write the pseudocode for a problem, it is best to come to an understanding of how much detail is expected. Fortunately, unlike in a classroom setting, the answer to this question is usually self-evident to a large degree. The reason is simple - in most cases where you might be asked to do this, you also know why you are being asked to do it and therefore you know the context in which your work will be used. You will probably also have some sort of feedback so that if you aren't sufficiently detailed you will be asked to go into more depth whereas if you are going into too much detail your boss will start asking what's taking so long - although, in practice, they may do that anyway even in the same breath in which they request more detail. 

As mentioned previously, algorithms are generally represented by either pseudocode or a flowchart. But what are these? It might be accurate to claim that each is merely a means of representing an algorithm, but that would hardly move the discussion along. Instead, let's focus on what features we need our means of algorithm representation to have in order for it to be a meaningful and useful representation.

• Show the logic of how the problem is solved - not how it is implemented.
• Readily reveal the flow of the algorithm.
• Be expandable and collapsible. 
• Lend itself to implementation of the algorithm.

One of the most difficult things for people just learning problem solving - especially when it involves computer programming - is to clearly distinguish between the concept of problem logic and implementation logic. The former is independent of the details of how the problem solution is implemented. If you are trying to find the radius of a sphere having a specific surface area, then you need to find out what that area is, you need some means of dividing that area by 4pi, and you need some means of taking the square root of the result. It doesn't matter whether you are solving the problem with a C program, a Java program, a calculator, a pencil and paper, or in your head - those elements are part of the logic of solving the problem. The logic involved in taking the square root of a number, on the other hand, is germane primarily to the logic of how you are implementing your solution. In other words, for most purposes I can communicate the logic behind how to determine the radius of a sphere with a specific surface area by going into no more detail than to note that, at some point, it is necessary to take the square root of a number.

Your algorithm representation should focus on the logic of the problem, and not the logic of the eventual implementation. More specifically, the upper levels of your representation should, to the degree possible, be devoid of implementation details - these should be relegated to the lower levels of the representation.

Most problems, especially if they are intended to be solved with the aid of a computer program, involve flow control. In the "structured programming" paradigm, this flow control consists of sequences, selections, and repetitions. This may not be readily apparent at the topmost level where the algorithm can be represented by a list of tasks that are to be performed one after another in a specific sequence. But at some point, as each of those tasks is developed, decisions will have to be made and different steps taken depending on the outcome of those decisions. The representation method used should be compatible with this and clearly show the points at which decisions are made and what the various courses of action are that can result.

Our algorithm representation should be flexible and allow us to readily collapse it so as to show less detail and focus on the more abstract elements of the algorithm or to expand it so as to get as detailed as necessary in order to actually implement the solution. Unstated in this is an acknowledgement that, as we expand our algorithm and become more detailed, at some point we have to get into the logic of the implementation issues. 

For instance, if we expand the step that says to take the square root of a number, we have to start describing the specific method that will be used to do this and that method is highly dependent on the eventual implementation. At that point, our algorithm is becoming "locked" to that particular implementation. This is perfectly acceptable. The reason that we should be asking for more detail on how to take the square root is because we are now dealing with implementation issues and therefore expect that the steps will be specific to the implementation. 

If we have structured our representation properly, then we can always back up. If our original implementation was with a C program and now we want to implement the algorithm in assembly on a PIC microcontroller, then we simply collapse our algorithm until the implementation dependent portions are gone and then re-expand the high level logic that was left in such a way that it can now be implemented on a PIC. If our high level logic is geared towards a particular implementation and our problem-oriented tasks are contained at lower levels, then this because very difficult to do.    

At the end of the day, the goal is usually to actually implement a solution to the problem being solved. If our method of representing our algorithm does not lend itself to an orderly implementation of that algorithm, then our method is seriously flawed. Conversely, if our method of representation lends itself to a systematic implementation of the algorithm, then our method is extremely useful.

By "systematic implementation" we mean that we should be able to take our represented algorithm and break it into easily identifiable fragments each of which can be readily translated into one of the structures, such as a while() loop or an if()/else block, available to us in our chosen implementation scheme be it a C program, an assembly language routine, an electronic circuit, or a physical mechanism.

This is one of the reasons why we seldom use flowcharts for algorithms that are slated for implementation using a physical circuit - flowcharts do not lend themselves to aiding such an implementation. But schematics do and properly developed schematics possess all of the properties described above. Likewise, schematics are seldom used to develop algorithms slated for implementation with a computer program for the same reason. However, when collapsed to their most abstract level - the topmost level or two - a well-structured flowchart and a well-structured schematic for a program and circuit, respectively, that solve the same problem may will look nearly identical. The reason is that, in each case, the topmost levels are representing only the logic of the problem and do not contain much, if any, information specific to the eventual means of implementation.

From this point forward, we will restrict the discussion to algorithms that are intended for eventual implementation using a computer program - but the concepts described can be readily generalized to any type of implementation and you should read them with the intent of grasping those generalized concepts.

Most texts maintain that the pseudocode or flowchart for a problem should represent the solution in a manner that is independent of how that solution will eventually be implemented and sufficiently complete such that the person developing the conceptual solution, who may have little if any programming background, can turn the material over to a programmer who could, in turn, decide what programming language to use and proceed to implement the solution without even understanding any of the conceptual goals behind the code being written. For instance, I should be able to give you a flowchart for a function that accepts one value and that then uses that value to produce and return another value. If I have done my job adequately, you should be able to write the function to accomplish this task in any language you are familiar and comfortable with without ever knowing or caring that the function is actually implementing a Bessel Function of Order Zero using truncated Chebyshev polynomials. 

But such a philosophy is needlessly restrictive and fails to recognize some important realities. As discussed in the previous sections, some effort should be put into making the upper levels of the represented algorithm implementation independent. If it is practical to halt the expansion of the algorithm at the point where dealing with implementation specifics is feasible - great. This is likely to be the case if the the purpose of the given flowchart or pseudocode is to communicate the overall approach to a potential investor or an end-user. But generally it is necessary to carry the algorithm development at least a bit further - to step over the "implementation boundary" far enough that the people actually implementing and testing the code can be confident that the level of detail has truly made it into "their world" and that they are dealing only with implementation issues and not problem logic issues.

In point of fact, in the "real world" pseudocode and flowcharts are used in a variety of ways. On rare occasion reality and ideality actually come close to each other and they are used precisely as described above in the Bessel Function example. But, flowcharts also commonly serve as formal documentation for the high level structure of programs and, when used as such, generally offer very little detail but, instead, illustrate the overall flow of the program. In these cases, avoiding implementation details is usually pretty important. Other times they are used specifically to show the detailed steps necessary to carry out a specific implementation and, when used this way, are completely dependent on the language and, perhaps, even the processor being used. For instance, the algorithm could be for a new means of computing trigonometric functions using the latest processor instructions so as to increase speed and reduce memory usage. Such an algorithm is fundamentally tied to the implementation - but then so is the very problem that is being solved. The problem isn't how to compute the value of the sine of an angle, the problem is how to efficiently use the latest processor resources to compute the value of the sine of an angle - a subtle but critical distinction.

However, the vast majority of cases falls somewhere between these two extremes. From a code development point of view, pseudocode and flowcharts are generally very informal and incomplete - their purpose is to guide the programmer's thoughts just far enough to enable them to proceed with the coding directly. This is particularly the case when the person writing the pseudocode and the person writing the source code are one and the same but it is also quite common even when one person (or team) is preparing the flowcharts and another person (or team) is writing the code, especially if there is good communication back and forth. It is not uncommon to see a flow chart that is very chaotic in that one section has virtually no detail while other parts are documented in excruciating detail. The sparse sections probably represent portions where the programmer is comfortable with the tasks and needs very little guidance while the highly detailed sections are probably where the programmer is unfamiliar with the concepts or having a difficult time getting correct results.

Just like in the "real world", the guidelines in this course reflect the purposes of the pseudocode or flowchart being submitted - and there are two of them. In addition to guiding your own code development efforts, what is submitted must also serve to satisfy the grader that you have an adequate understanding of the problem being solved and have a viable approach to its solution. Keep in mind that the grader's sole insight into whether you know how to perform a particular task is what you have presented. The grader is not a mind reader and is not expected to make any effort to become one. A useful guideline for how detailed your pseudocode or flowchart should be is that it should be reasonable for you to hand it to another student in the course who is about average in their performance and who has been keeping up with the material to date (but no further) and expect them to be able to implement the code with little or no difficulty even if they have not seen the problem previously. 

Imbedded in this guideline are a few subtleties. As we reach new material, your pseudocode and flowcharts should be more detailed with regards to that material than it needs to be when dealing with material from considerably earlier in the course. It will be understood (hoped?) that your programming skills are improving and that your pseudocode and flowcharts don't need to be as detailed about material that you should be familiar with. However, if your source code demonstrates that you are not yet adequately comfortable and proficient with a particular topic, don't be surprised to lose points for inadequately detailed pseudocode or flowcharts. In general you will not lose points for presenting your pseudocode/flowcharts in too detail.

As mentioned previously, pseudocode is ideally language independent, however the reality is that all of the pseudocode you write in this course will be used to implement source code in a specific programming language, namely C. It is therefore permissible for you to use C statements and constructs in your pseudocode and flowcharts. By similar reasoning, it is NOT permissible to use statements and constructs from Matlab, Basic, Java, or any other language you might be familiar with. This is not to say that you can't use these in pseudocode or flowcharts that you are using strictly for yourself (how would we know, anyway?) but only that the pseudocode you submit for grading must be free of them. Be aware that there is a danger to using language elements within your pseudocode - which is one of the reasons why the use is generally frowned upon. By using language elements it becomes very easy to lose focus on representing the logic of the problem solution and begin focusing on the logic of the implementation. Keep in mind that pseudocode and flowcharts are not simply another way of expressing your program - they are to represent the logic behind how the problem is solved. 

Even if you don't use actual C statements within your pseudocode or flowchart, it is highly encouraged that the structure of your algorithm be laid to match the control structures available to you in C. Doing so will drastically decrease the amount of time you spend converting the algorithm to viable C code.

To a much greater degree than programming style guidelines, there are very few commonly accepted standards for how pseudocode is written. This generally reflects the fact that it is used primarily as a rather short-term communication between members working on a specific project - the code itself and other documents are used for long-term archival purposes. Where those other documents use algorithm representations, flowcharts tend to be the preferred means because they convey structure much more effectively at that level. Therefore, pseudocode tends to be much more informal and a case of "whatever works". Some people choose to write their pseudocode very much as though it were a true programming language with very formal constructs. In fact, a common project in some software engineering courses is to devise a formal pseudocode and a translator that converts the pseudocode into actual code in some programming language. On the other end of the spectrum, some people write their pseudocode almost like a free-verse description of what the program needs to do.

The authors of your text tend to be more toward the latter end of the spectrum. You will probably notice that they seldom present highly detailed steps and generally prefer to describe what the input is, what the output should be, and then discuss how they go about producing that output. This is perfectly acceptable. You should probably also note that when they do represent an algorithm as a list of steps, they tend to use statements like "Repeat lines 15 through 17 while x < 4". This is also perfectly valid, but I think you will quickly discover a major disadvantage to writing your pseudocode this way. The frequent references to specific line numbers does not present a problem to someone reading the pseudocode, but when you're writing your pseudocode you will find two things to be very true - you will frequently be referring to lines that haven't been written yet meaning that you will have to go back and add the line numbers, once known, to earlier instructions. Worse, you will find that the line numbers keep changing as you add and delete lines. Just adding a single line at the top of your list means that every line number that appears in any instruction now has to be updated.

Fortunately, this last drawback can be avoided in a couple of ways. The first way is to provide labels for some of the instructions - namely the lines referred to in other instructions. The other way is to use indenting or some other means of showing that some instructions are controlled by other, higher level instructions. Your authors use this latter approach in their solution to Exercise 1.5.7 (in the back of the book). If you look at line 14, you will notice that the authors could have left out the statement "repeat lines 15 and 16" because lines 15 and 16 are the only two lines that are indented more than line 14. The same is true every place else the level of indenting changes. But also notice that, relying on the indenting alone, can get confusing. For instance, it's hard to tell exactly which of the instructions line 19 is associated with (and the fact that it is on the next page simply makes matters worse).

Fortunately again, there is a pretty easy way around this as well, though your authors elect not to use it. It is called the "legal outline". In legal documents it is necessary to be able to refer to specific sections or even specific clauses of the document in an unambiguous fashion and a simple means of numbering sections and their component parts was adopted for that purpose. This, combined with a commitment to adhere to the use of structured programming constructs (sequence, selection, and repetition), allows the pseudocode to be written entirely without the need to refer to line numbers within any of the instructions.

But using the legal outline notation has drawbacks as well - most notably, it is cumbersome, especially if you are doing it on paper. You can avoid most of this by using the indenting alone to show the structure and adding in the outline numbers at the end. Or, you could completely forego the outline numbers altogether - but if you do that you must be certain that the indenting structure is very clear. This is reasonably easy to accomplish with a fixed-pitch font but can be difficult to accomplish with a proportional pitch font. Another way to circumvent this - and in fact to use it to your advantage - is to develop your pseudocode with a tool that is set up to work with legal outlines. Fortunately, most reasonably featured word processors, including Word, are capable of doing this. Although you cannot submit a Word document as your pseudocode, you can copy and paste the contents of the Word document to an ASCII text file (using Notepad, for instance) and the numbering will be carried over in the operation, which is very convenient.

To aid in communication - particularly between you and the grader (the value of which should be relatively obvious) it is recommended that the problem be decomposed into a set of hierarchical tasks. The lowest-level tasks should either be tasks that are very straightforward to implement directly in C (using your level of knowledge) or the specific instructions for performing the task should be provided. By beginning each line with one of the keywords discussed below, the chance for miscommunication between you and the grader is greatly diminished.

Documentation keywords describe what needs to be done or provides information about why something is being done. You will quickly discover that, if you have done a decent job of writing your pseudocode, that these lines make very useful comment lines in your final code.

A TASK statement is something that the program must perform but that is described at a level more abstract than what can be coded directly. One way to think of it is that you break a problem down into a set of TASKs. Each TASK can, in turn, be broken down into more narrowly defined TASKs. At some point, the TASK can be described in terms of steps that can be directly implemented. From one perspective, anytime a TASK: keyword is used, it means that there should (or at least could) be a subordinate level of the hierarchy which is the pseudocode for that TASK. In practice, that pseudocode need not be present if the TASK is sufficiently narrow that the person implementing it can go directly from the TASK description to the actual code without the benefit of the detailed steps.

Action keywords are the lines that actually do the work. There are three basic actions that can be carried out: changing the value stored at some location in memory, getting input from some device, or generating output to some device. We will use the SET, GET, and PUT keywords for these actions respectively.

This is an "action" keyword that denotes performing some operation that changes a value in memory. The most common example would be the evaluation of some equation.

This is an "action" keyword that denotes an output operation, generally to the screen. If the destination is anything other than the screen, such as a file or the serial port, then that should be explicitly stated.

While the action keywords perform the actual work, they are insufficient in and of themselves to write all but the most trivial programs. Of the three structured programming constructs, the action keywords are only sufficient to implement the first of them, namely a sequence of instructions. A program's true power comes from the other two - selection and repetition - because they give it the ability to select whether a particular action will actually be carried out based on the information made available to it at the time that it is executed. This ability is the result of controlling the flow of the program which is the purpose of the flow control keywords.

Because flow control is a more complex task that merely executing a single statement, all but the simplest flow control keywords are used in groups and there are some options in how to use them depending on the specific situation.

Selection - Case 1 SEL: (test condition) TRUE: Statement(s) to be executed if test condition is TRUE FALSE Statement(s) to be executed if test condition is FALSE Selection - Case 2 IF: (test condition) Statement(s) to be executed if test condition is TRUE ELSE: Statement(s) to be executed if test condition is FALSE

The advantage of Case 1 is that it clearly identifies the block as a selection construct, but it is a bit more involved than is usually necessary. The format of Case 2 is very close to the format of the actual C code that would result and is therefore a bit more straightforward to convert in the coding process, but not enough so as to be a significant factor.

In a legal outline, the ELSE: statement in Case 2 would be numbered one more than the IF: statement - in other words, if the IF: statement was numbered 3.4.2.6) then the ELSE: statement would be numbered 3.4.2.7). This can be useful or confusing depending upon how you thing of it. If you think of the test condition controlling a single selection construct, then it would be nice if the controlling expression was one level in the outline and everything it controls was at a lower level. So this could be a bit confusing. However, this format actually emphasizes the fact that, in C, an "else" statement truly is a separate statement and that it must immediately follow an "if" statement that is at the same level of control. Neither convention is significantly better than the other - and you should quickly get comfortable with whichever you choose to use.

Repetition - Case 1 LOOP: WHILE: (test condition) Statement(s) to be executed if test condition is TRUE Repetition - Case 2 LOOP: Statement(s) to be executed if test condition is TRUE WHILE: (test condition)

These two cases map directly into the while() and do/while() looping constructs of the C language. In Case 1, the test condition is evaluated prior to making the first pass through the statements controlled by it and, as a result, the possibility exists that those statements won't be executed even once. The only difference in Case 2 is that the statements controlled by the test condition are executed one time and the test is evaluated after that first pass. If the test condition is TRUE then another pass is made - and the test condition evaluated at the end of that and each succeeding pass until the test finally fails.

While the two cases above are more than adequate to represent any looping logic - in fact, either one of them by itself is sufficient, just more cumbersome in some cases - the logic is sometime clearer to the reader if it is expressed in terms of repeating the loop until some some condition is met - meaning that the loop is terminated as soon as the test condition becomes TRUE. 

Repetition - Case 3 LOOP: UNTIL: (test condition) Statement(s) to be executed if test condition is FALSE Repetition - Case 4 LOOP: Statement(s) to be executed if test condition is FALSE UNTIL: (test condition)

Although C does not support a "loop until" construct (some languages do) converting Case 3 to an equivalent form of Case 1 is trivial - you simply invert the test condition. Similarly, Case 4 can be converted to Case 2 by the same mechanism.

Just as the selection construct can be streamlined, so too can a couple of the repetition constructs.

Repetition - Case 5 (streamlined version of Case 1) WHILE: (test condition) Statement(s) to be executed if test condition is TRUE Repetition - Case 6 (streamlined version of Case 3) UNTIL: (test condition) Statement(s) to be executed if test condition is FALSE

Streamlining the other two is more difficult because, since the test comes at the end of the statement within the loop, it is very useful to mark the beginning of those statements in such a way that the fact that it is a loop is readily apparent to the reader. The LOOP: statement does that about as well as any other option would.

As you code loops, you will discover that it is frequently the case that there are steps that are logically associated with the loop but which must reside outside of the loop code. The most common by far is the need to initialize certain variables, especially counters, prior to entering the loop. Much less frequently, it is necessary to perform some cleanup tasks immediately after the loop is exited. A pseudocode construct that gathers all of these together so that their association is obvious is the following:

Repetition - Case 7 REP: PRE: Statement(s) to be executed prior to entering loop WHILE: (test condition) Statement(s) to be executed if test condition is TRUE LOOP: POST: Statement(s) to be executed prior after the loop is finished

The above can be easily altered so as to cover all four of the first four cases. As shown, it implements Case 1. By switching the WHILE: and LOOP: statements it implements Case 2. Similarly, Case 3 is obtained simply by changing the WHILE: to UNTIL: and swapping the UNTIL: with the LOOP: then generated Case 4.

Flowcharts are a graphical means of representing an algorithm, as should be expected, they have advantages and disadvantages compared to pseudocode. One of their primary advantages is that they permit the structure of a program to be easily visualized - even if all the text were to be removed. The human brain is very good at picking out these patterns and keeping them "in the back of the mind" as a reference frame for viewing the code as it develops. 

Most programmers also find it easier to sketch flowcharts on a piece of paper and to modify them by crossing out connection arrows and drawing new ones that they would working with pseudocode by hand. By the same token, most programmers do not like to develop flowcharts in an electronic format because the overhead of creating and modifying it is generally more than they want to deal with while pseudocode lends itself to such electronic development. 

Furthermore, if the pseudocode is already in an electronic format that has been structured to lend itself to translation to the final language - such as the one recommended in the previous section - then doing so can be a very simply matter of copying the pseudocode to a new file, overlaying the necessary syntax associated with the language, and compiling the result. This can be a powerful advantage of pseudocode over flowcharts where the entire source code still has to be typed by hand unless you are fortunate to have a tool that can take a flowchart - typically developed using that same tool - and translating it to directly to code. Such tools do exist - and they tend to be rather expensive.

Now that we have looked as some of the pros and cons of flowcharts relative to pseudocode, let's delve into flowcharting itself. The idea behind a flowchart is that it links together a series of blocks each of which perform some specific task. Each of these tasks is represented by a block and has exactly one arrow leading to it and, more importantly, one arrow exiting from it. This is key to the concept of a "structured program". 

The shape of the block may convey additional information about what is happening. For instance, a rectangular block is frequently used to indicated that a computation is occurring while a slanted parallelogram is used to indicate some type of input or output operation. The diversity of shapes that can be used and what they mean is staggering - for instance a different shape can be used to indicated output to a tape drive versus to a hard disk or to indicate output in text format verses binary format. By using such highly specialized symbols, much of what is happening can be conveyed by the symbols themselves. But the power of using these distinctions is generally only useful to people that work with flowcharts continuously, professionally, and who are describing very large and complex systems. At our level, it is far better to restrict ourselves to a minimum number of shapes and explicitly indicate any information that otherwise might have been implied by using a different shape.

The shapes we will use are the circle, the rectangle, the parallelogram, the diamond, and the arrows that interconnect them.

The circle indicates the entry and exit point for the program - or for the current segment of the program. The entry point has exactly one arrow leaving it and the exit point has exactly one arrow entering it. Execution of the program - or of that segment of the program - always starts at the entry point and finishes at the exit point.

The rectangle represents a task that is to be performed. That task might be as simple as incrementing the value of a single variable or as complex as you can imagine. The key point is that it also has a single entry point and a single exit point. 

The parallelogram is used to indicate that some form in input/output operation is occurring. They must also obey the single entry single exit point rule which makes sense given that they are a task-block except with a slightly different shape for the symbol. We could easily eliminate this symbol and use the basic rectangle but the points at which I/O occur within our programs are extremely important and being able to easily and quickly identify them is valuable enough to warrant dealing with a special symbol.

Since a Task block can be arbitrarily complex, it can also contain I/O elements. Whether to use a rectangle or a parallelogram is therefore a judgment call. One way to handle this is to decide whether a task's primary purpose is to perform I/O. Again, that is a judgment call. Another option is to use a symbol that is rectangular on one side and slanted on the other indicating that it is performing both I/O and non-I/O tasks.  

The diamond represents a decision point within our program. A question is asked and depending on the resulting answer, different paths are taken. Therefore a diamond has a single entry point but more than one exit point. Usually, there are two exit points - one that is taken if the answer to the question is "true" and another that is taken if the answer to the question is "false". This is sufficient to represent any type of branching logic including both the typical selection statements and the typical repetition statements. However, most languages support some type of "switch" or "case" statement that allows the program to select one from among a potentially large set of possible paths. The basic two-exit-point diamond is fully capable of representing this construct, but it is generally cleaner and more useful to represent it using a as many exit points from the diamond as there are paths.

The arrows simply show which symbol gets executed next. The rule is that once an arrow leaves a symbol, it must lead directly to exactly one other symbol - arrows can never fork and diverge. They can, however, converge and join arrows coming from other blocks.

• Analysis of Algorithms
• Backtracking
• Dynamic Programming
• Divide and Conquer
• Geometric Algorithms
• Mathematical Algorithms
• Pattern Searching
• Bitwise Algorithms
• Branch & Bound
• Randomized Algorithms

What is Algorithm | Introduction to Algorithms

Definition of algorithm.

The word Algorithm means ” A set of finite rules or instructions to be followed in calculations or other problem-solving operations ” Or ” A procedure for solving a mathematical problem in a finite number of steps that frequently involves recursive operations” .

Therefore Algorithm refers to a sequence of finite steps to solve a particular problem.

Use of the Algorithms:

Algorithms play a crucial role in various fields and have many applications. Some of the key areas where algorithms are used include:

• Computer Science: Algorithms form the basis of computer programming and are used to solve problems ranging from simple sorting and searching to complex tasks such as artificial intelligence and machine learning.
• Mathematics: Algorithms are used to solve mathematical problems, such as finding the optimal solution to a system of linear equations or finding the shortest path in a graph.
• Operations Research : Algorithms are used to optimize and make decisions in fields such as transportation, logistics, and resource allocation.
• Artificial Intelligence: Algorithms are the foundation of artificial intelligence and machine learning, and are used to develop intelligent systems that can perform tasks such as image recognition, natural language processing, and decision-making.
• Data Science: Algorithms are used to analyze, process, and extract insights from large amounts of data in fields such as marketing, finance, and healthcare.

These are just a few examples of the many applications of algorithms. The use of algorithms is continually expanding as new technologies and fields emerge, making it a vital component of modern society.

Algorithms can be simple and complex depending on what you want to achieve.

It can be understood by taking the example of cooking a new recipe. To cook a new recipe, one reads the instructions and steps and executes them one by one, in the given sequence. The result thus obtained is the new dish is cooked perfectly. Every time you use your phone, computer, laptop, or calculator you are using Algorithms. Similarly, algorithms help to do a task in programming to get the expected output.

The Algorithm designed are language-independent, i.e. they are just plain instructions that can be implemented in any language, and yet the output will be the same, as expected.

What is the need for algorithms?

• Algorithms are necessary for solving complex problems efficiently and effectively. 
• They help to automate processes and make them more reliable, faster, and easier to perform.
• Algorithms also enable computers to perform tasks that would be difficult or impossible for humans to do manually.
• They are used in various fields such as mathematics, computer science, engineering, finance, and many others to optimize processes, analyze data, make predictions, and provide solutions to problems.

What are the Characteristics of an Algorithm?

As one would not follow any written instructions to cook the recipe, but only the standard one. Similarly, not all written instructions for programming are an algorithm. For some instructions to be an algorithm, it must have the following characteristics:

• Clear and Unambiguous : The algorithm should be unambiguous. Each of its steps should be clear in all aspects and must lead to only one meaning.
• Well-Defined Inputs : If an algorithm says to take inputs, it should be well-defined inputs. It may or may not take input.
• Well-Defined Outputs: The algorithm must clearly define what output will be yielded and it should be well-defined as well. It should produce at least 1 output.
• Finite-ness: The algorithm must be finite, i.e. it should terminate after a finite time.
• Feasible: The algorithm must be simple, generic, and practical, such that it can be executed with the available resources. It must not contain some future technology or anything.
• Language Independent: The Algorithm designed must be language-independent, i.e. it must be just plain instructions that can be implemented in any language, and yet the output will be the same, as expected.
• Input : An algorithm has zero or more inputs. Each that contains a fundamental operator must accept zero or more inputs.
•   Output : An algorithm produces at least one output. Every instruction that contains a fundamental operator must accept zero or more inputs.
• Definiteness: All instructions in an algorithm must be unambiguous, precise, and easy to interpret. By referring to any of the instructions in an algorithm one can clearly understand what is to be done. Every fundamental operator in instruction must be defined without any ambiguity.
• Finiteness: An algorithm must terminate after a finite number of steps in all test cases. Every instruction which contains a fundamental operator must be terminated within a finite amount of time. Infinite loops or recursive functions without base conditions do not possess finiteness.
• Effectiveness: An algorithm must be developed by using very basic, simple, and feasible operations so that one can trace it out by using just paper and pencil.

Properties of Algorithm:

• It should terminate after a finite time.
• It should produce at least one output.
• It should take zero or more input.
• It should be deterministic means giving the same output for the same input case.
• Every step in the algorithm must be effective i.e. every step should do some work.

Types of Algorithms:

There are several types of algorithms available. Some important algorithms are:

1. Brute Force Algorithm :

It is the simplest approach to a problem. A brute force algorithm is the first approach that comes to finding when we see a problem.

2. Recursive Algorithm :

A recursive algorithm is based on recursion . In this case, a problem is broken into several sub-parts and called the same function again and again.

3. Backtracking Algorithm :

The backtracking algorithm builds the solution by searching among all possible solutions. Using this algorithm, we keep on building the solution following criteria. Whenever a solution fails we trace back to the failure point build on the next solution and continue this process till we find the solution or all possible solutions are looked after.

4. Searching Algorithm :

Searching algorithms are the ones that are used for searching elements or groups of elements from a particular data structure. They can be of different types based on their approach or the data structure in which the element should be found.

5. Sorting Algorithm :

Sorting is arranging a group of data in a particular manner according to the requirement. The algorithms which help in performing this function are called sorting algorithms. Generally sorting algorithms are used to sort groups of data in an increasing or decreasing manner.

6. Hashing Algorithm :

Hashing algorithms work similarly to the searching algorithm. But they contain an index with a key ID. In hashing, a key is assigned to specific data.

7. Divide and Conquer Algorithm :

This algorithm breaks a problem into sub-problems, solves a single sub-problem, and merges the solutions to get the final solution. It consists of the following three steps:

8. Greedy Algorithm :

In this type of algorithm, the solution is built part by part. The solution for the next part is built based on the immediate benefit of the next part. The one solution that gives the most benefit will be chosen as the solution for the next part.

9. Dynamic Programming Algorithm :

This algorithm uses the concept of using the already found solution to avoid repetitive calculation of the same part of the problem. It divides the problem into smaller overlapping subproblems and solves them.

10. Randomized Algorithm :

In the randomized algorithm, we use a random number so it gives immediate benefit. The random number helps in deciding the expected outcome.

To learn more about the types of algorithms refer to the article about “ Types of Algorithms “.

Advantages of Algorithms:

• It is easy to understand.
• An algorithm is a step-wise representation of a solution to a given problem.
• In an Algorithm the problem is broken down into smaller pieces or steps hence, it is easier for the programmer to convert it into an actual program.

Disadvantages of Algorithms :

• Writing an algorithm takes a long time so it is time-consuming.
• Understanding complex logic through algorithms can be very difficult.
• Branching and Looping statements are difficult to show in Algorithms (imp) .

How to Design an Algorithm?

To write an algorithm, the following things are needed as a pre-requisite: 

• The problem that is to be solved by this algorithm i.e. clear problem definition.
• The constraints of the problem must be considered while solving the problem.
• The input to be taken to solve the problem.
• The output is to be expected when the problem is solved.
• The solution to this problem is within the given constraints.

Then the algorithm is written with the help of the above parameters such that it solves the problem.

Example: Consider the example to add three numbers and print the sum.

Step 1: Fulfilling the pre-requisites  

As discussed above, to write an algorithm, its prerequisites must be fulfilled. 

• The problem that is to be solved by this algorithm : Add 3 numbers and print their sum.
• The constraints of the problem that must be considered while solving the problem : The numbers must contain only digits and no other characters.
• The input to be taken to solve the problem: The three numbers to be added.
• The output to be expected when the problem is solved: The sum of the three numbers taken as the input i.e. a single integer value.
• The solution to this problem, in the given constraints: The solution consists of adding the 3 numbers. It can be done with the help of the ‘+’ operator, or bit-wise, or any other method.

Step 2: Designing the algorithm

Now let’s design the algorithm with the help of the above pre-requisites:

Algorithm to add 3 numbers and print their sum:  

• Declare 3 integer variables num1, num2, and num3.
• Take the three numbers, to be added, as inputs in variables num1, num2, and num3 respectively.
• Declare an integer variable sum to store the resultant sum of the 3 numbers.
• Add the 3 numbers and store the result in the variable sum.
• Print the value of the variable sum

Step 3: Testing the algorithm by implementing it.

To test the algorithm, let’s implement it in C language.

// C++ program to add three numbers // with the help of above designed // algorithm #include <bits/stdc++.h> using namespace std ; int main () { // Variables to take the input of // the 3 numbers int num1 , num2 , num3 ; // Variable to store the resultant sum int sum ; // Take the 3 numbers as input cout << "Enter the 1st number: " ; cin >> num1 ; cout << " " << num1 << endl ; cout << "Enter the 2nd number: " ; cin >> num2 ; cout << " " << num2 << endl ; cout << "Enter the 3rd number: " ; cin >> num3 ; cout << " " << num3 ; // Calculate the sum using + operator // and store it in variable sum sum = num1 + num2 + num3 ; // Print the sum cout << " \n Sum of the 3 numbers is: " << sum ; return 0 ; } // This code is contributed by shivanisinghss2110

// C program to add three numbers // with the help of above designed algorithm #include <stdio.h> int main () { // Variables to take the input of the 3 numbers int num1 , num2 , num3 ; // Variable to store the resultant sum int sum ; // Take the 3 numbers as input printf ( "Enter the 1st number: " ); scanf ( "%d" , & num1 ); printf ( "%d \n " , num1 ); printf ( "Enter the 2nd number: " ); scanf ( "%d" , & num2 ); printf ( "%d \n " , num2 ); printf ( "Enter the 3rd number: " ); scanf ( "%d" , & num3 ); printf ( "%d \n " , num3 ); // Calculate the sum using + operator // and store it in variable sum sum = num1 + num2 + num3 ; // Print the sum printf ( " \n Sum of the 3 numbers is: %d" , sum ); return 0 ; }

// Java program to add the three numbers // with the help of above designed // algorithm import java.util.* ; class GFG { public static void main ( String [] args ) { // Variable to store the resultant sum int sum = 0 ; // Declare the object and initialize with // predefined standard input object Scanner sc = new Scanner ( System . in ); // Scanner definition // Variables to take the input of // the 3 numbers System . out . println ( "Enter the 1st number: " ); int num1 = sc . nextInt (); // input is an Integer // read by nextInt() function System . out . println ( " " + num1 ); System . out . println ( "Enter the 2nd number: " ); int num2 = sc . nextInt (); System . out . println ( " " + num2 ); System . out . println ( "Enter the 3rd number: " ); int num3 = sc . nextInt (); System . out . println ( " " + num3 ); // Calculate the sum using + operator // and store it in variable sum sum = num1 + num2 + num3 ; System . out . println ( "Sum of the 3 numbers is = " + sum ); } } /*This code is contributed by Rishab Dugar*/

# Python3 program to add three numbers # with the help of above designed # algorithm if __name__ == "__main__" : # Variables to take the input of # the 3 numbers num1 = num2 = num3 = 0 # Variable to store the resultant sum sum = 0 # Take the 3 numbers as input num1 = int ( input ( "Enter the 1st number: " )) num2 = int ( input ( "Enter the 2nd number: " )) num3 = int ( input ( "Enter the 3rd number: " )) # Calculate the sum using + operator # and store it in variable sum sum = num1 + num2 + num3 # Print the sum print ( " \n Sum of the 3 numbers is:" , sum )

// C# program to add the three numbers // with the help of above designed // algorithm using System ; class GFG { static public void Main () { // Variable to store the resultant sum int sum = 0 ; // Variables to take the input of // the 3 numbers Console . Write ( "Enter the 1st number: " ); int num1 = int . Parse ( Console . ReadLine ()); Console . WriteLine ( " " + num1 ); Console . Write ( "Enter the 2nd number: " ); int num2 = int . Parse ( Console . ReadLine ()); Console . WriteLine ( " " + num2 ); Console . Write ( "Enter the 3rd number: " ); int num3 = int . Parse ( Console . ReadLine ()); Console . WriteLine ( " " + num3 ); // Calculate the sum using + operator // and store it in variable sum sum = num1 + num2 + num3 ; Console . WriteLine ( "Sum of the 3 numbers is = " + sum ); } } /*This code is contributed by Pushpesh Raj*/

// Javascript program to add three numbers // with the help of above designed // algorithm // Variables to take the input of // the 3 numbers let num1 = 0 , num2 = 0 , num3 = 0 ; // Variable to store the resultant sum let sum = 0 ; // Take the 3 numbers as input console . log ( "Enter the 1st number: " ); num1 = parseInt ( prompt ()); console . log ( " " + num1 + "<br>" ); console . log ( "Enter the 2nd number: " ); num2 = parseInt ( prompt ()); console . log ( " " + num2 + "<br>" ); console . log ( "Enter the 3rd number: " ); num3 = parseInt ( prompt ()); console . log ( " " + num3 ); // Calculate the sum using + operator // and store it in variable sum sum = num1 + num2 + num3 ; // Print the sum console . log ( "<br>Sum of the 3 numbers is: " + sum ); // This code is contributed by Aman Kumar

Enter the 1st number: 0 Enter the 2nd number: 0 Enter the 3rd number: -1577141152 Sum of the 3 numbers is: -1577141152

Here is the step-by-step algorithm of the code:

• Declare three variables num1, num2, and num3 to store the three numbers to be added.
• Declare a variable sum to store the sum of the three numbers.
• Use the cout statement to prompt the user to enter the first number.
• Use the cin statement to read the first number and store it in num1.
• Use the cout statement to prompt the user to enter the second number.
• Use the cin statement to read the second number and store it in num2.
• Use the cout statement to prompt the user to enter the third number.
• Use the cin statement to read and store the third number in num3.
• Calculate the sum of the three numbers using the + operator and store it in the sum variable.
• Use the cout statement to print the sum of the three numbers.
• The main function returns 0, which indicates the successful execution of the program.

Time complexity: O(1) Auxiliary Space: O(1) 

One problem, many solutions: The solution to an algorithm can be or cannot be more than one. It means that while implementing the algorithm, there can be more than one method to implement it. For example, in the above problem of adding 3 numbers, the sum can be calculated in many ways:

• Bit-wise operators

How to analyze an Algorithm? 

For a standard algorithm to be good, it must be efficient. Hence the efficiency of an algorithm must be checked and maintained. It can be in two stages:

1. Priori Analysis:

“Priori” means “before”. Hence Priori analysis means checking the algorithm before its implementation. In this, the algorithm is checked when it is written in the form of theoretical steps. This Efficiency of an algorithm is measured by assuming that all other factors, for example, processor speed, are constant and have no effect on the implementation. This is done usually by the algorithm designer. This analysis is independent of the type of hardware and language of the compiler. It gives the approximate answers for the complexity of the program.

2. Posterior Analysis:

“Posterior” means “after”. Hence Posterior analysis means checking the algorithm after its implementation. In this, the algorithm is checked by implementing it in any programming language and executing it. This analysis helps to get the actual and real analysis report about correctness(for every possible input/s if it shows/returns correct output or not), space required, time consumed, etc. That is, it is dependent on the language of the compiler and the type of hardware used.

What is Algorithm complexity and how to find it?

An algorithm is defined as complex based on the amount of Space and Time it consumes. Hence the Complexity of an algorithm refers to the measure of the time that it will need to execute and get the expected output, and the Space it will need to store all the data (input, temporary data, and output). Hence these two factors define the efficiency of an algorithm.  The two factors of Algorithm Complexity are:

• Time Factor : Time is measured by counting the number of key operations such as comparisons in the sorting algorithm.
• Space Factor : Space is measured by counting the maximum memory space required by the algorithm to run/execute.

Therefore the complexity of an algorithm can be divided into two types :

1. Space Complexity : The space complexity of an algorithm refers to the amount of memory required by the algorithm to store the variables and get the result. This can be for inputs, temporary operations, or outputs. 

How to calculate Space Complexity? The space complexity of an algorithm is calculated by determining the following 2 components:   

• Fixed Part: This refers to the space that is required by the algorithm. For example, input variables, output variables, program size, etc.
• Variable Part: This refers to the space that can be different based on the implementation of the algorithm. For example, temporary variables, dynamic memory allocation, recursion stack space, etc. Therefore Space complexity S(P) of any algorithm P is S(P) = C + SP(I) , where C is the fixed part and S(I) is the variable part of the algorithm, which depends on instance characteristic I.

Example: Consider the below algorithm for Linear Search

Step 1: START Step 2: Get n elements of the array in arr and the number to be searched in x Step 3: Start from the leftmost element of arr[] and one by one compare x with each element of arr[] Step 4: If x matches with an element, Print True. Step 5: If x doesn’t match with any of the elements, Print False. Step 6: END Here, There are 2 variables arr[], and x, where the arr[] is the variable part of n elements and x is the fixed part. Hence S(P) = 1+n. So, the space complexity depends on n(number of elements). Now, space depends on data types of given variables and constant types and it will be multiplied accordingly.

2. Time Complexity : The time complexity of an algorithm refers to the amount of time required by the algorithm to execute and get the result. This can be for normal operations, conditional if-else statements, loop statements, etc.

How to Calculate , Time Complexity? The time complexity of an algorithm is also calculated by determining the following 2 components: 

• Constant time part: Any instruction that is executed just once comes in this part. For example, input, output, if-else, switch, arithmetic operations, etc.
• Variable Time Part: Any instruction that is executed more than once, say n times, comes in this part. For example, loops, recursion, etc. Therefore Time complexity  [Tex]T(P)                        [/Tex] of any algorithm P is T(P) = C + TP(I) , where C is the constant time part and TP(I) is the variable part of the algorithm, which depends on the instance characteristic I.

Example: In the algorithm of Linear Search above, the time complexity is calculated as follows:

Step 1: –Constant Time Step 2: — Variable Time (Taking n inputs) Step 3: –Variable Time (Till the length of the Array (n) or the index of the found element) Step 4: –Constant Time Step 5: –Constant Time Step 6: –Constant Time Hence, T(P) = 1 + n + n(1 + 1) + 1 = 2 + 3n, which can be said as T(n).

How to express an Algorithm?

• Natural Language:- Here we express the Algorithm in the natural English language. It is too hard to understand the algorithm from it.
• Flowchart :- Here we express the Algorithm by making a graphical/pictorial representation of it. It is easier to understand than Natural Language.
• Pseudo Code :- Here we express the Algorithm in the form of annotations and informative text written in plain English which is very much similar to the real code but as it has no syntax like any of the programming languages, it can’t be compiled or interpreted by the computer. It is the best way to express an algorithm because it can be understood by even a layman with some school-level knowledge.

Similar Reads

Please login to comment....

• Best Smartwatches in 2024: Top Picks for Every Need
• Top Budgeting Apps in 2024
• 10 Best Parental Control App in 2024
• Top Language Learning Apps in 2024
• GeeksforGeeks Practice - Leading Online Coding Platform

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Help | Advanced Search

Computer Science > Networking and Internet Architecture

Title: a novel improved beluga whale optimization algorithm for solving localization problem in swarm robotic systems.

Abstract: In Swarm Robotic Systems (SRSs), only a few robots are equipped with Global Positioning System (GPS) devices, known as anchors. A challenge lies in inferring the positions of other unknown robots based on the positions of anchors. Existing solutions estimate their positions using distance measurements between unknown robots and anchors. Based on existing solutions, this study proposes a novel meta-heuristic algorithm - Improved Beluga Whale Optimization Algorithm (IBWO) to address the localization problem of SRSs, focusing on enhancing the accuracy of localization results. Simulation results demonstrate the effectiveness of this study. Specifically, we test the localization accuracy of robots under different proportions of anchors, different communication radius of robots, and different total number of robots. Compared to the traditional multilateration method and four other localization methods based on meta-heuristic algorithms, the localization accuracy of this method is consistently superior.

Submission history

Access paper:.

• HTML (experimental)
• Other Formats

References & Citations

• Google Scholar
• Semantic Scholar

BibTeX formatted citation

Bibliographic and Citation Tools

Code, data and media associated with this article, recommenders and search tools.

• Institution

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .

Multi-strategy improved sparrow search algorithm for job shop scheduling problem

New citation alert added.

This alert has been successfully added and will be sent to:

You will be notified whenever a record that you have chosen has been cited.

To manage your alert preferences, click on the button below.

New Citation Alert!

Please log in to your account

Information & Contributors

Bibliometrics & citations, view options, index terms.

Computing methodologies

Artificial intelligence

Control methods

Planning and scheduling

Search methodologies

Heuristic function construction

Mathematics of computing

Probability and statistics

Probabilistic reasoning algorithms

Markov-chain Monte Carlo methods

Simulated annealing

Theory of computation

Design and analysis of algorithms

Recommendations

A hybrid imperialist competitive algorithm for the flexible job shop problem.

Flexible job shop scheduling problem FJSP is one of the hardest combinatorial optimization problems known to be NP-hard. This paper proposes a novel hybrid imperialist competitive algorithm with simulated annealing HICASA for solving the FJSP. HICASA ...

An Improved Adaptive Genetic Algorithm for Job-Shop Scheduling Problem

An adaptive genetic algorithm with some improvement is proposed to solve the job-shop scheduling problem (JSSP) better. The improved adaptive genetic algorithm (IAGA) obtained by applying the improved sigmoid function to adaptive genetic algorithm. And ...

To Solve the Job Shop Scheduling Problem with the Improve Quantum Genetic Algorithm

Job shop scheduling problem has been a typical scheduling problem that has been thoroughly studied over the last few decades. It has been proven to be a NP-hard problem. The purpose of job scheduling is to assign the work pieces to each machine ...

Information

Published in.

Kluwer Academic Publishers

United States

Publication History

Author tags.

• Job shop scheduling
• Sparrow search algorithm
• Tent chaotic
• GA opterator
• Simulated annealing algorithm
• Research-article

Funding Sources

• national natural Science Foundation of China
• Science and Technology Research Project of Henan Province
• Key Scientific Research Projects of Higher Education of Henan Province

Contributors

Other metrics, bibliometrics, article metrics.

• 0 Total Citations
• 0 Total Downloads
• Downloads (Last 12 months) 0
• Downloads (Last 6 weeks) 0

View options

Login options.

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Share this publication link.

Copying failed.

Share on social media

Affiliations, export citations.

• Please download or close your previous search result export first before starting a new bulk export. Preview is not available. By clicking download, a status dialog will open to start the export process. The process may take a few minutes but once it finishes a file will be downloadable from your browser. You may continue to browse the DL while the export process is in progress. Download
• Download citation
• Copy citation

We are preparing your search results for download ...

We will inform you here when the file is ready.

Your file of search results citations is now ready.

Your search export query has expired. Please try again.