Introduction to Algorithm

What is Algorithm?

In this course, we will learn about algorithms through examples.

An algorithm is a series of well-defined instructions for solving a specific problem in computer programming. It accepts a collection of inputs and outputs the desired result. As an example,

An algorithm for multiplying two numbers:

• Consider two numerical inputs.
• Using the + operator, add two numbers together.
• Show the outcome

Qualities of a good Algorithm

• Input and output must be carefully defined.
• Each stage of the algorithm should be distinct and unequivocal.
• Algorithms should be the most effective solution among many possible solutions to a problem.
• Computer code should not be included in an algorithm. Instead, the method should be constructed in a form that allows it to be utilized in a variety of programming languages.

Characteristics of Algorithm

1. Input- 0 or more
2. Output- At least 1 output
3. Definiteness- Should have definite results or solutions
4. Finite- It must be stop or there should be an end state
5. Effectiveness- No unnecessary statement or redundant statements in algorithm

Algorithm

1. Design oriented
2. Need domain knowledge
3. Any language can be used
4. No hardware and operating system specification
5. This is an analysis of any solution

Program

1. Implementation oriented
2. Need programming knowledge
3. Only programming language can be used
4. Specified hardware and operating system
5. This is an testing oriented approach

Prior Analysis

1. Algorithm
2. Independent of language
3. Hardware independent
4. Time and space function

Posterior Analysis

1. Program
2. Language dependent
3. Hardware dependent
4. Analysis of time and bytes

How to write an Algorithm?

Algorithm Sawap(a, b){
		temp:= a ;
			a:= b ;
			b:= temp ;
}

How to analyze an Algorithm?

1. Time - how much time the algorithm is taken?
2. Space- how much space/memory it is consumed?
3. Network consumption- Reduction of data quality for transferring a data.
4. Power consumption- how much power the algorithm will consume?
5. CPU consumption- how many register it is consuming?

Example:

Algorithm Sawap(a, b){
		temp:= a ;  // require 1 unit of time
			a:= b ; // require 1 unit of time
			b:= temp ;  // require 1 unit of time
}

Time analysis: f(n)= 1+1+1 = 3, that means this algorithm require order of 1 or, O(1)

Space analysis: how many variables are require to solve this algorithm?

Here, we require 3 variables to solve swap problem. temp, a, and b. So, S(n)=3 or order of 1 or, O(1)

Frequency Count Method

Example 1:

Algorithm Sum(A, n){
	s=0;   \\require 1 unit of time
	for(i=0; i<n; i++){    \\ require n+1 unit of time
		s=s+A[i]      \\ require n unit of time
	 }
  return s; \\require 1 unit of time
}

Time analysis: f(n)= 1+n+1+n+1=2n+3, that means this algorithm require order of n or, O(n) [the highest power of n in the time function]

Space analysis:

Here we have one array of length n, 'A', variables n, s, and i.

array, A = requires n unit of space

variable, n= requires 1 unit of space

variable, s= requires 1 unit of space

variable, i= requires 1 unit of space

Total S(n) = n+1+1+1= n+3 that means this algorithm require order of n or, O(n) [the highest power of n in the space function]

Example 2:

Algorithm Add_Array(A, B, n){
	for(i=0; i<n; i++){    \\ require n+1 unit of time
			for(j=0; j<n; j++){    \\ require n(n+1) unit of time
				C[i,j]= A[i,j]+B[i,j] ;   \\ require n * n unit of time
			}
	 }
  return C; \\require 1 unit of time
}

Time analysis: f(n)= n+1+n(n+1)+n*n+1=2n^2+2n+1, that means this algorithm require order of n^2 or, O(n^2) [the highest power of n in the time function]

Space analysis:

Here we have one array of length n, 'A, B, C', variables n, j, and i.

array, A = requires n^2 unit of space [As we are using 2d array]

array, B = requires n^2 unit of space [As we are using 2d array]

array, C = requires n^2 unit of space [As we are using 2d array]

variable, n= requires 1 unit of space

variable, i= requires 1 unit of space

variable, j= requires 1 unit of space

Total S(n) = 3n^2+3 that means this algorithm require order of n^2 or, O(n^2) [the highest power of n in the space function]

Example 3: [Do it now!]

Algorithm Multiply_Array(A, B, n){
	for(i=0; i<n; i++){
			for(j=0; j<n; j++){
				C[i,j]= 0 ;
					for(k=0; k<n; k++){
C[i,j]= C[i,j]+ A[i,k]*B[k,j];
					}
			}
	 }
  return C;
}