حسام حداد تکنولوژی، برنامه‌نویسی، هوش مصنوعی

Guilan Faculty of Engineering
Hesam Haddad

Today we are going to be talking about the Importance of Algorithms in Programming and providing their usage, optimization after definitions.
The main propose of this is to help you have a clear view of algorithms or some basic knowledge.

What’s An Algorithm?
Algorithms are sets of rules to be followed in calculation or other problem solving by computer.

Runtime Analysis
After The correctness of an algorithm to solve all the test cases, the most important thing is runtime.
Computer Scientists typically talk about the runtime relative to the size of input. If the input consists of N integers, an algorithm witch has a runtime proportion to N² represent as O(N²) means that this algorithm terminate and complete after doing N² operations.

An Example Comparison
As a computer science student you all know at least one sorting algorithm, we are going to compare runtime of Bubble Sort, The most famous sorting algorithm with O(N²) runtime and Merge Sort , Another well-known sorting algorithm with O(NlogN) when the input size is a bit large. Also we can estimate that a normal computer complete 10⁸ operation per second.

As you know 100 seconds so differs from within a second for a user waiting. And we can understand that just finding a correct way to solve problem is not enough we need to do in in efficient way. N² is not so bad. There are some algorithms with N! or 2^N runtime just imagine how terrible will they work when the size of input get bigger.

Modular Power Problem
We need to design a fast algorithm getting 3 parameters a, n and k and return  a^n  mod k . Where the mod means remind divisor and you can use it as % sign in c like languages.
I will explain the both efficient and inefficient solutions.
The basic math rules used below as you all know by your high school knowledge.
N.M mod k=N mod k .M mod K
a^N.a^M= a^N+M

Inefficient solution:
We do the calculation easily just by one loop and then return the output. The runtime is O(N).

int modpow(int a,int n, int k){
	int i,out=1%k;
	for(i=0;i<n;i++)
		out=out*a%k;
	return out;
}

int modpow(int a,int n, int k){
	if(n==0)return 1;
	int tmp=modpow(a,n/2,k);
	if(n%2) return (tmp*tmp*a)%k;
	else return (tmp*tmp)%k;
}