Algorithm

An algorithm is a finite set of precise instructions for performing a computation or

for solving a problem.

An algorithm is a set of well-defined instructions to solve a particular problem. It

is also defined as step by step process to solve a given problem.

Properties of Algorithm
Input: An algorithm has input values from a specified set.

Output: From the input values, the algorithm produces the output values from a
specified set. The output values are the solution.

Correctness: An algorithm should produce the correct output values for each set
of input values.

Finiteness: An algorithm should produce the output after a finite number of steps
for any input.

Effectiveness: It must be possible to perform each step of the algorithm correctly

and in a finite amount of time.

Generality: The algorithm should work for all problems of the desired form.

Pseudocode
Pseudocode is an artificial and informal language that helps programmers to
develop an algorithm.

Pseudocode is a "text-based" detail (algorithmic) design tool.

Searching Algorithm
Searching algorithm is used to search an element from a given list of element.

Linear Search
A linear search is also known as a sequential search it is a method of finding an
element within a list. It checks each element of the list sequentially until a match
is found or the whole list has been searched.

Pseudocode:
Input: x: integer, [a1, . . . an] : list of distinct integers.
Output: Index i if x = ai or 0 if x is not in the list.

i=0 // first position of list of the number

While i < n
If x=ai then
return i
i=i+1
If i = n then return := 0

Binary Search
Binary search is an efficient algorithm for finding an item from a sorted list of
items.

It works by repeatedly dividing in half the portion of the list that could contain the
item, until you've narrowed down the possible locations to just one.
Pseudocode:
Input: x: integer, [a1, . . . an] : list of distinct integers.
Output: Index i if x = ai or 0 if x is not in the list.

i := 0 // i is the left endpoint of the interval

j := n-1; // j is the right endpoint of the interval
While i < j
m := [(i + j)/2]
If x > am then i := m + 1 else j := m
If x = ai then result := i else result := 0; return result;

Sorting
The arrangement of the list of elements either in ascending or descending or in
alphabetically order in known as Sorting.

There are multiple sorting algorithms available; among them we will elaborate the
following algorithm.

 Bubble Sort
 Insertion Sort
Bubble Sort
Bubble Sort is the simplest sorting algorithm that works by
repeatedly swapping the adjacent elements if they are in wrong
order.

Eg:-

5 6 3 9 4

Insertion Sort
Insertion sort is a simple sorting algorithm that sorts the given list of element.
The array is virtually split into a sorted and an unsorted part. Values from the
unsorted part are picked and placed at the correct position in the sorted part.
Algorithm
To sort an array of size n in ascending order:
1: Iterate from arr[1] to arr[n-1] over the array.
2: Compare the current element (key) to its predecessor.
3: If the key element is smaller than its predecessor, compare it to the elements
before. Move the greater elements one position up to make space for the
swapped element.
Example:
Another Example:
12, 11, 13, 5, 6
Let us loop for i = 1 (second element of the array) to 4 (last
element of the array)
i = 1. Since 11 is smaller than 12, move 12 and insert 11 before
12
11, 12, 13, 5, 6
i = 2. 13 will remain at its position as all elements in A[0..I-1] are
smaller than 13
11, 12, 13, 5, 6
i = 3. 5 will move to the beginning and all other elements from
11 to 13 will move one position ahead of their current position.
5, 11, 12, 13, 6
i = 4. 6 will move to position after 5, and elements from 11 to 13
will move one position ahead of their current position.
5, 6, 11, 12, 13

Pseudocode
for i = 1 to n
key ← A [i]
j ← i – 1
while j > = 0 and A[j] > key
A[j+1] ← A[j]
j ← j – 1
 End while
A[j+1] ← key
End for

Greedy Method
A greedy algorithm is an approach for solving a problem by selecting the best
option available at the moment. It doesn't worry whether the current best result
will bring the overall optimal result.

This is one of the approach/strategy for solving the problem. This method is
useful for solving the optimization problem.

A problem which requires either minimum result or maximum result then that
problem is called as optimization problem.

Eg: P: AB [within 5 hr]

For a problem there will be many solutions but the solution which is satisfying the
condition is called feasible solution.

The solution which is already feasible but also giving the minimum cost , that
solution is called as optimal solution. And for any problem there can be only one
optimal solution.

The list of problem can be solved by using Greedy method.

 Finding Shortest path

 Determining how to encode message using the fewest possible bits.
 Finding the fiber links between network nodes using least amount of fiber.
 Kruskal’s and Prism’s algorithm
 Huffman codes
 Knapsack problem
 Job Scheduling Problem

Halting Problem
Halting means that the program on certain input will accept it and halt or reject
it and halt and it would never go into an infinite loop. This is an decidable
problem because we cannot have an algorithm which will tell us whether a given
program will halt or not in a generalized way

Basically, halting means terminating. So can we have an algorithm that will tell
that the given program will halt or not.

In terms of Turing machine, will it terminate when run on some machine with
some particular given input string.

The answer is no we cannot design a generalized algorithm which can

appropriately say that given a program will ever halt or not?
The only way is to run the program and check whether it halts or not.

Proof by Contradiction
Problem statement: Can we design a machine which if given a program can
find out if that program will always halt or not halt on a particular input?

Soln:
Input − A Turing machine and an input string w.
Problem − Does the Turing machine finish computing of the string w in a finite number of
steps? The answer must be either yes or no.
Proof − At first, we will assume that such a Turing machine exists to solve this problem and
then we will show it is contradicting itself. We will call this Turing machine as a Halting
machine that produces a ‘yes’ or ‘no’ in a finite amount of time. If the halting machine finishes
in a finite amount of time, the output comes as ‘yes’, otherwise as ‘no’. The following is the
block diagram of a Halting machine −
Now we will design an inverted halting machine (HM)’ as −
 If H returns YES, then loop forever.
 If H returns NO, then halt.
The following is the block diagram of an ‘Inverted halting machine’ −

Further, a machine (HM)2 which input itself is constructed as follows −

 If (HM)2 halts on input, loop forever.

 Else, halt.
Here, we have got a contradiction. Hence, the halting problem is undecidable.